Construct AVL tree by inserting the following elements in the given order: 68,53,24,8,18,92,48,6,32,5,86,38,47,95

Q.) Construct AVL tree by inserting the following elements in the given order: 68,53,24,8,18,92,48,6,32,5,86,38,47,95

 Subject: Data Structures

To construct an AVL tree by inserting the given elements, we will follow the AVL tree insertion rules. An AVL tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Here are the steps we will follow for each insertion:

  1. Insert the element as you would in a regular binary search tree.
  2. After the insertion, check the balance factor of each node, which is the height of the left subtree minus the height of the right subtree. The balance factor must be -1, 0, or 1 for the tree to remain an AVL tree.
  3. If the balance factor of any node is not -1, 0, or 1, perform the appropriate rotation to balance the tree. There are four types of rotations:
    • Single Right Rotation (LL Rotation)
    • Single Left Rotation (RR Rotation)
    • Left-Right Rotation (LR Rotation)
    • Right-Left Rotation (RL Rotation)

Let's start inserting the elements one by one and balance the tree as needed:

  1. Insert 68:

    68
/  \
null null

    Balance factors: 68 (0)

  2. Insert 53:

    68
/  \
53  null

    Balance factors: 53 (0), 68 (-1)

  3. Insert 24:

    68
/  \
53  null
/
24

    Balance factors: 24 (0), 53 (1), 68 (-2) -> Unbalanced, requires rotation

Perform a single right rotation (LL Rotation) at 68:

   53
  /  \
 24   68

Balance factors: 24 (0), 53 (0), 68 (0)

  1. Insert 8:

    53
/  \
24   68
/
8

    Balance factors: 8 (0), 24 (1), 53 (1), 68 (0)

  2. Insert 18:

    53
/  \
24   68
/ \
8  18

    Balance factors: 8 (0), 18 (0), 24 (0), 53 (1), 68 (0)

  3. Insert 92:

    53
/  \
24   68
/ \    \
8  18   92

    Balance factors: 8 (0), 18 (0), 24 (0), 53 (0), 68 (-1), 92 (0)

  4. Insert 48:

    53
/  \
24   68
/ \    \
8  18   92
/
48

    Balance factors: 8 (0), 18 (1), 24 (1), 48 (0), 53 (0), 68 (-1), 92 (0)

  5. Insert 6:

    53
/  \
24   68
/ \    \
8  18   92
/   /
6  48

    Balance factors: 6 (0), 8 (-1), 18 (1), 24 (1), 48 (0), 53 (0), 68 (-1), 92 (0)

  6. Insert 32:

    53
/  \
24   68
/ \    \
8  18   92
/   / \
6  48 32

    Balance factors: 6 (0), 8 (-1), 18 (0), 24 (0), 32 (0), 48 (-1), 53 (0), 68 (-1), 92 (0)

  7. Insert 5:

    53
/  \
24   68
/ \    \
8  18   92
/   / \
5  48 32

    Balance factors: 5 (0), 6 (1), 8 (0), 18 (0), 24 (0), 32 (0), 48 (-1), 53 (0), 68 (-1), 92 (0)

  8. Insert 86:

    53
/  \
24   68
/ \    \
8  18   92
/   / \   /
5  48 32 86

    Balance factors: 5 (0), 6 (1), 8 (0), 18 (0), 24 (0), 32 (0), 48 (-1), 53 (0), 68 (0), 86 (0), 92 (-1)

  9. Insert 38:

    53
/  \
24   68
/ \    \
8  18   92
/   / \   /
5  48 32 86
 /
38

    Balance factors: 5 (0), 6 (1), 8 (0), 18 (0), 24 (1), 32 (1), 38 (0), 48 (1), 53 (0), 68 (0), 86 (0), 92 (-1)

  10. Insert 47:

    53
/  \
24   68
/ \    \
8  18   92
/   / \   /
5  48 32 86
 / \
38 47

    Balance factors: 5 (0), 6 (1), 8 (0), 18 (0), 24 (1), 32 (0), 38 (0), 47 (0), 48 (0), 53 (0), 68 (0), 86 (0), 92 (-1)

  11. Insert 95:

    53
/  \
24   68
/ \    \
8  18   92
/   / \   / \
5  48 32 86 95
 / \
38 47

    Balance factors: 5 (0), 6 (1), 8 (0), 18 (0), 24 (1), 32 (0), 38 (0), 47 (0), 48 (0), 53 (0), 68 (0), 86 (0), 92 (0), 95 (0)

After inserting all the elements, we have the following AVL tree:

   53
  /  \
 24   68
 / \    \
8  18   92
/   / \   / \
5  48 32 86 95
     / \
   38 47

All nodes have balance factors of -1, 0, or 1, so the tree is balanced and no further rotations are needed.