14.8 Testing

The testing code harbors no surprises.

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

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

551. <Compare two PAVL trees for structure and content 551> =
/* 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 (" Copied nodes differ:\n"
              "  a: %d, bal %+d, parent %d, %s left child, %s right child\n"
              "  b: %d, bal %+d, parent %d, %s left child, %s right child\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 550.

552. <Recursively verify PAVL tree structure 552> =
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;

  <Verify binary search tree ordering 115>

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

  <Verify AVL node balance factor; avl => pavl 191>

  <Verify PBST node parent pointers; pbst => pavl 520>
}

This code is included in 550.

14.7 Copying

14 AVL Trees with Parent Pointers

15 Red-Black Trees with Parent Pointers