Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 10 M

Year: May 2015

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 guarentee a height of log(n) so that insertions and deletions always occour at O(log(n)).

Each node of an AVL tree can have a balanced factor of -1, 0 or +1 only.

If the balanced factor’s magniture exceeds 1after an operation such as insertion or deletion, then balancing is required. This is done with the help of rotations.