5.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.

180. <AVL traversal functions 180> =
<BST traverser refresher; bst => avl 63>
<BST traverser null initializer; bst => avl 65>
<AVL traverser least-item initializer 182>
<AVL traverser greatest-item initializer 183>
<AVL traverser search initializer 184>
<AVL traverser insertion initializer 181>
<BST traverser copy initializer; bst => avl 70>
<AVL traverser advance function 185>
<AVL traverser back up function 186>
<BST traverser current item function; bst => avl 75>
<BST traverser replacement function; bst => avl 76>

This code is included in 147 and 198.

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:

181. <AVL traverser insertion initializer 181> =
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 180.

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

182. <AVL traverser least-item initializer 182> =
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 180.

183. <AVL traverser greatest-item initializer 183> =
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 180.

184. <AVL traverser search initializer 184> =
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 180.

185. <AVL traverser advance function 185> =
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 180.

186. <AVL traverser back up function 186> =
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 180.

Exercises:

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

    (struct avl_node *) ((char *) p - offsetof (struct avl_node, avl_data))

[answer]