Construct AVL tree by inserting the following elements in the given order. निम्न तत्वों को दिए गए क्रम में सम्मिलित करके AVL वृक्ष का निर्माण करें. 68,53,24,18,92,8,47,95

Q.) Construct AVL tree by inserting the following elements in the given order. निम्न तत्वों को दिए गए क्रम में सम्मिलित करके AVL वृक्ष का निर्माण करें. 68,53,24,18,92,8,47,95

 Subject: Data Structures

To construct an AVL tree by inserting the given elements, we will follow these steps:

  1. Insert elements one by one.
  2. After each insertion, check the balance factor of each node.
  3. If the balance factor of any node is not in the range of -1, 0, or 1, perform the appropriate rotation to balance the tree.

The balance factor of a node in an AVL tree is defined as the height of its left subtree minus the height of its right subtree. The balance factor can be -1, 0, or 1 for a balanced AVL tree.

Let's start constructing the AVL tree with the given elements: 68, 53, 24, 18, 92, 8, 47, 95.

Step 1: Insert 68

    68
   /  \
null  null

Balance factor of 68 = height(left subtree) - height(right subtree) = 0 - 0 = 0

Step 2: Insert 53

    68
   /  \
  53  null
 /  \
null null

Balance factors:

  • 53: 0 - 0 = 0
  • 68: 1 - 0 = 1

Step 3: Insert 24

    68
   /  \
  53  null
 /  \
24  null

Balance factors:

  • 24: 0 - 0 = 0
  • 53: 1 - 0 = 1
  • 68: 2 - 0 = 2 (Unbalanced, requires rotation)

Perform a right rotation on 68:

    53
   /  \
  24   68

Balance factors after rotation:

  • 24: 0 - 0 = 0
  • 53: 1 - 1 = 0
  • 68: 0 - 0 = 0

Step 4: Insert 18

    53
   /  \
  24   68
 /  \
18  null

Balance factors:

  • 18: 0 - 0 = 0
  • 24: 1 - 0 = 1
  • 53: 2 - 1 = 1
  • 68: 0 - 0 = 0

Step 5: Insert 92

    53
   /  \
  24   68
 /  \    \
18  null  92

Balance factors:

  • 18: 0 - 0 = 0
  • 24: 1 - 0 = 1
  • 68: 0 - 1 = -1
  • 92: 0 - 0 = 0
  • 53: 2 - 2 = 0

Step 6: Insert 8

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

Balance factors:

  • 8: 0 - 0 = 0
  • 18: 1 - 0 = 1
  • 24: 2 - 0 = 2 (Unbalanced, requires rotation)
  • 68: 0 - 1 = -1
  • 92: 0 - 0 = 0
  • 53: 3 - 2 = 1

Perform a left rotation on 24:

    53
   /  \
  18   68
 /  \    \
8   24   92

Balance factors after rotation:

  • 8: 0 - 0 = 0
  • 18: 1 - 1 = 0
  • 24: 0 - 0 = 0
  • 68: 0 - 1 = -1
  • 92: 0 - 0 = 0
  • 53: 2 - 2 = 0

Step 7: Insert 47

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

Balance factors:

  • 8: 0 - 0 = 0
  • 18: 1 - 1 = 0
  • 24: 0 - 1 = -1
  • 47: 0 - 0 = 0
  • 68: 0 - 1 = -1
  • 92: 0 - 0 = 0
  • 53: 2 - 2 = 0

Step 8: Insert 95

    53
   /  \
  18   68
 /  \    \
8   24   92
      \    \
      47   95

Balance factors:

  • 8: 0 - 0 = 0
  • 18: 1 - 1 = 0
  • 24: 0 - 1 = -1
  • 47: 0 - 0 = 0
  • 68: 0 - 2 = -2 (Unbalanced, requires rotation)
  • 92: 0 - 1 = -1
  • 95: 0 - 0 = 0
  • 53: 2 - 3 = -1

Perform a left rotation on 68:

    53
   /  \
  18   92
 /  \  /  \
8   24 68  95
      \
      47

Balance factors after rotation:

  • 8: 0 - 0 = 0
  • 18: 1 - 1 = 0
  • 24: 0 - 1 = -1
  • 47: 0 - 0 = 0
  • 68: 0 - 0 = 0
  • 92: 1 - 1 = 0
  • 95: 0 - 0 = 0
  • 53: 2 - 2 = 0

The final AVL tree is balanced with all nodes having balance factors of -1, 0, or 1.