AVL Trees

August 22, 2019

Introduction to AVL Tree

  1. The search operation in a BST is efficient if heights of both the left and the right subtrees of any node are equal. However, frequent insertions and deletions tend to render a BST unbalanced.
  2. The efficiency of a search operation is considered model if the difference between the heights of the left and the right subtrees in a BST is at most one.Such a BST is known as an AVL Tree.
  3. AVL Tree stands for Adelson-Velskii and Landis.
  4. Here in the image given to us we can see that each node has a number over it’s head in brown.
  5. This number is the height of each node.
    • For example: The height of the the node ‘20′ is 0.
    • The height of the node ’35’ is ‘2’.
  6. This height is also known as Balancing factor. We will study it in detail in the next section.

Representation of an AVL Tree

  • For representing an AVL tree we require four fields-
    • One for data.
    • One for address of the right sub tree.
    • One for the address of the left sub tree.
    • An additional field for storing the balancing factor.
  • Taking the example above as reference, we can se that,
    • Data value = 30.
    • Height/ = 3.
    • Left child = 17.
    • Right child = 35.
  • The structure of a node of an AVL tree is as follows-
    • struct AVL ;
    • {
    •         struct AVL *left;
    •         int data;
    •         struct AVL *right;
    •         int bfact;
    • }
    •  
avl2
avl3

Operations in an AVL Tree

We can perform same operations on an AVL tree as other trees. But in this case, an additional factor, i.e, balancing factor comes into play which identifes if a given tree fall under the category of an AVL tree. Thus apart from the mainstream operations performed on the trees we have an additional operation known as Rotation. The rotation mechanism is used for the conservation of the conditions of an AVL Tree.

Thus to conclude we can say that the operations that can be performed on an AVL tree are:

  • Insertion.
  • Deletion.
  • Rotation.

AVL Tree and Balancing Factor

It is of utmost importance to understand the difference between Height and Balancing factor of an AVL Tree.

  • Height of an AVL tree is the distance of a particular node from the root of the tree.
  • Balancing Factor of an AVL tree is the difference between the height of the left subtree and the right subtree, which can only range between ‘0’ , ‘1’ and ‘-1’.
  • The balance factor for any AVL tree can be calculated by subtracting the height of the right subtree from the height of the left subtree, i.e ,

bfact = height(left_subtree) – height(right_subtree).

Balancing Factor

The values of the bfact of any node can be -1 , 0 or 1. If it is other than these three values, then the tree is not balanced or it is not an AVL tree. Thus ,

If bfact = 0, 

The height of the right subtree and the left subtree is exactly the same.

avl6

If bfact = -1,

The height of the right subtree of that node is one more than the height of it’s left sub tree.

If bfact = 1,

The height of the left subtree of that node is one more than the height of it’s right subtree.

avl8

Rotation in an AVL tree

  • The Rotation operation is performed when the AVL Tree becomes unbalanced due to any insertion or deletion operation on the tree.
  • The prime motive to use the rotation mechanism is to preserve the stated balancing factor, which is to checked for each node at each level.
  • The balancing factor must always lie between ‘0’ , ‘-1’ , ‘1’. If it is other than that either it is not balanced or is not an AVL tree.
  • There are four types of rotation:
    • LL Rotation.
    • RR Rotation.
    • LR Rotation.
    • RL Rotation.

1. LL – Rotation(Left Rotation)

This rotation is used when the new node has been inserted into right subtree and makes the tree unbalanced.

r1

2. RR – Rotation(Right Rotation)

This rotation is used when the new node is inserted to the left of left subtree and makes the tree unbalanced.

rotation

3. LR – Rotation(Left-Right Rotation)

This rotation is used when the new node is inserted to the right of left subtree and makes the tree unbalanced.

rotation

4. RL – Rotation(Right-Left Rotation)

This rotation is used when the new node is inserted to the left of the right subtree and makes the tree unbalanced.

rotation
Summary
Review Date
Author Rating
51star1star1star1star1star

2 comments on “AVL Trees”