The AVL Tree was invented in 1962 by GM Adelson – Velsky and EM Landis. In honour of its inventors, the tree was given the name AVL. The AVL Tree is a height balanced binary search tree in which each node’s balancing factor is calculate to subtracting the right subtree’s height from the left subtree’s height.
The tree is said to balanced if the balance factor of each node is between -1 and 1; otherwise, the tree is unbalanced and must be balanced.
Balance Factor (k) = height (left(k)) – height (right(k))
- If the balance factor of any node is 1, it means that the left sub-tree is one level higher than the right subtree.
- Next, If the balance factor of any node is 0, it means that the left subtree and right subtree contain equal height.
- If the balance factor of any node is -1, it means that the left sub-tree is one level lower than the right subtree.
Why AVL Tree?
The height of the binary search tree is control the AVL tree, which prevents it from becoming skewed. In a binary search tree of height h, the total time taken for all operations is O. (h). If the BST becomes skewed, it can extended to O(n) (i.e. worst case). The AVL tree imposes an upper bound on each operation of O(log n), where n is the number of nodes, by limiting the height to log n.
AVL Rotations
Only when the Balance Factor is greater than -1, 0, or 1 do we rotate the AVL tree. Rotations could divided into four categories, as follows:
- L L rotation: The inserted node is located in the left subtree of A’s left subtree.
- R R rotation: The node that insert is in the right subtree of A’s right subtree.
- L R rotation: The inserted node is in the left subtree of A’s right subtree.
- R L rotation: The inserted node is in A’s right subtree’s left subtree.
Complexity
| Algorithm | Average case | Worst case |
| Space | o(n) | o(n) |
| Search | o(log n) | o(log n) |
| Insert | o(log n) | o(log n) |
| Delete | o(log n) | o(log n) |
Interested in learning about similar topics? Here are a few hand-picked blogs for you!
- What is single source shortest path?
- Describe binary search tree?
- What is semaphore?
- Explain DBMS?
- What is constructor?