[bind10-dev] rbtree handle non-terminal design
feng
hanfeng at cnnic.cn
Sat Jan 1 15:27:01 UTC 2011
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>
More information about the bind10-dev
mailing list