Поиск правильного предка в 2-3 Дереве

Question

Так что у меня возникли проблемы с поиском правильного предка в 2-3 Дереве. В 2-3 Дереве произвольной высоты есть несколько случаев, чтобы искать.

Мои узлы спроектированы следующим образом:

template<typename DataType> 
struct node{ 
    Node<DataType> *child1; //left-child 
    Node<DataType> *child2; //middle-child (3-node only) 
    Node<DataType> *child3; //right-child 
    Node<DataType> *extraChild; //for splitting purposes 

    Node<DataType> *parent; 

    DataType key1; //key1 <= key2 
    DataType key2; //key2 <= extraKey (only when node needs to be split) 
    DataType extraKey; //for splitting purposes 
}; 

Есть ли алгоритм или что-то подобное, чтобы найти правильный предка к узлу?

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

Моя цель в конце - создать итератор, который совершает обход 2-3 дерева. Цель поиска узла-предка заключается в том, что узел-предок будет преемником в последовательности листового узла, который является правильным потомком его родительского узла. Опять же, как в приведенном выше примере.

Answer 1

Если цель состоит в том, чтобы просто пересечь 2-3 дерева в порядке, вам просто нужно написать рекурсивную функцию, которая начинается с корня.

алгоритм выглядит следующим образом:

traverse(Node n) 

    if n.left != null 
     traverse(n.left) 

    if n.middle != null 
     visit(n.key1) 
     traverse(n.middle) 
     visit(n.key2) 
    else 
     visit(n.key1) 

    if n.right != null 
     traverse(n.right) 

Algorithm taken from this link.