Weak AVL Tree Implementation 1

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

#define TOLERANCE  1

typedef struct _Node  Node;
struct _Node {
  struct _Node* left;
  struct _Node* right;
  int rank;
  int key;
};

int max (int a, int b)
{
  if (a > b)
    return a;
  else
    return b;
}

int rank (Node* node)
{
  if (!node)
    return 0;

  return node->rank;
}

void update (Node* h)
{
  h->rank = max (rank (h->left), rank (h->right)) + 1;
}

Node* left_rotate (Node* h)
{
    assert (h->left != nullptr);

    Node* x = h->left;
    h->left = x->right;
    x->right = h;

    update (h);
    update (x);

    return x;
}

Node* right_rotate (Node* h)
{
    assert (h->right != nullptr);

    Node* x = h->right;
    h->right = x->left;
    x->left = h;

    update (h);
    update (x);

    return x;
}

Node* query (Node* h, int key)
{
    if (h == nullptr)
        return nullptr;

    if (key < h->key)
        return query (h->left, key);
    else if (key > h->key)
        return query (h->right, key);
    else
        return h;
}

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

        h = left_rotate (h);
    }
    else
    {
      if ((rank(h->left) < rank(h->right)) &&
          ((rank(h->right) - rank(h->left)) > TOLERANCE))
      {
          if (rank(h->right->left) > rank(h->right->right))
              h->right = left_rotate (h->right);

          h = right_rotate (h);
      }
    }

    update (h);
    return h;
}

Node* node_new (int key)
{
  Node* node = calloc (1, sizeof (Node));
  node->key = key;
  update (node);
  return node;
}

void node_free (Node* node)
{
  if (!node)
    return;

  node_free (node->left);
  node_free (node->right);
  free (node);
}

Node* insert (Node* h, int key)
{
    if (h == nullptr)
        return node_new (key);

    if (key < h->key)
        h->left = insert (h->left, key);
    else if (key > h->key)
        h->right = insert (h->right, key);

    return balance (h);
}

#define C_VOIDP_TO_INT(p)  ((int) (intptr_t) (p))

void traverse (Node* node)
{
  if (!node)
    return;

  traverse (node->left);

  printf ("k:%d\t r:%d\n", node->key, node->rank);

  switch (C_VOIDP_TO_INT (node->key))
  {
    case 2:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 5:
      assert (C_VOIDP_TO_INT (node->rank) == 2);
      assert (node->left != nullptr);
      assert (C_VOIDP_TO_INT (node->left->key) == 2);
      assert (node->right == nullptr);
      break;
    case 9:
      assert (C_VOIDP_TO_INT (node->rank) == 4);
      assert (node->left != nullptr);
      assert (C_VOIDP_TO_INT (node->left->key) == 5);
      assert (node->right != nullptr);
      assert (C_VOIDP_TO_INT (node->right->key) == 13);
      break;
    case 11:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 13:
      assert (C_VOIDP_TO_INT (node->rank) == 3);
      assert (node->left != nullptr);
      assert (C_VOIDP_TO_INT (node->left->key) == 11);
      assert (node->right != nullptr);
      assert (C_VOIDP_TO_INT (node->right->key) == 20);
      break;
    case 18:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 20:
      assert (C_VOIDP_TO_INT (node->rank) == 2);
      assert (node->left != nullptr);
      assert (C_VOIDP_TO_INT (node->left->key) == 18);
      assert (node->right != nullptr);
      assert (C_VOIDP_TO_INT (node->right->key) == 23);
      break;
    case 23:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 25:
      assert (C_VOIDP_TO_INT (node->rank) == 5);
      assert (node->left != nullptr);
      assert (C_VOIDP_TO_INT (node->left->key) == 9);
      assert (node->right != nullptr);
      assert (C_VOIDP_TO_INT (node->right->key) == 33);
      break;
    case 29:
      assert (C_VOIDP_TO_INT (node->rank) == 2);
      assert (node->left == nullptr);
      assert (node->right != nullptr);
      assert (C_VOIDP_TO_INT (node->right->key) == 31);
      break;
    case 31:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 33:
      assert (C_VOIDP_TO_INT (node->rank) == 3);
      assert (node->left != nullptr);
      assert (C_VOIDP_TO_INT (node->left->key) == 29);
      assert (node->right != nullptr);
      assert (C_VOIDP_TO_INT (node->right->key) == 59);
      break;
    case 59:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    default:
      printf ("Programming ERROR: %d is not processed\n",
              C_VOIDP_TO_INT (node->key));
      abort ();
      break;
  }

  traverse (node->right);
}

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

  Node* node = nullptr;
  for (int i = 0; i < sizeof (numbers) / sizeof (numbers[0]); i++)
    node = insert (node, numbers[i]);

  traverse (node);
  node_free (node);

  return 0;
}