11.7 Testing

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

<RTBST print function; rtbst => rtavl 414>
<BST traverser check function; bst => rtavl 105>
<Compare two RTAVL trees for structure and content 452>
<Recursively verify RTAVL tree structure 453>
<AVL tree verify function; avl => rtavl 192>
<BST test function; bst => rtavl 101>
<BST overflow test function; bst => rtavl 123>

452. <Compare two RTAVL trees for structure and content 452> =
static int 
compare_trees (struct rtavl_node *a, struct rtavl_node *b) 
{
  int okay;

  if (a == NULL || b == NULL) 
    {
      if (a != NULL || b != NULL) 
        {
          printf (" a=%d b=%d\n",
                  a ? *(int *) a->rtavl_data : -1, 
                  b ? *(int *) b->rtavl_data : -1);
          assert (0);
        }
      return 1;
    }
  assert (a != b);

  if (*(int *) a->rtavl_data != *(int *) b->rtavl_data
      || a->rtavl_rtag != b->rtavl_rtag 
      || a->rtavl_balance != b->rtavl_balance) 
    {
      printf (" Copied nodes differ: a=%d (bal=%d) b=%d (bal=%d) a:",
              *(int *) a->rtavl_data, a->rtavl_balance,
              *(int *) b->rtavl_data, b->rtavl_balance);

      if (a->rtavl_rtag == RTAVL_CHILD) 
        printf ("r");

      printf (" b:");
      if (b->rtavl_rtag == RTAVL_CHILD) 
        printf ("r");

      printf ("\n");
      return 0;
    }

  if (a->rtavl_rtag == RTAVL_THREAD)
    assert ((a->rtavl_link[1] == NULL) != (a->rtavl_link[1] != b->rtavl_link[1]));

  okay = compare_trees (a->rtavl_link[0], b->rtavl_link[0]);
  if (a->rtavl_rtag == RTAVL_CHILD)
    okay &= compare_trees (a->rtavl_link[1], b->rtavl_link[1]);
  return okay;
}

This code is included in 451.

453. <Recursively verify RTAVL tree structure 453> =
static void 
recurse_verify_tree (struct rtavl_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->rtavl_data;

  <Verify binary search tree ordering 115>

  subcount[0] = subcount[1] = 0;
  subheight[0] = subheight[1] = 0;
  recurse_verify_tree (node->rtavl_link[0], okay, &subcount[0], 
                       min, d -  1, &subheight[0]);
  if (node->rtavl_rtag == RTAVL_CHILD)
    recurse_verify_tree (node->rtavl_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 => rtavl 191>
}

This code is included in 451.

11.6 Copying

11 Right-Threaded AVL Trees

12 Right-Threaded Red-Black Trees