Алгоритм обхода структуры B-дерева

Мне трудно написать функцию обхода, которая выводит родительские узлы дочернего узла.

Взгляните на пример b-дерева

график btree

Вот пример набора данных, который я использую:

$nodes = array(
  array('f','b'),
  array('f','g'),
  array('b','a'),
  array('b','d'),
  array('g','i'),
  array('d','c'),
  array('d','e'),
  array('i','h')
);

Я пытаюсь вывести массив results, содержащий все массивы дочерних узлов, которые содержат родительские ассоциации.

Пример выходных данных:

  • родители узла (d) - (b,f)
  • родители узла (c) (d, b, f)
  • родители узла (h) (i, g, f)

Я не могу понять, как пройти мимо прямого родительского узла.

foreach($nodes as $node){
    //CHECK IF NODE EXISTS
    if(array_key_exists($node[1],$results)){
        //DO NOTHING
        array_push($results[$node[1]],$node[0]);
    }
    else{
        //CREATE NEW CHILD ARRAY
        $results[$node[1]] = [];
        //PUSH PARENT INTO CHILD ARRAY
        array_push($results[$node[1]],$node[0]);
    }
}
foreach($results as $k => $v){
    echo "child[$k] parents(" . implode($v,', ').")" ; 
    echo "</br>";
}

Вопрос: как добиться этого результата наиболее эффективным способом?


php algorithm b-tree-index b-tree
person Community    schedule 20.04.2017    source источник
comment
Пожалуйста, покажите, что вы пытались решить эту проблему самостоятельно.   -  person miken32    schedule 20.04.2017
comment
Добавлен код @miken32.   -  person    schedule 20.04.2017

Ответы (1)


arrow_upward
1
arrow_downward

Лучший способ справиться с такими случаями — использовать рекурсивные функции.

echo findParents('h',$nodes);

function findParents($find,$btree){
      $parents;
        foreach($btree as $node){
            if($node[1]===$find){
                $parents .=$find.',';
                return $parents .= findParents($node[0], $btree);
            }
        }
     return $find;
    }

Проверьте код здесь: https://www.tehplayground.com/ElTdtP61DwFT1qIc

Единственным недостатком является то, что он вернет исходный узел в списке возврата. Но я думаю, с этим можно жить.

Я думаю, что лучшим представлением дерева было бы:

$nodes = array(
  'f'=>array('d','g'),
  'b'=>array('a','d'),
  'g'=>array('i'),
  'd'=>array('c','e'),
  'i'=>array('h')
);

Но для этого потребуется небольшая модификация приведенного выше кода.

Чтобы получить массив в качестве ответа:

function findParentsArray($find,$btree){
  $parentsArray = explode(',',findParents($find,$btree));
  array_shift($parentsArray);
  return $parentsArray;
}

Должна быть возможность сделать это непосредственно в findParents(), но сейчас у меня нет времени разбираться в этом.

person blokeish    schedule 20.04.2017
comment
рекурсивные функции немного сложны для отладки. вы передаете значение вперед findParents('h',[]); -> findParents('i',['i']); -> findParents('g',['i','g']); -> findParents('f',['i','g','f']); но когда функции возвращаются, ничего не возвращается. каждая итерация представляет собой совершенно новый экземпляр функции. Если вы хотите получить массив в качестве ответа, я рекомендую вам создать другую функцию для преобразования строки в массив. Я обновлю исходный пост. - person blokeish; 20.04.2017