13.8 Testing

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

<BST print function; bst => pbst 120>
<BST traverser check function; bst => pbst 105>
<Compare two PBSTs for structure and content 518>
<Recursively verify PBST structure 519>
<BST verify function; bst => pbst 110>
<TBST test function; tbst => pbst 297>
<BST overflow test function; bst => pbst 123>

518. <Compare two PBSTs for structure and content 518> =
static int 
compare_trees (struct pbst_node *a, struct pbst_node *b) 
{
  int okay;

  if (a == NULL || b == NULL) 
    {
      assert (a == NULL && b == NULL);
      return 1;
    }

  if (*(int *) a->pbst_data != *(int *) b->pbst_data
      || ((a->pbst_link[0] != NULL) != (b->pbst_link[0] != NULL))
      || ((a->pbst_link[1] != NULL) != (b->pbst_link[1] != NULL))
      || ((a->pbst_parent != NULL) != (b->pbst_parent != NULL))
      || (a->pbst_parent != NULL && b->pbst_parent != NULL
          && a->pbst_parent->pbst_data != b->pbst_parent->pbst_data)) 
    {
      printf (" Copied nodes differ:\n"
              "  a: %d, parent %d, %s left child, %s right child\n"
              "  b: %d, parent %d, %s left child, %s right child\n",
              *(int *) a->pbst_data,
              a->pbst_parent != NULL ? *(int *) a->pbst_parent : -1,
              a->pbst_link[0] != NULL ? "has" : "no",
              a->pbst_link[1] != NULL ? "has" : "no",
              *(int *) b->pbst_data,
              b->pbst_parent != NULL ? *(int *) b->pbst_parent : -1,
              b->pbst_link[0] != NULL ? "has" : "no",
              b->pbst_link[1] != NULL ? "has" : "no");
      return 0;
    }

  okay = 1;
  if (a->pbst_link[0] != NULL)
    okay &= compare_trees (a->pbst_link[0], b->pbst_link[0]);
  if (a->pbst_link[1] != NULL)
    okay &= compare_trees (a->pbst_link[1], b->pbst_link[1]);
  return okay;
}

This code is included in 517.

519. <Recursively verify PBST structure 519> =
static void 
recurse_verify_tree (struct pbst_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. */
  int i;

  if (node == NULL) 
    {
      *count = 0;
      return;
    }
  d = *(int *) node->pbst_data;

  <Verify binary search tree ordering 115>

  recurse_verify_tree (node->pbst_link[0], okay, &subcount[0], min, d - 1);
  recurse_verify_tree (node->pbst_link[1], okay, &subcount[1], d + 1, max);
  *count = 1 + subcount[0] + subcount[1];

  <Verify PBST node parent pointers 520>
}

This code is included in 517.

520. <Verify PBST node parent pointers 520> =
for (i = 0; i < 2; i++) 
  {
    if (node->pbst_link[i] != NULL 
        && node->pbst_link[i]->pbst_parent != node) 
      {
        printf (" Node %d has parent %d (should be %d).\n",
                *(int *) node->pbst_link[i]->pbst_data,
                (node->pbst_link[i]->pbst_parent != NULL
                 ? *(int *) node->pbst_link[i]->pbst_parent->pbst_data : -1),
                d);
        *okay = 0;
      }
  }

This code is included in 519, 552, and 587.

13.7 Balance

13 BSTs with Parent Pointers

14 AVL Trees with Parent Pointers