AVL Tree-
- AVL trees are special kind of binary search trees.
- In AVL trees, height of left subtree and right subtree of every node differs by at most one.
- AVL trees are also called as self-balancing binary search trees.
Example-
Following tree is an example of AVL tree-
![AVL Tree Example](https://www.gatevidyalay.com/wp-content/uploads/2018/08/AVL-Tree-Example.png)
This tree is an AVL tree because-
- It is a binary search tree.
- The difference between height of left subtree and right subtree of every node is at most one.
Following tree is not an example of AVL Tree-
![Not An AVL Tree](https://www.gatevidyalay.com/wp-content/uploads/2018/08/Not-An-AVL-Tree.png)
AVL Tree Operations-
Like BST Operation commonly performed operations on AVL tree are-
- Search Operation
- Insertion Operation
- Deletion Operation
Case-01:
- After the operation, the balance factor of each node is either 0 or 1 or -1.
- In this case, the AVL tree is considered to be balanced.
- The operation is concluded.
Case-02:
- After the operation, the balance factor of at least one node is not 0 or 1 or -1.
- In this case, the AVL tree is considered to be imbalanced.
- Rotations are then performed to balance the tree.
AVL Tree Rotations-
Kinds of Rotations-
There are 4 kinds of rotations possible in AVL Trees-
- Left Rotation (LL Rotation)
- Right Rotation (RR Rotation)
- Left-Right Rotation (LR Rotation)
- Right-Left Rotation (RL Rotation)
Cases Of Imbalance And Their Balancing Using Rotation Operations-
Case-01:
![AVL Tree Rotations | Case-1](https://www.gatevidyalay.com/wp-content/uploads/2018/08/AVL-Tree-Rotations-Case-1.png)
Case-02:
![AVL Tree Rotations | Case-2](https://www.gatevidyalay.com/wp-content/uploads/2018/08/AVL-Tree-Rotations-Case-2.png)
Case-03:
![AVL Tree Rotations | Case-3](https://www.gatevidyalay.com/wp-content/uploads/2018/08/AVL-Tree-Rotations-Case-3.png)
Case-04:
![AVL Tree Rotations | Case-4](https://www.gatevidyalay.com/wp-content/uploads/2018/08/AVL-Tree-Rotations-Case-4.png)
0 टिप्पणियाँ:
Post a Comment