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

Question

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

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

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

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

$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>";
}

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

1

algorithm b-tree b-tree-index php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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 (), но у меня нет времени сейчас на это разбираться.

0