AVL Tree is a tree
where each of the root node does not have an imbalance between height of right
and left sub tree
- Minimal difference of 1 between height of left and right sub tree for each node.
- THE FORMULA |Hr-Hl| <=1
- Height of a tree is the length from longest leave to it's root.
- For each node always count for imbalances after adding a new node.
- The edge of the leave starts from 0
- Visual Representation
How do you make a
imbalanced tree into a AVL Tree
- Use 4 type of rotation to fix their position
- LL ROTATION
- LR ROTATION
- RR ROTATION
- RL ROTATION
- THE rotation should be applied to only 3 nodes no matter how big the tree.
- The rotation should be done after every adding a new node and finding a height imbalance.
- How to Pick The Right node to rotate?
- Find the newly inserted node
- Go up through that node parents
- The first parents you find that's imbalance becomes "THE" node
- After you find "THE" node trace the step from that node to the newly added node
- Only take the first 2 step out of it to rotate for ex: RLLR only take RL
- Rotate the 3 node that has been trace according to the shape (RR, RL, LL, LR)
- Reconnect all the nodes that have been move
- If there exist a sub-node that collides with another sub node due to the position changed then insert it again using the BST rule.
