Introduction:
Searching in a binary search tree is efficient if the heights of both left and right sub-trees of any node are equal.
However, frequent insertions and deletions in a BST are likely to make it unbalanced.
The efficiency of searching is ideal if the difference between left and right sub-trees of all the nodes in a binary search tree is at the most one.
This is the basic approach of AVL trees.
It was invented by G.M. Adelson-Velskii and E.M. Landis ate 1962.
Explanation:
An AVL tree is a binary search tree which has the following properties:-
The sub-trees of every node differ in height by at most one.
Every sub-tree is an AVL tree.
Each node in the AVL Tree possesses any one of the following properties:
A node is called left heavy, if the largest path in its left sub tree is one level larger than the largest path of its right sub tree.
A node is called right heavy, if the largest path in its right sub tree is one level larger than the largest path of its left sub tree.
The node is called balanced, if the largest paths in both the right and left sub trees are equal.
Consider the following example of AVL tree where every left subtree has a height one greater than each right subtree.
Figure 1: AVL Tree
The motivation of AVL trees was to guarantee a height of log(n) so that insertions and deletions always occur at O(log(n)).
A balanced factor is an integer which is associated with each node of the tree. It indicates weather a tree is left-heavy (height of left subtree is greater than that of right subtree), balanced (both subtress are of the same height), or right-heavy(opposite of left-heavy).
Balance factor of a node = height othe left subtree - the height of the right subtree
Each node of an AVL tree can have a balanced factor of -1, 0 or +1 only.
If the balanced factor’s magnitude exceeds 1after an operation such as insertion or deletion, then balancing is required.
This is done with the help of rotations.
and 4 others joined a min ago.
teamques10
★ 69k