AVL Trees in Data Structures

AVL Trees

One of the more popular balanced trees, known as an AVL tree in Data Structures, was introduced in 1962 by Adelson-Velski and Landis

Definition:

An empty binary search tree is an AVL tree. If T is a non empty binary search tree with T2 and TR as its left and right sub trees, The T is an AVL tree iff.

  • T2 and TR are AVL trees and
  • | hL – hR | < =1 where hL and hR are the heights of TL and T respectively

                                                                Or

An Avl trees is a binary search tree in which for every node in the tree, The height of the left and right Sub trees differ by at most1.

64

 

 

hL – hR =1

This is AVL Tree

 

65

 

 

hL – hR =2

This is not AVL Tree

66

 

 

 

This is also a AVL tree

hL = Height of left sub tree =2

|hl – hR |=|2-3|=|-

1|=1

| hL –hR| <=1

 

 

The difference between heights at left sub tree and right sub tree is called balancing Factor of a node.

 

Importance of Rotations :

  • The insert and delete operations of AVL tree are the same as binary search tree (BST)
  • Since an insertion(deletion) involve adding (deleting) a tree node, this can only increase (decrease) the heights of same sub tree(s) by 1
  • Thus, the AVL tree property may be violated
  • If the AVL tree property is violated ata node x, it means that the height of left(x) and right(x) differ by exactly 2
  • After the insertion or deletion operations, we need to examine the tree and see if any node violates the AVL tree property
  • If the AVL tree property is violated at node so, single or double rotation will be applied to x to restore the AVL tree property.
  • Rotation will be applied in a bottom up manner starting at the place of insertion(deletion)
  • Thus when we perform a rotation at x, The AVL tree property is restored at all proper descendants of x.

This fact is important.

 

Single Rotations :

RR rotation :- [ Right – Right Rotation]

67

68

 

69

 

 

 Double Rotations :

70

 

LR Rotaion  c Left Right Rotation :

 

71

 

 

    Ex : Example of RL Rotation :

72

 

 

Ex: Example of LR Rotation:

 

72

 

Example:

Construct an AVL tree with the following elements

3,2,1,4,5,6,716,15,14

72

72

72

 

 

Insertion :

  • Trace from path of inserted leaf towards the root, and check if the AVL tree property is violated perform rotation if necessary
  • For insertion, once we perform (Single or doubles) rotation at a node x, The AVL tree property is already restored. We need not to perform any rotation at any ancestor of X.
  • Thus one rotation is enough to restore the AVL tree properly
  • There are 4 different cases (actually 2) , so don’t mix up them
  • The time complexity to perform rotation is 0(1)
  • The time completely to insert, and find a node that violates the AVL property is dependent on the height of the tree, which is 0(log(n))
  • So insertion takes o(log(n))

 

Deletion :

  • Delete a node X as in ordinary BST(Note that X is either a leaf or X has exactly one child)
  • Check and restore the AVL tree property.
  • Trace from path of deleted node towards the root and check if the AVL tree property is violated
  • Similar to an insertion operation, there are four cases to restore the AVL tree property.
  • The only difference from insertion is that after we perform a rotation at x, we may have to perform, a rotation at some ancestors of x, It may involve several rotations.
  • Therefore, we must continue to trace the path until we reach the root.
  • The time complexity to delete a node is dependent on the height of the tree, which is also o(log(n))