Finding the correct ancestor in a 2-3 Tree

Question

So I am having trouble finding the correct ancestor in a 2-3 Tree. In a 2-3 Tree of arbitrary height, there are a couple of cases to look for.

My nodes are designed as follows:

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

Is there an algorithm or something similar to find the proper ancestor to a node?

For example, say we were looking for the ancestor of H (bottom of the provided tree), it is obvious from a visual perspective that ancestor of H is the H at the root of the tree. But that requires jumping up 4 parent links. The tree could be of arbitrary size which is the issue.

My goal in the end is to create an iterator that does an in order traversal of the 2-3 tree. The purpose of finding an ancestor node is that the ancestor node will be the in-order successor of the leaf node that is the right child of it's parent node. Again, as in the example provided above.

score 2 · Answer 1 · answered Apr 13 '16 at 04:24

2

If the goal is simply to traverse a 2-3 tree in-order, then you just need to write a recursive function that starts at the root.

The algorithm is as follows:

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.

answered Apr 13 '16 at 04:24

Luke Pillar

164
1
4

Unfortunately this does not answer my question. I am not trying to achieve a "one-shot" in-order traversal. I am creating an object that holds state in any spot in a tree. From that spot the object would be able to move to the successor, and if there were no more successors return the past the end iterator, null. – Saggitori Apr 13 '16 at 04:48
Then the stated goal in your original post is incorrect: you are not trying to create an iterator that does an in-order traversal of a 2-3 tree. If you specifically need to find the most recent parent that satisfies some constraint (such as having an equivalent key,) then the most efficient way to do so is just to crawl back up through the parent links that you've already created, which will scale in logarithmic time with the size of the tree. – Luke Pillar Apr 13 '16 at 04:58
Exactly, which the algorithm you provided does not account for. For example if my iterator is at leaf N in the provided example then the successor should be internal node O. Saying "crawl back up the parent node" is fine, it works, but I need to be able to do it from the scope of node N. Node N does not know which child it is, or from which branch it came from. All it knows is that its parent is internal node M. I need to stop at O by going back up through the parents and comparing values, but with repetitions this can become dangerous. – Saggitori Apr 13 '16 at 05:13
The algorithm I provided doesn't include that functionality, but it's trivial to add. Your node definition already includes a link to the node's parent. Just add code to populate and maintain the parent node link. Crawling up the sequence of links to check each parent is neither dangerous nor inefficient. However, I still cannot understand why you would want to do this as part of an in-order traversal. Needing to crawl up a tree from the context of a leaf is a very anti-tree concept. – Luke Pillar Apr 13 '16 at 05:22

Finding the correct ancestor in a 2-3 Tree

1 Answers1