AVL Tree is a balanced binary search tree.(balanced BST).
Balanced binary tree means
mod (Height(left subtree) – Height(right subtree) ) <= 1
This is called balance factor.
A node is said to be left burdened when height of left subtree > height of right subtree
A node is said to be right burdened when height of right subtree > height of left subtree
————————————————————————————————————————
While performing insert/delete operations on the AVL tree , it may get imbalanced.So we need to rebalance it by either a left rotation/right rotation/both at the imbalanced node.
When node in an AVL tree becomes imbalanced then one of the below 4 cases arise.Let 20 be the imbalanced node in each case.
- LL case
L——>The imbalanced node is left burdened.
L ——>We go to the left of the imbalanced node(left child) and this node is also left burdened.
Solution : Perform right rotation at imbalanced node.
- LR case
L——>The imbalanced node is left burdened.
R——>We go to the left of the imbalanced node(left child) and this node is right burdened.
Solution : Perform left rotation at left child of imbalanced node.Then perform right rotation at imbalanced node.So we perform rotation twice.
- RR case
R——>The imbalanced node is right burdened.
R ——>We go to the right of the imbalanced node(right child) and this node is also right burdened.
Solution : Perform left rotation at imbalanced node.
- RL case
R——>The imbalanced node is right burdened.
L——>We go to the right of the imbalanced node(right child) and this node is left burdened.
Solution : Perform right rotation at right child of imbalanced node.Then perform left rotation at imbalanced node.So we perform rotation twice.
So when we insert/delete a key,we identify the imbalanced node/s and identify the case that the imbalanced node falls in i.e (LL,LR,RR,RL) and we have a solution(rotation/s) for each of these cases as discussed above.So the imbalanced node is rebalanced.
No comments:
Post a Comment