www.delorie.com/gnu/docs/avl/libavl_58.html

search

	Buy GNU books!

GNU libavl 2.0.1

5.9.3.7 Advancing to the Next Node

The algorithm of bst_t_next(), the function for finding a successor, divides neatly into three cases. Two of these are the ones that we discussed earlier in the introduction to this kind of traverser (see section 5.9.3 Better Iterative Traversal). The third case occurs when the last node returned was NULL, in which case we return the least node in the table, in accordance with the semantics for libavl tables. The function outline is this:

void * bst_t_next (struct bst_traverser *trav) { struct bst_node *x; assert (trav != NULL); if (trav->bst_generation != trav->bst_table->bst_generation) trav_refresh (trav); x = trav->bst_node; if (x == NULL) { return bst_t_first (trav, trav->bst_table); } else if (x->bst_link[1] != NULL) { <@xref{\NODE\, , Handle case where x.> has a right child,71} } else { <@xref{\NODE\, , Handle case where x.> has no right child,72} } trav->bst_node = x; return x->bst_data; }

This code is included in @refalso{63

The case where the current node has a right child is accomplished by stepping to the right, then to the left until we can't go any farther, as discussed in detail earlier. The only difference is that we must check for stack overflow. When stack overflow does occur, we recover by calling trav_balance(), then restarting bst_t_next() using a tail-recursive call. The tail recursion will never happen more than once, because trav_balance() ensures that the tree's height is small enough that the stack cannot overflow again:

if (trav->bst_height >= BST_MAX_HEIGHT) { bst_balance (trav->bst_table); return bst_t_next (trav); } trav->bst_stack[trav->bst_height++] = x; x = x->bst_link[1]; while (x->bst_link[0] != NULL) { if (trav->bst_height >= BST_MAX_HEIGHT) { bst_balance (trav->bst_table); return bst_t_next (trav); } trav->bst_stack[trav->bst_height++] = x; x = x->bst_link[0]; }

This code is included in @refalso{70

In the case where the current node has no right child, we move upward in the tree based on the stack of parent pointers that we saved, as described before. When the stack underflows, we know that we've run out of nodes in the tree:

struct bst_node *y; do { if (trav->bst_height == 0) { trav->bst_node = NULL; return NULL; } y = x; x = trav->bst_stack[--trav->bst_height]; } while (y == x->bst_link[1]);

This code is included in @refalso{70