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.

178. <AVL traversal functions 178> =
<BST traverser refresher; bst => avl 62>
<BST traverser null initializer; bst => avl 64>
<AVL traverser least-item initializer 180>
<AVL traverser greatest-item initializer 181>
<AVL traverser search initializer 182>
<AVL traverser insertion initializer 179>
<BST traverser copy initializer; bst => avl 69>
<AVL traverser advance function 183>
<AVL traverser back up function 184>
<BST traverser current item function; bst => avl 74>
<BST traverser replacement function; bst => avl 75>

This code is included in 145 and 196.

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:

179. <AVL traverser insertion initializer 179> =
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 178.

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

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

181. <AVL traverser greatest-item initializer 181> =
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 178.

182. <AVL traverser search initializer 182> =
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 178.

183. <AVL traverser advance function 183> =
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 178.

184. <AVL traverser back up function 184> =
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 178.

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]