[bind10-dev] rbtree handle non-terminal design

[feng]

For non-terminal handling, I have do some experiment, the following is the
general idea.

The key point for this task is to find the next node of one node, and for
that we need the node path (all the ancestor nodes)

During find process, we can get the node path( typedef stack<const RBNode<T>
*> NodeChain), if we got the node path, to find

The next node of node, the steps are:

(tree in following sentences means the one level tree, and the whole rbtree
consists of  bunch of trees using down point connected)

If node has down tree, return the smallest(left most)node in the down tree

Otherwise, find the not null successor of node in the tree which node
resides

Otherwise, find the not null successor of the top node in node chain,  if no
null successor we will keep pop the node chain, until the node chain gets
empty

Return null node

 

Successor node of one node, is that 

If node has right node, then it is the leftmost node of right node

Otherwise find the first left branch on the path to root.  If found, the
parent of the branch is the successor.

Otherwise return null node.

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20110101/fe524863/attachment.html>