GNU libavl 2.0.1
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;
<@xref{\NODE\, , Check tree.>->bst_count is correct,110}
if (okay)
{
<@xref{\NODE\, , Check BST structure.>,111}
}
if (okay)
{
<@xref{\NODE\, , Check that the tree contains all the elements it should.>,115}
}
if (okay)
{
<@xref{\NODE\, , Check that forward traversal works.>,116}
}
if (okay)
{
<@xref{\NODE\, , Check that backward traversal works.>,117}
}
if (okay)
{
<@xref{\NODE\, , Check that traversal from the null element works.>,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->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->bst_root, &okay, &count, 0, INT_MAX);
<@xref{\NODE\, , Check counted nodes.>,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->bst_data;
<@xref{\NODE\, , 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 @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]
