www.delorie.com/gnu/docs/avl/libavl_237.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

14.5.5 Advancing to the Next Node

There are the same three cases for advancing a traverser as the other types of binary trees that we've already looked at. Two of the cases, the ones where we're starting from the null item or a node that has a right child, are unchanged.

The third case, where the node that we're starting from has no right child, is the case that must be revised. We can use the same algorithm that we did for ordinary BSTs without threads or parent pointers, described earlier (see section 5.9.3 Better Iterative Traversal). Simply put, we move upward in the tree until we move up to the right (or until we move off the top of the tree).

The code uses q to move up the tree and p as q's child, so the termination condition is when p is q's left child or q becomes a null pointer. There is a non-null successor in the former case, where the situation looks like this:

pbstsucc

 
void *
pbst_t_next (struct pbst_traverser *trav)
{ assert (trav != NULL); if (trav-&#62;pbst_node == NULL) return pbst_t_first (trav, trav-&#62;pbst_table); else if (trav-&#62;pbst_node-&#62;pbst_link[1] == NULL)
{ struct pbst_node *q, *p; /* Current node and its child. */ for (p = trav-&#62;pbst_node, q = p-&#62;pbst_parent; ;
p = q, q = q-&#62;pbst_parent) if (q == NULL || p == q-&#62;pbst_link[0])
{ trav-&#62;pbst_node = q; return trav-&#62;pbst_node != NULL ? trav-&#62;pbst_node-&#62;pbst_data : NULL; } }
else
{ trav-&#62;pbst_node = trav-&#62;pbst_node-&#62;pbst_link[1]; while (trav-&#62;pbst_node-&#62;pbst_link[0] != NULL) trav-&#62;pbst_node = trav-&#62;pbst_node-&#62;pbst_link[0]; return trav-&#62;pbst_node-&#62;pbst_data; } }
This code is included in @refalso{502

See also: [ Cormen 1990], section 13.2.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003