High School

1. Construct an AVL Tree for the following data:
30, 20, 10, 25, 40, 50, 22, 27, 5, 15

2. Perform Deletion of the following data from the AVL tree of Ques-1:
20, 40, 15, 25

Answer :

To construct an AVL Tree, which is a self-balancing binary search tree, you need to insert the given numbers one by one, ensuring that after each insertion, the tree remains balanced. Here's how it can be done with the provided data:

Insertion:

  1. Insert 30:

    • Tree: 30

  2. Insert 20:

    • Tree: 30
      /
      20

  3. Insert 10:

    • This insertion causes the tree to become unbalanced (Left-Left Case).
    • Perform Right Rotation around 30.
    • Tree: 20
      / \
      10 30

  4. Insert 25:

    • Tree: 20
      / \
      10 30
      /
      25

  5. Insert 40:

    • Tree: 20
      / \
      10 30
      / \
      25 40

  6. Insert 50:

    • Tree becomes unbalanced after insertion (Right-Right Case).
    • Perform Left Rotation around 30.
    • Tree: 20
      / \
      10 40
      / \
      30 50
      /
      25

  7. Insert 22:

    • Tree: 20
      / \
      10 40
      / \
      30 50
      /
      25
      \
      22

  8. Insert 27:

    • Tree becomes unbalanced by this insertion (Left-Right Case at 30).
    • Perform Left Rotation around 25, then Right Rotation around 30.
    • Tree: 20
      / \
      10 40
      / \
      27 50
      /
      25
      / \
      22 30

  9. Insert 5:

    • Tree: 20
      / \
      10 40
      / / \

    5 27 50
    /
    25
    /
    22 30

  10. Insert 15:

    • Tree becomes unbalanced at 10 after this insertion (Right-Left Case).
    • Perform Right Rotation around 10.
    • Tree: 20
      / \
      15 40
      / \ / \
      10 5 27 50
      /
      25
      / \
      22 30

Deletion:

Now, let's perform deletions in the order provided:

  1. Delete 20:

    • 20 is replaced by its successor from the right subtree (22).
    • Tree becomes: 22
      / \
      15 40
      / \ / \
      5 10 27 50
      /
      25
      \
      30

  2. Delete 40:

    • 40 is replaced by its successor (50).
    • Tree: 22
      / \
      15 50
      / \ /
      5 10 27
      /
      25
      \
      30

  3. Delete 15:

    • 15 is replaced by its successor (10).
    • Tree: 22
      / \
      10 50
      / /
      5 27
      /
      25
      \
      30

  4. Delete 25:

    • 25 is replaced by its successor (27).
    • Tree: 22
      / \
      10 50
      /
      5 27
      \
      30

At each step when the AVL tree is modified, rotations (left or right) are performed to ensure that the tree is balanced, maintaining the AVL property where the difference between heights of left and right subtrees for any node is no more than one.

Other Questions