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

AVL Tree Explanation

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. AVL trees are named after their inventors, Adelson-Velsky and Landis.

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 considered unbalanced and requires rebalancing.

The balance factor (BF) can be calculated as follows:

[ BF(node) = Height(RightSubtree) - Height(LeftSubtree) ]

AVL Tree Insertion

When inserting a new element into an AVL tree, we first insert it as we would in a regular binary search tree. After the insertion, we check the balance factors of all nodes starting from the newly inserted node up to the root. If we find a node that is unbalanced, we perform one of the four types of rotations to balance the tree:

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

Inserting Elements Step by Step

Let's insert the elements 48, 25, 10, 5, 7, 3, 28, 20, 8, 16 into an AVL tree, one by one, and balance the tree as necessary.

Insert 48

Start with an empty tree. Insert 48.

    48
   /  \
null  null

Balance Factor for all nodes: 0 (Tree is balanced)

Insert 25

Insert 25 to the left of 48.

    48
   /  \
 25   null

Balance Factor for all nodes: 0 (Tree is balanced)

Insert 10

Insert 10 to the left of 25.

    48
   /  \
 25   null
 /
10

Balance Factor for nodes:

• 10: 0
• 25: -1 (left-heavy)
• 48: -2 (unbalanced)

Perform a single right rotation (LL Rotation) at 48.

    25
   /  \
 10   48

Balance Factor for all nodes: 0 (Tree is balanced)

Insert 5

Insert 5 to the left of 10.

    25
   /  \
 10   48
 /
5

Balance Factor for nodes:

• 5: 0
• 10: -1 (left-heavy)
• 25: -1 (left-heavy)
• 48: 0

Tree is still balanced.

Insert 7

Insert 7 between 5 and 10.

    25
   /  \
 10   48
 /
5
 \
  7

Balance Factor for nodes:

• 5: -1 (left-heavy)
• 7: 0
• 10: 0
• 25: -1 (left-heavy)
• 48: 0

Tree is still balanced.

Insert 3

Insert 3 to the left of 5.

    25
   /  \
 10   48
 /
5
/ \
3  7

Balance Factor for nodes:

• 3: 0
• 5: -1 (left-heavy)
• 7: 0
• 10: -1 (left-heavy)
• 25: -2 (unbalanced)
• 48: 0

Perform a single right rotation (LL Rotation) at 25.

    10
   /  \
  5   25
 / \    \
3   7   48

Balance Factor for all nodes: 0 (Tree is balanced)

Insert 28

Insert 28 to the right of 25.

    10
   /  \
  5   25
 / \    \
3   7   48
        /
      28

Balance Factor for nodes:

• 3: 0
• 5: 0
• 7: 0
• 10: 0
• 25: -1 (left-heavy)
• 28: 0
• 48: 1 (right-heavy)

Tree is still balanced.

Insert 20

Insert 20 to the left of 25.

    10
   /  \
  5   25
 / \  /  \
3   7 20  48
          /
        28

Balance Factor for nodes:

• 3: 0
• 5: 0
• 7: 0
• 10: 0
• 20: 0
• 25: 0
• 28: 0
• 48: 1 (right-heavy)

Tree is still balanced.

Insert 8

Insert 8 between 7 and 10.

    10
   /  \
  5   25
 / \  /  \
3   7 20  48
     \    /
      8  28

Balance Factor for nodes:

• 3: 0
• 5: -1 (left-heavy)
• 7: 1 (right-heavy)
• 8: 0
• 10: 0
• 20: 0
• 25: 0
• 28: 0
• 48: 1 (right-heavy)

Tree is still balanced.

Insert 16

Insert 16 between 10 and 20.

    10
   /  \
  5   25
 / \  /  \
3   7 20  48
     \ /   /
      8 16 28

Balance Factor for nodes:

• 3: 0
• 5: -1 (left-heavy)
• 7: 1 (right-heavy)
• 8: 0
• 10: 1 (right-heavy)
• 16: 0
• 20: 1 (right-heavy)
• 25: 1 (right-heavy)
• 28: 0
• 48: 1 (right-heavy)

Now, the tree is unbalanced at node 10, which has a balance factor of +2.

Perform a left-right rotation (LR Rotation) at 10. This involves a single left rotation at 5 followed by a single right rotation at 10.

After the left rotation at 5:

    10
   /  \
  7   25
 / \  /  \
3   5 20  48
   /  /   /
  8 16   28

After the right rotation at 10:

     7
   /   \
  5    10
 / \   /  \
3   8 20   25
       /    \
      16    48
            /
          28

Balance Factor for all nodes: 0 (Tree is balanced)

The final AVL tree after all insertions and necessary rotations is balanced and maintains the AVL property.