BST Verification - GNU libavl 2.0.2

After each change to the tree in the testing program, we call verify_tree() to check that the tree's structure and content are what we think they should be. This function runs through a full gamut of checks, with the following outline:

109. <BST verify function 109> =
/* Checks that tree is well-formed
   and verifies that the values in array[] are actually in tree.  
   There must be n elements in array[] and tree.
   Returns nonzero only if no errors detected. */
static int 
verify_tree (struct bst_table *tree, int array[], size_t n) 
{
  int okay = 1;

  <Check tree->bst_count is correct 110>

  if (okay) 
    { 
      <Check BST structure 111> 
    }

  if (okay) 
    { 
      <Check that the tree contains all the elements it should 115> 
    }

  if (okay) 
    { 
      <Check that forward traversal works 116> 
    }

  if (okay) 
    { 
      <Check that backward traversal works 117> 
    }

  if (okay) 
    { 
      <Check that traversal from the null element works 118> 
    }

  return okay;
}

This code is included in 98, 411, and 515.

The first step just checks that the number of items passed in as n is the same as tree->bst_count.

110. <Check tree->bst_count is correct 110> =
/* Check tree's bst_count against that supplied. */
if (bst_count (tree) != n) 
  {
    printf (" Tree count is %lu, but should be %lu.\n",
            (unsigned long) bst_count (tree), (unsigned long) n);
    okay = 0;
  }

This code is included in 109, 190, 244, and 294.

Next, we verify that the BST has proper structure and that it has the proper number of items. We'll do this recursively because that's easiest and most obviously correct way. Function recurse_verify_tree() for this returns the number of nodes in the BST. After it returns, we verify that this is the expected number.

111. <Check BST structure 111> =
/* Recursively verify tree structure. */
size_t count;

recurse_verify_tree (tree->bst_root, &okay, &count, 0, INT_MAX);
<Check counted nodes 112>

This code is included in 109 and 294.

112. <Check counted nodes 112> =
if (count != n) 
  {
    printf (" Tree has %lu nodes, but should have %lu.\n", 
            (unsigned long) count, (unsigned long) n);
    okay = 0;
  }

This code is included in 111, 191, and 246.

The function recurse_verify_tree() does the recursive verification. It checks that nodes' values increase down to the right and decrease down to the left. We also use it to count the number of nodes actually in the tree:

113. <Recursively verify BST structure 113> =
/* Examines the binary tree rooted at node.  
   Zeroes *okay if an error occurs.  
   Otherwise, does not modify *okay.
   Sets *count to the number of nodes in that tree, 
   including node itself if node != NULL.
   All the nodes in the tree are verified to be at least min 
   but no greater than max. */
static void 
recurse_verify_tree (struct bst_node *node, int *okay, size_t *count, 
                     int min, int max) 
{
  int d;                /* Value of this node's data. */
  size_t subcount[2];   /* Number of nodes in subtrees. */

  if (node == NULL) 
    {
      *count = 0;
      return;
    }
  d = *(int *) node->bst_data;

  <Verify binary search tree ordering 114>

  recurse_verify_tree (node->bst_link[0], okay, &subcount[0], min, d - 1);
  recurse_verify_tree (node->bst_link[1], okay, &subcount[1], d + 1, max);
  *count = 1 + subcount[0] + subcount[1];
}

This code is included in 98.

114. <Verify binary search tree ordering 114> =
if (min > max) 
  {
    printf (" Parents of node %d constrain it to empty range %d...%d.\n",
            d, min, max);
    *okay = 0;
  } 
else if (d < min || d > max) 
  {
    printf (" Node %d is not in range %d...%d implied by its parents.\n",
            d, min, max);
    *okay = 0;
  }

This code is included in 113, 188, 240, 293, 332, 370, 414, 451, 484, 517, 550, and 585.

The third step is to check that the BST indeed contains all of the items that it should:

115. <Check that the tree contains all the elements it should 115> =
/* Check that all the values in array[] are in tree. */
size_t i;

for (i = 0; i < n; i++)
  if (bst_find (tree, &array[i]) == NULL) 
    {
      printf (" Tree does not contain expected value %d.\n", array[i]);
      okay = 0;
    }

This code is included in 109, 190, 244, and 294.

The final steps all check traversal of the BST, first by traversing in forward order from the beginning to the end, then in reverse order, then by checking that the null item behaves correctly. The forward traversal checks that the proper number of items are in the BST. It could appear to have too few items if the tree's pointers are screwed up in one way, or it could appear to have too many items if they are screwed up in another way. We try to figure out how many items actually appear in the tree during traversal, but give up if the count gets to be more than twice that expected, assuming that this indicates a “loop” that will cause traversal to never terminate.

116. <Check that forward traversal works 116> =
/* Check that bst_t_first() and bst_t_next() work properly. */
struct bst_traverser trav;
size_t i;
int prev = -1;
int *item;

for (i = 0, item = bst_t_first (&trav, tree); i < 2 * n && item != NULL;
     i++, item = bst_t_next (&trav)) 
  {
    if (*item <= prev) 
      {
        printf (" Tree out of order: %d follows %d in traversal\n", 
                *item, prev);
        okay = 0;
      }

    prev = *item;
  }

if (i != n) 
  {
    printf (" Tree should have %lu items, but has %lu in traversal\n",
            (unsigned long) n, (unsigned long) i);
    okay = 0;
  }

This code is included in 109, 190, 244, and 294.

We do a similar traversal in the reverse order:

117. <Check that backward traversal works 117> =
/* Check that bst_t_last() and bst_t_prev() work properly. */
struct bst_traverser trav;
size_t i;
int next = INT_MAX;
int *item;

for (i = 0, item = bst_t_last (&trav, tree); i < 2 * n && item != NULL;
     i++, item = bst_t_prev (&trav)) 
  {
    if (*item >= next) 
      {
        printf (" Tree out of order: %d precedes %d in traversal\n", 
                *item, next);
        okay = 0;
      }

    next = *item;
  }

if (i != n) 
  {
    printf (" Tree should have %lu items, but has %lu in reverse\n",
            (unsigned long) n, (unsigned long) i);
    okay = 0;
  }

This code is included in 109, 190, 244, and 294.

The final check to perform on the traverser is to make sure that the traverser null item works properly. We start out a traverser at the null item with bst_t_init(), then make sure that the next item after that, as reported by bst_t_next(), is the same as the item returned by bst_t_init(), and similarly for the previous item:

118. <Check that traversal from the null element works 118> =
/* Check that bst_t_init() works properly. */
struct bst_traverser init, first, last;
int *cur, *prev, *next;

bst_t_init (&init, tree);
bst_t_first (&first, tree);
bst_t_last (&last, tree);

cur = bst_t_cur (&init);
if (cur != NULL) 
  {
    printf (" Inited traverser should be null, but is actually %d.\n", 
            *cur);
    okay = 0;
  }

next = bst_t_next (&init);
if (next != bst_t_cur (&first)) 
  {
    printf (" Next after null should be %d, but is actually %d.\n",
            *(int *) bst_t_cur (&first), *next);
    okay = 0;
  }
bst_t_prev (&init);

prev = bst_t_prev (&init);
if (prev != bst_t_cur (&last)) 
  {
    printf (" Previous before null should be %d, but is actually %d.\n",
            *(int *) bst_t_cur (&last), *prev);
    okay = 0;
  }
bst_t_next (&init);

This code is included in 109, 190, 244, and 294.

Exercises:

1. Many of the segments of code in this section cast size_t arguments to printf() to unsigned long. Why? [answer]

2. Does test() work properly for testing trees with only one item in them? Zero items? [answer]