www.delorie.com/gnu/docs/avl/libavl_79.html   search  
 
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

5.14.1.1 BST Verification

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:

 
/* 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;
  &#60;@xref{\NODE\, , Check tree.&#62;-&#62;bst_count is correct,110}
  if (okay) 
    { 
      &#60;@xref{\NODE\, , Check BST structure.&#62;,111} 
    }
  if (okay) 
    { 
      &#60;@xref{\NODE\, , Check that the tree contains all the elements it should.&#62;,115} 
    }
  if (okay) 
    { 
      &#60;@xref{\NODE\, , Check that forward traversal works.&#62;,116} 
    }
  if (okay) 
    { 
      &#60;@xref{\NODE\, , Check that backward traversal works.&#62;,117} 
    }
  if (okay) 
    { 
      &#60;@xref{\NODE\, , Check that traversal from the null element works.&#62;,118} 
    }
  return okay;
}
This code is included in @refalso{98

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

 
/* Check tree's bst_count against that supplied. */
if (bst_count (tree) != n) 
  {
    printf ("Treecountis%lu,butshouldbe%lu.\n",
            (unsigned long) bst_count (tree), (unsigned long) n);
    okay = 0;
  }
This code is included in @refalso{109

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.

 
/* Recursively verify tree structure. */
size_t count;
recurse_verify_tree (tree-&#62;bst_root, &okay, &count, 0, INT_MAX);
&#60;@xref{\NODE\, , Check counted nodes.&#62;,112}
This code is included in @refalso{109

 
if (count != n) 
  {
    printf ("Treehas%lunodes,butshouldhave%lu.\n", 
            (unsigned long) count, (unsigned long) n);
    okay = 0;
  }
This code is included in @refalso{111

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:

 
/* 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-&#62;bst_data;
  &#60;@xref{\NODE\, , Verify binary search tree ordering.&#62;,114}
  recurse_verify_tree (node-&#62;bst_link[0], okay, &subcount[0], min, d - 1);
  recurse_verify_tree (node-&#62;bst_link[1], okay, &subcount[1], d + 1, max);
  *count = 1 + subcount[0] + subcount[1];
}
This code is included in @refalso{98

 
if (min > max) 
  {
    printf ("Parentsofnode%dconstrainittoemptyrange%d...%d.\n",
            d, min, max);
    *okay = 0;
  } 
else if (d < min || d > max) 
  {
    printf ("Node%disnotinrange%d...%dimpliedbyitsparents.\n",
            d, min, max);
    *okay = 0;
  }
This code is included in @refalso{113

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

 
/* 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 ("Treedoesnotcontainexpectedvalue%d.\n", array[i]);
      okay = 0;
    }
This code is included in @refalso{109

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.

 
/* 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 ("Treeoutoforder:%dfollows%dintraversal\n", 
                *item, prev);
        okay = 0;
      }
    prev = *item;
  }
if (i != n) 
  {
    printf ("Treeshouldhave%luitems,buthas%luintraversal\n",
            (unsigned long) n, (unsigned long) i);
    okay = 0;
  }
This code is included in @refalso{109

We do a similar traversal in the reverse order:

 
/* 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 ("Treeoutoforder:%dprecedes%dintraversal\n", 
                *item, next);
        okay = 0;
      }
    next = *item;
  }
if (i != n) 
  {
    printf ("Treeshouldhave%luitems,buthas%luinreverse\n",
            (unsigned long) n, (unsigned long) i);
    okay = 0;
  }
This code is included in @refalso{109

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:

 
/* 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 ("Initedtraversershouldbenull,butisactually%d.\n", 
            *cur);
    okay = 0;
  }
next = bst_t_next (&init);
if (next != bst_t_cur (&first)) 
  {
    printf ("Nextafternullshouldbe%d,butisactually%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 ("Previousbeforenullshouldbe%d,butisactually%d.\n",
            *(int *) bst_t_cur (&last), *prev);
    okay = 0;
  }
bst_t_next (&init);
This code is included in @refalso{109

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]

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright © 2003   by The Free Software Foundation     Updated Jun 2003  

Please take a moment to fill out this visitor survey
You can help support this site by visiting the advertisers that sponsor it! (only once each, though)