5.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 Testing BST Functions). All we have to do is produce functions for AVL trees that correspond to each of those in <bst-test.c 99>. This just involves making small changes to the functions used there. They are presented below without additional comment.

188. <avl-test.c 188> =
<Program License 2>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "avl.h"
#include "test.h"

<BST print function; bst => avl 120>
<BST traverser check function; bst => avl 105>
<Compare two AVL trees for structure and content 189>
<Recursively verify AVL tree structure 190>
<AVL tree verify function 192>
<BST test function; bst => avl 101>
<BST overflow test function; bst => avl 123>

189. <Compare two AVL trees for structure and content 189> =
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 (" Copied nodes differ: 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 188.

190. <Recursively verify AVL tree structure 190> =
/* 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;

  <Verify binary search tree ordering 115>

  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]);

  <Verify AVL node balance factor 191>
}

This code is included in 188.

191. <Verify AVL node balance factor 191> =
if (subheight[1] - subheight[0] != node->avl_balance) 
  {
    printf (" Balance factor of node %d is %d, but should be %d.\n",
            d, node->avl_balance, subheight[1] - subheight[0]);
    *okay = 0;
  }
else if (node->avl_balance < -1 || node->avl_balance > +1) 
  {
    printf (" Balance factor of node %d is %d.\n", d, node->avl_balance);
    *okay = 0;
  }

This code is included in 190, 334, 453, and 552.

192. <AVL tree verify function 192> =
static int 
verify_tree (struct avl_table *tree, int array[], size_t n) 
{
  int okay = 1;

  <Check tree->bst_count is correct; bst => avl 111>

  if (okay) 
    { 
      <Check AVL tree structure 193> 
    }

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

  if (okay) 
    { 
      <Check that forward traversal works; bst => avl 117> 
    }

  if (okay) 
    { 
      <Check that backward traversal works; bst => avl 118> 
    }

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

  return okay;
}

This code is included in 188, 332, 451, and 550.

193. <Check AVL tree structure 193> =
/* Recursively verify tree structure. */
size_t count;
int height;

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

This code is included in 192.

5.7 Copying

5 AVL Trees

6 Red-Black Trees