Types of Trees : 4_Adel'son-Vel'skii and Landis(AVL) Trees

 

AVL trees, named after G. M. Adelson-Velskii and E. M. Landis were invented in 1962. The definition of an AVL tree is as follows. First, we define the balance factor of a node to be the absolute difference in heights of its left subtree and right subtree. For example, a given node with a left subtree of height 4 and right subtree of height 7 will have a balance factor of 3. We define an AVL tree to be a tree such that the balance factor of each node is less or equal to 1.

In height-balanced HB(k), if k = 1 (if balance factor is one), such a binary search tree is called an AVL tree. That means an AVL tree is a binary search tree with a balance condition: the difference between left subtree height and right subtree height is at most 1.Properties of AVL Trees

A binary tree is said to be an AVL tree, if:

•  It is a binary search tree
•  For any node X, the height of the left subtree of X and the height of the right subtree of X differ by at most 1.

As an example, among the above binary search trees, the left one is not an AVL tree, whereas the right binary search tree is an AVL tree.

ADDITIONAL PROPERTY:

The difference between the depth of right and left subtrees cannot be more than one. In order to maintain this guarantee, and implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee.AVL trees have a worst-case lookup, insert and delete time of O(log n).

Binary searching is efficient, but the binary search tree does not guarantee a short search. We want a height-balanced tree, this type of structure will guarantee a short search. We enforce the height-balanced property: For every internal node b of, the heights of the children differ by at most 1. A binary search tree which also satisfies the height-balanced property is called an AVL tree, Adel'son-Vel'skii and Landis. AVL trees keep the height small and guarantee O(log n) searches, after performing every operation like insertion and deletion we need to check the balance factor of every node in the tree.

ROTATIONS:

Single Left Rotation (LL Rotation): In LL Rotation every node moves one position to left from the current position.

Single Right Rotation (RR Rotation): In RR Rotation every node moves one position to right from the current position.

Left Right Rotation (LR Rotation) The LR Rotation is a combination of single left rotation followed by a single right rotation. In LR Rotation, first every node moves one position to left then one position to the right from the current position

Right Left Rotation (RL Rotation) The RL Rotation is a combination of single right rotation followed by a single left rotation. In RL Rotation, first every node moves one position to right then one position to the left from the current position.

TIME COMPLEXITY ANALYSIS:

AVL tree is a binary search tree with an additional property that the difference between the height of the left subtree and right sub-tree of any node can’t be more than 1. Algorithm Average Worst case: Space: O(n), Time: O(n).

APPLICATION:

AVL trees are beneficial in cases where you are designing some database where insertions and deletions are not that frequent but you have to frequently lookup for the items present in there.

NOTE:

AVL trees are good data structures to maintain an “almost” balanced tree. However, AVL trees are no longer used in practice. For the most part, practical applications use other types of trees, in particular, “Splay Trees”. Splay trees maintain access to most frequently accessed elements by bringing them closer to the root.