Weak AVL Tree Implementation 4

Fri, Aug 9 2024 18:42:12 KST

Simplification of the `balance` function

I remove #define TOLERANCE 1 and simplify the balance function.

The balance function has the following code:

 ((rank(h->left) > rank(h->right)) &&
  ((rank(h->left) - rank(h->right)) > 1))

The above code can be simplified as follows:

l > r &&
l - r > 1

l - r > r - r &&
l - r > 1

l - r > 0 &&
l - r > 1

l - r > 1

So the rewritten balance function is:

Node* balance (Node* h)
{
  if ((rank(h->left) - rank(h->right) > 1))
  {
    if (rank(h->left->right) > rank(h->left->left))
      h->left = right_rotate (h->left);

    h = left_rotate (h);
  }
  else
  {
    if ((rank(h->right) - rank(h->left) > 1))
    {
      if (rank(h->right->left) > rank(h->right->right))
        h->right = left_rotate (h->right);

      h = right_rotate (h);
    }
  }

  update_rank (h);
  return h;
}

Verification

Even if the input data is the same, the shape of the tree can change if the input order changes. Therefore, we need a code to verify whether the tree is a Weak AVL tree. This alone is not enough. We also need to check whether n outputs are generated when n different data are input. To check this, we create an int size variable.

typedef struct _Tree  Tree;
struct _Tree {
  Node* root;
  int size;
};

Tree* tree_new ()
{
  Tree* tree = malloc (sizeof (Tree));
  tree->root = nullptr;
  tree->size = 0;
  return tree;
}

We modify insert function to increase size when inserting a node.

void tree_insert (Tree* tree, int key)
{
  tree->root = insert (tree, tree->root, key);
}

Node* insert (Tree* tree, Node* h, int key)
{
  if (h == nullptr)
  {
    tree->size++;
    return node_new (key);
  }

  if (key < h->key)
    h->left = insert (tree, h->left, key);
  else if (key > h->key)
    h->right = insert (tree, h->right, key);
  else // On a hit, size is not increased and the balance function is not performed.
    return h;

  return balance (h);
}

I decided to modify the traverse function to a verify function.

void verify (Node* node, int* count)
{
  if (!node)
    return;

  verify (node->left, count);

  if (node->left)
    printf ("%d(%d)\t", node->left->key,  node->left->rank);
  else
    printf (" \t");

  printf ("%d(%d)", node->key, node->rank);

  if (node->right)
    printf ("\t%d(%d)", node->right->key, node->right->rank);
  else
    printf ("\t");

  puts ("");

  // All leaf nodes have rank 0.
  if (!node->left && !node->right)
    assert (node->rank == 0);

  if (node->left && node->right && // An internal node
      !node->left->left && !node->left->right &&
      !node->right->left && !node->right->right) //  with two leaf nodes
    assert (node->rank == 1);  // has rank 1.

  // The rank difference from the parent node is 1 or 2.
  int diff;
  diff = abs (rank(node) - rank(node->left));
  assert (diff == 1 || diff == 2);
  diff = abs (rank(node) - rank(node->right));
  assert (diff == 1 || diff == 2);

  (*count)++;

  verify (node->right, count);
}

void tree_verify (Tree* tree, int size)
{
  int count = 0;
  verify (tree->root, &count);
  assert (tree->size == size);
  assert (tree->size == count);
}

int main ()
{
  int numbers[] = {
    29, 13, 23, 59, 25, 20,  5,  9, 33,  2, 31, 18, 11, 37,  7, 98,
    // duplicate keys
    31,  2, 13, 25,  9, 18, 37, 29, 23, 98, 20, 59,  5,  7, 11, 33
  };

  Tree* tree = tree_new ();

  for (int i = 0; i < sizeof (numbers) / sizeof (numbers[0]); i++)
    tree_insert (tree, numbers[i]);

  tree_verify (tree, 16);
  tree_free (tree);

  return 0;
}

Weak AVL Tree Implementation 4

Simplification of the balance function

Verification

Simplification of the `balance` function