Explain AVL tree. Insert the following elements in AVL tree: 48 25 10 5 73 28 20 8 16

Q.) Explain AVL tree. Insert the following elements in AVL tree: 48 25 10 5 73 28 20 8 16

 Subject: Data Structures

Explanation of AVL Tree

An AVL tree 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. This balance condition ensures that the tree remains approximately balanced, which guarantees O(log n) time complexity for key operations such as search, insert, and delete.

The balance factor of a node in an AVL tree is the height of its right subtree minus the height of its left subtree. A node with a balance factor of +1, 0, or -1 is considered balanced. A node with a balance factor of +2 or -2 is unbalanced and requires rebalancing.

The rebalancing is done through rotations. There are four types of rotations:

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

Insertion in AVL Tree

To insert a new element into an AVL tree, we follow these steps:

  1. Perform the regular BST insertion.
  2. The new insertion might have caused the tree to become unbalanced. Starting from the newly inserted node, travel up to the root and find the first unbalanced node.
  3. Determine what kind of rotation will balance the tree:
    • If the balance factor of the unbalanced node is greater than 1 and the key of the newly inserted node is less than the key of the left child of the unbalanced node, perform a right rotation (LL Rotation).
    • If the balance factor of the unbalanced node is less than -1 and the key of the newly inserted node is greater than the key of the right child of the unbalanced node, perform a left rotation (RR Rotation).
    • If the balance factor of the unbalanced node is greater than 1 and the key of the newly inserted node is greater than the key of the left child of the unbalanced node, perform a left-right rotation (LR Rotation).
    • If the balance factor of the unbalanced node is less than -1 and the key of the newly inserted node is less than the key of the right child of the unbalanced node, perform a right-left rotation (RL Rotation).

Now, let's insert the given elements into an AVL tree step by step:

Elements to insert: 48 25 10 5 73 28 20 8 16

Step 1: Insert 48

    48
   /  \
null null

Balance factor of 48 is 0, so the tree is balanced.

Step 2: Insert 25

    48
   /  \
  25  null

Balance factor of 48 is +1, so the tree is balanced.

Step 3: Insert 10

    48
   /  \
  25  null
 /
10

Balance factor of 25 is +1, and balance factor of 48 is +2 (unbalanced). We need to perform a right rotation (LL Rotation) at 48.

After rotation:

    25
   /  \
  10   48

Step 4: Insert 5

    25
   /  \
  10   48
 /
5

Balance factor of 10 is +1, balance factor of 25 is +1, and the tree is balanced.

Step 5: Insert 73

    25
   /  \
  10   48
 /      \
5       73

Balance factor of 48 is -1, balance factor of 25 is 0, and the tree is balanced.

Step 6: Insert 28

    25
   /  \
  10   48
 /      \
5       73
       /
     28

Balance factor of 48 is -2 (unbalanced), and the balance factor of 73 is +1. We need to perform a right-left rotation (RL Rotation) at 48.

After rotation:

    25
   /  \
  10   28
 /    /  \
5    48  73

Step 7: Insert 20

    25
   /  \
  10   28
 /    /  \
5    48  73
 \
 20

Balance factor of 10 is -1, balance factor of 25 is 0, and the tree is balanced.

Step 8: Insert 8

    25
   /  \
  10   28
 /    /  \
5    48  73
 \   /
 20 8

Balance factor of 10 is -2 (unbalanced), and the balance factor of 5 is +1. We need to perform a left-right rotation (LR Rotation) at 10.

After rotation:

    25
   /  \
  8    28
 / \   /  \
5  10 48  73
    \
    20

Step 9: Insert 16

    25
   /  \
  8    28
 / \   /  \
5  10 48  73
    \
    20
     \
     16

Balance factor of 20 is -1, balance factor of 10 is -2 (unbalanced). We need to perform a left rotation (RR Rotation) at 10.

After rotation:

    25
   /  \
  8    28
 / \   /  \
5  20 48  73
   / \
 10  16

After the final insertion and rebalancing, the balance factors of all nodes are either -1, 0, or +1, which means the tree is balanced. This is the final AVL tree after inserting all the elements.