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

search

	Buy GNU books!

GNU libavl 2.0.1

15.8 Testing

The testing code harbors no surprises.

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

/* Compares binary trees rooted at a and b, making sure that they are identical. */ static int compare_trees (struct pavl_node *a, struct pavl_node *b) { int okay; if (a == NULL || b == NULL) { assert (a == NULL && b == NULL); return 1; } if (*(int *) a->pavl_data != *(int *) b->pavl_data || ((a->pavl_link[0] != NULL) != (b->pavl_link[0] != NULL)) || ((a->pavl_link[1] != NULL) != (b->pavl_link[1] != NULL)) || ((a->pavl_parent != NULL) != (b->pavl_parent != NULL)) || (a->pavl_parent != NULL && b->pavl_parent != NULL && a->pavl_parent->pavl_data != b->pavl_parent->pavl_data) || a->pavl_balance != b->pavl_balance) { printf ("Copiednodesdiffer:\n" "a:%d,bal%+d,parent%d,%sleftchild,%srightchild\n" "b:%d,bal%+d,parent%d,%sleftchild,%srightchild\n", *(int *) a->pavl_data, a->pavl_balance, a->pavl_parent != NULL ? *(int *) a->pavl_parent : -1, a->pavl_link[0] != NULL ? "has" : "no", a->pavl_link[1] != NULL ? "has" : "no", *(int *) b->pavl_data, b->pavl_balance, b->pavl_parent != NULL ? *(int *) b->pavl_parent : -1, b->pavl_link[0] != NULL ? "has" : "no", b->pavl_link[1] != NULL ? "has" : "no"); return 0; } okay = 1; if (a->pavl_link[0] != NULL) okay &= compare_trees (a->pavl_link[0], b->pavl_link[0]); if (a->pavl_link[1] != NULL) okay &= compare_trees (a->pavl_link[1], b->pavl_link[1]); return okay; }

This code is included in @refalso{548

static void recurse_verify_tree (struct pavl_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. */ int i; if (node == NULL) { *count = 0; *height = 0; return; } d = *(int *) node->pavl_data; <@xref{\NODE\, , Verify binary search tree ordering.>,114} recurse_verify_tree (node->pavl_link[0], okay, &subcount[0], min, d - 1, &subheight[0]); recurse_verify_tree (node->pavl_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; avl =>.> pavl,189} <@xref{\NODE\, , Verify PBST node parent pointers; pbst =>.> pavl,518} }

This code is included in @refalso{548