Write Short notes on AVL Tree
An AVL tree is a height balance tree. These trees are binary search trees in which the
heights of two siblings are not permitted to differ by more than one.
Searching time in a binary search tree is O(h) where h is the height of the tree. For
efficient searching it is necessary that the height should be kept minimum.
A full binary search tree with n nodes will have a height of O(log n). In practice, it is
very difficult to control the height of a BST. It lies between O(n) to O(log n). An AVL tree is
a close approximation of full binary search tree.
The balance factor of a node in a AVL tree could be -1, 0 or 1.
1. 0 indicates that the left and right subtrees are equal.
2. +1 means the height of the left subtree is one more than the height of the right
3. -1 indicates that the height of the right subtree is one more than the height of the left
Explore more Questions in Data Structure