4.14.1.1 BST Verification [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

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: 

110. <BST verify function 110> =
/* 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 111>

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

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

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

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

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

  return okay;
}

This code is included in 99, 413, and 517.

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

111. <Check tree->bst_count is correct 111> =
/* 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 110, 192, 246, and 296.

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. 

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

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

This code is included in 110 and 296. 

113. <Check counted nodes 113> =
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 112, 193, and 248.

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: 

114. <Recursively verify BST structure 114> =
/* 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 115>

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

115. <Verify binary search tree ordering 115> =
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 114, 190, 242, 295, 334, 372, 416, 453, 486, 519, 552, and 587.

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

116. <Check that the tree contains all the elements it should 116> =
/* 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 110, 192, 246, and 296.

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. 

117. <Check that forward traversal works 117> =
/* 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 110, 192, 246, and 296.

We do a similar traversal in the reverse order: 

118. <Check that backward traversal works 118> =
/* 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 110, 192, 246, and 296.

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: 

119. <Check that traversal from the null element works 119> =
/* 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 110, 192, 246, and 296.

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]