Explain AVL Tree

Q.) Explain AVL Tree

 Subject: Data Structures

An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

AVL Tree Properties

  1. The tree must be a binary search tree (BST).
  2. The balance factor of each node is either -1, 0, or +1. The balance factor is calculated as the difference between the heights of the left and right subtrees.

Balance Factor Calculation

The balance factor of a node in an AVL tree is calculated as follows:

Balance Factor = Height of Left Subtree - Height of Right Subtree

AVL Tree Rotations

When the balance factor of a node in an AVL tree is not -1, 0, or +1, then the tree is unbalanced and requires rotation. There are four types of rotations:

  1. Left-Left Rotation (LL Rotation)
  2. Right-Right Rotation (RR Rotation)
  3. Left-Right Rotation (LR Rotation)
  4. Right-Left Rotation (RL Rotation)

Example of AVL Tree

Let's consider an example of an AVL tree:

      20
     /  \
   10   30
  /  \    \
 5   15   40

In this tree, the balance factor for each node is as follows:

  • Node 20: Balance Factor = (Height of Left Subtree - Height of Right Subtree) = (2 - 2) = 0
  • Node 10: Balance Factor = (Height of Left Subtree - Height of Right Subtree) = (1 - 1) = 0
  • Node 30: Balance Factor = (Height of Left Subtree - Height of Right Subtree) = (0 - 1) = -1
  • Node 5: Balance Factor = (Height of Left Subtree - Height of Right Subtree) = (0 - 0) = 0
  • Node 15: Balance Factor = (Height of Left Subtree - Height of Right Subtree) = (0 - 0) = 0
  • Node 40: Balance Factor = (Height of Left Subtree - Height of Right Subtree) = (0 - 0) = 0

Since the balance factor for all nodes is either -1, 0, or +1, this is a balanced AVL tree.

Summary

Property Description
Binary Search Tree AVL tree is a binary search tree
Balance Factor The balance factor of each node is either -1, 0, or +1
AVL Tree Rotations When the balance factor of a node is not -1, 0, or +1, then the tree is unbalanced and requires rotation
Time Complexity Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases