GNU libavl 2.0.1

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

search

	Buy GNU books!

GNU libavl 2.0.1

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

6.6 Traversal

Traversal is largely unchanged from BSTs. However, we can be confident that the tree won't easily exceed the maximum stack height, because of the AVL balance condition, so we can omit checking for stack overflow.

<@xref{\NODE\, , BST traverser refresher; bst =>.> avl,62} <@xref{\NODE\, , BST traverser null initializer; bst =>.> avl,64} <@xref{\NODE\, , AVL traverser least-item initializer.>,180} <@xref{\NODE\, , AVL traverser greatest-item initializer.>,181} <@xref{\NODE\, , AVL traverser search initializer.>,182} <@xref{\NODE\, , AVL traverser insertion initializer.>,179} <@xref{\NODE\, , BST traverser copy initializer; bst =>.> avl,69} <@xref{\NODE\, , AVL traverser advance function.>,183} <@xref{\NODE\, , AVL traverser back up function.>,184} <@xref{\NODE\, , BST traverser current item function; bst =>.> avl,74} <@xref{\NODE\, , BST traverser replacement function; bst =>.> avl,75}
This code is included in @refalso{145

We do need to make a new implementation of the insertion traverser initializer. Because insertion into an AVL tree is so complicated, we just write this as a wrapper to avl_probe(). There probably wouldn't be much of a speed improvement by inlining the code anyhow:

void *
avl_t_insert (struct avl_traverser *trav, struct avl_table *tree, void *item)
{ void **p; assert (trav != NULL && tree != NULL && item != NULL); p = avl_probe (tree, item); if (p != NULL)
{ trav->avl_table = tree; trav->avl_node = ((struct avl_node *)
((char *) p - offsetof (struct avl_node, avl_data))); trav->avl_generation = tree->avl_generation - 1; return *p; }
else
{ avl_t_init (trav, tree); return NULL; } }
This code is included in @refalso{178

We will present the rest of the modified functions without further comment.

void *
avl_t_first (struct avl_traverser *trav, struct avl_table *tree)
{ struct avl_node *x; assert (tree != NULL && trav != NULL); trav->avl_table = tree; trav->avl_height = 0; trav->avl_generation = tree->avl_generation; x = tree->avl_root; if (x != NULL) while (x->avl_link[0] != NULL)
{ assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[0]; } trav->avl_node = x; return x != NULL ? x->avl_data : NULL; }
This code is included in @refalso{178

void *
avl_t_last (struct avl_traverser *trav, struct avl_table *tree)
{ struct avl_node *x; assert (tree != NULL && trav != NULL); trav->avl_table = tree; trav->avl_height = 0; trav->avl_generation = tree->avl_generation; x = tree->avl_root; if (x != NULL) while (x->avl_link[1] != NULL)
{ assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[1]; } trav->avl_node = x; return x != NULL ? x->avl_data : NULL; }
This code is included in @refalso{178

void *
avl_t_find (struct avl_traverser *trav, struct avl_table *tree, void *item)
{ struct avl_node *p, *q; assert (trav != NULL && tree != NULL && item != NULL); trav->avl_table = tree; trav->avl_height = 0; trav->avl_generation = tree->avl_generation; for (p = tree->avl_root; p != NULL; p = q)
{ int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); if (cmp < 0)
q = p->avl_link[0]; else if (cmp > 0)
q = p->avl_link[1]; else /* cmp == 0 */
{ trav->avl_node = p; return p->avl_data; } assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = p; } trav->avl_height = 0; trav->avl_node = NULL; return NULL; }
This code is included in @refalso{178

void *
avl_t_next (struct avl_traverser *trav)
{ struct avl_node *x; assert (trav != NULL); if (trav->avl_generation != trav->avl_table->avl_generation) trav_refresh (trav); x = trav->avl_node; if (x == NULL)
{ return avl_t_first (trav, trav->avl_table); }
else if (x->avl_link[1] != NULL)
{ assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[1]; while (x->avl_link[0] != NULL)
{ assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[0]; } }
else
{ struct avl_node *y; do
{ if (trav->avl_height == 0)
{ trav->avl_node = NULL; return NULL; } y = x; x = trav->avl_stack[--trav->avl_height]; }
while (y == x->avl_link[1]); } trav->avl_node = x; return x->avl_data; }
This code is included in @refalso{178

void *
avl_t_prev (struct avl_traverser *trav)
{ struct avl_node *x; assert (trav != NULL); if (trav->avl_generation != trav->avl_table->avl_generation) trav_refresh (trav); x = trav->avl_node; if (x == NULL)
{ return avl_t_last (trav, trav->avl_table); }
else if (x->avl_link[0] != NULL)
{ assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[0]; while (x->avl_link[1] != NULL)
{ assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[1]; } }
else
{ struct avl_node *y; do
{ if (trav->avl_height == 0)
{ trav->avl_node = NULL; return NULL; } y = x; x = trav->avl_stack[--trav->avl_height]; }
while (y == x->avl_link[0]); } trav->avl_node = x; return x->avl_data; }
This code is included in @refalso{178

Exercises:

1. Explain the meaning of this ugly expression, used in avl_t_insert():

[answer]