Нахождение правильного предка в 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)

Алгоритм взят по этой ссылке.