AVL

Introduction

Hello there, in the previous post I've talked about Binary Search Tree before. Some of you might've encountered a situation where when you input the first data with extreme value (too big or too small), the following leaves/nodes just get overweight at one side, probably looking like this.

100

/ 

50   

/  \   

45  60     

/             

30                

Actually, there's nothing wrong with it. But since one invented an innovation towards this, here we are, a self-balancing binary tree : AVL tree. Technically speaking, AVL tree is an self-balancing binary tree in which the difference of depth between left and right subtree cannot be more than one.

How does it work

So basically, everytime when we input a data, we check on the balance between the right and left sub trees, and perform rotation accordingly to realign [rebalance] them.

There are four kinds of unbalanced tree that happens in a binary tree :
- Left left tree = [rotate right]

- Left right tree = [rotate right]

- Right right tree = [rotate left]

- Right left tree = [rotate left]

All situation on above will then get resolved in AVL by a few left/right rotation.

Like this :

What to code

To keep this short, I'll just mention a few core function that make up the balancing feature of AVL.

First, of all : imagine we have a data packed in struct named node , you should know that it is compulsory for every node to have an attribute that represents their height in the tree. Le'ts pretend the Node holds an numeric value named value

 node=leftRotate(node);

Struct * leftRotate(Struct *node){

  Struct *rightNode = node->right;

  Struct *rightLeftNode = rightNode->left;

 

  rightNode->left = node;  

  node->right = rightLeftNode;  

//Note : since we reshuffled the node, we should rewrite the height attribute that implies their       sequence

    node -> height = (node->left->height - node->right->height) +1;

//Note : apply above function to either leftNode or  rightNode too [for this case (LeftRotate), leftNode (which was rightLeftNode before) doesn't have to be re-written because it's height value is the same as before]. 

//Note : if they don't have child node anymore, should just return 0 for child's height.

  

  return rightNode;

}

I do think that the implementation for rotateRight and the code for the condition to use rotation isnt quite hard. So i'll leave it for y'all to think. See you soon ;D