www.delorie.com/gnu/docs/avl/libavl_110.html

search

	Buy GNU books!

GNU libavl 2.0.1

6.8 Testing

Our job isn't done until we can demonstrate that our code works. We'll do this with a test program built using the framework from the previous chapter (see section 5.14 Testing). All we have to do is produce functions for AVL trees that correspond to each of those in <@xref{\NODE\, , bst-test.c.>,98}. This just involves making small changes to the functions used there. They are presented below without additional comment.

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <limits.h> #include <stdio.h> #include "avl.h" #include "test.h" <@xref{\NODE\, , BST print function; bst =>.> avl,119} <@xref{\NODE\, , BST traverser check function; bst =>.> avl,104} <@xref{\NODE\, , Compare two AVL trees for structure and content.>,187} <@xref{\NODE\, , Recursively verify AVL tree structure.>,188} <@xref{\NODE\, , AVL tree verify function.>,190} <@xref{\NODE\, , BST test function; bst =>.> avl,100} <@xref{\NODE\, , BST overflow test function; bst =>.> avl,122}

static int compare_trees (struct avl_node *a, struct avl_node *b) { int okay; if (a == NULL || b == NULL) { assert (a == NULL && b == NULL); return 1; } if (*(int *) a->avl_data != *(int *) b->avl_data || ((a->avl_link[0] != NULL) != (b->avl_link[0] != NULL)) || ((a->avl_link[1] != NULL) != (b->avl_link[1] != NULL)) || a->avl_balance != b->avl_balance) { printf ("Copiednodesdiffer:a=%d(bal=%d)b=%d(bal=%d)a:", *(int *) a->avl_data, a->avl_balance, *(int *) b->avl_data, b->avl_balance); if (a->avl_link[0] != NULL) printf ("l"); if (a->avl_link[1] != NULL) printf ("r"); printf ("b:"); if (b->avl_link[0] != NULL) printf ("l"); if (b->avl_link[1] != NULL) printf ("r"); printf ("\n"); return 0; } okay = 1; if (a->avl_link[0] != NULL) okay &= compare_trees (a->avl_link[0], b->avl_link[0]); if (a->avl_link[1] != NULL) okay &= compare_trees (a->avl_link[1], b->avl_link[1]); return okay; }

This code is included in @refalso{186

/* 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. Sets *height to the tree's height. All the nodes in the tree are verified to be at least min but no greater than max. */ static void recurse_verify_tree (struct avl_node *node, int *okay, size_t *count, int min, int max, int *height) { int d; /* Value of this node's data. */ size_t subcount[2]; /* Number of nodes in subtrees. */ int subheight[2]; /* Heights of subtrees. */ if (node == NULL) { *count = 0; *height = 0; return; } d = *(int *) node->avl_data; <@xref{\NODE\, , Verify binary search tree ordering.>,114} recurse_verify_tree (node->avl_link[0], okay, &subcount[0], min, d - 1, &subheight[0]); recurse_verify_tree (node->avl_link[1], okay, &subcount[1], d + 1, max, &subheight[1]); *count = 1 + subcount[0] + subcount[1]; *height = 1 + (subheight[0] > subheight[1] ? subheight[0] : subheight[1]); <@xref{\NODE\, , Verify AVL node balance factor.>,189} }

This code is included in @refalso{186

if (subheight[1] - subheight[0] != node-&#62;avl_balance) { printf ("Balancefactorofnode%dis%d,butshouldbe%d.\n", d, node-&#62;avl_balance, subheight[1] - subheight[0]); *okay = 0; } else if (node-&#62;avl_balance < -1 || node-&#62;avl_balance > +1) { printf ("Balancefactorofnode%dis%d.\n", d, node-&#62;avl_balance); *okay = 0; }

This code is included in @refalso{188

static int verify_tree (struct avl_table *tree, int array[], size_t n) { int okay = 1; <@xref{\NODE\, , Check tree.>->bst_count is correct; bst => avl,110} if (okay) { <@xref{\NODE\, , Check AVL tree structure.>,191} } if (okay) { <@xref{\NODE\, , Check that the tree contains all the elements it should; bst =>.> avl,115} } if (okay) { <@xref{\NODE\, , Check that forward traversal works; bst =>.> avl,116} } if (okay) { <@xref{\NODE\, , Check that backward traversal works; bst =>.> avl,117} } if (okay) { <@xref{\NODE\, , Check that traversal from the null element works; bst =>.> avl,118} } return okay; }

This code is included in @refalso{186

/* Recursively verify tree structure. */ size_t count; int height; recurse_verify_tree (tree->avl_root, &okay, &count, 0, INT_MAX, &height); <@xref{\NODE\, , Check counted nodes.>,112}

This code is included in @refalso{190