High School

We appreciate your visit to 1 Construct an AVL Tree for the following data 30 20 10 25 40 50 22 27 5 152 Perform Deletion of the following data. This page offers clear insights and highlights the essential aspects of the topic. Our goal is to provide a helpful and engaging learning experience. Explore the content and find the answers you need!

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.

Thanks for taking the time to read 1 Construct an AVL Tree for the following data 30 20 10 25 40 50 22 27 5 152 Perform Deletion of the following data. We hope the insights shared have been valuable and enhanced your understanding of the topic. Don�t hesitate to browse our website for more informative and engaging content!

Rewritten by : Barada