Weak AVL Tree Implementation 2

Thu, Aug 8 2024 23:17:43 KST

Weak AVL rule

  • Nil node has rank -1.
  • All leaf nodes have rank 0.
  • An internal node with two leaf nodes has rank 1.
  • The rank difference from the parent node is 1 or 2.

I modify what I previously wrote to conform to WAVL rules.

             25(4)
             / \
            /   \
           /     \
          /       \
         /         \
        9(3)        33(2)
       /\           / \
      /  \         /   \
     /    \       /     \
    5(1)  13(2)  29(1)  59(0)
   /     /  \      \
  /     /    \      \
 2(0)  11(0)  20(1)  31(0)
              / \
             /   \
           18(0)  23(0)

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

  return node->rank;
}

I modify the function name from update to update_rank to make it easier to understand.

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

I modify the check code to confirm the correct result.

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) == 0);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 5:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      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) == 3);
      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) == 0);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 13:
      assert (C_VOIDP_TO_INT (node->rank) == 2);
      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) == 0);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 20:
      assert (C_VOIDP_TO_INT (node->rank) == 1);
      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) == 0);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 25:
      assert (C_VOIDP_TO_INT (node->rank) == 4);
      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) == 1);
      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) == 0);
      assert (node->left == nullptr);
      assert (node->right == nullptr);
      break;
    case 33:
      assert (C_VOIDP_TO_INT (node->rank) == 2);
      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) == 0);
      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);
}

After recompiling and running it, I can see that the result is correct.

k:2	 r:0
k:5	 r:1
k:9	 r:3
k:11	 r:0
k:13	 r:2
k:18	 r:0
k:20	 r:1
k:23	 r:0
k:25	 r:4
k:29	 r:1
k:31	 r:0
k:33	 r:2
k:59	 r:0