Explain AVL trees. Insert the following elements in AVL tree and also write the AVL conditions after each insertion. 64, 44, 26, 113, 109, 98, 75

1. AVL Trees:

AVL trees (named after their inventors Adelson, Velsky, and Landis) are self-balancing binary search trees that maintain a height balance condition. This condition ensures that the tree remains relatively balanced, even after insertions and deletions, and has a logarithmic time complexity for search, insertion, and deletion operations.

2. AVL Conditions:

An AVL tree must satisfy the following conditions:

• Balance Condition: For every node in the tree, the difference between the heights of its left and right subtrees must be at most one.
• Search Tree Property: The tree must also satisfy the standard search tree property, where the keys in the left subtree are less than the key in the root node, and the keys in the right subtree are greater than the key in the root node.

3. AVL Tree Insertion:

To insert a new element into an AVL tree, we follow these steps:

1. Insertion: Insert the new element into the tree using the standard binary search tree insertion algorithm.
2. Update Heights: Update the heights of the nodes along the path from the newly inserted node to the root.
3. Check Balance: Check the balance condition for each node along the path from the newly inserted node to the root.
4. Rebalance Tree: If the balance condition is violated at any node, perform a series of tree rotations to restore the balance.

4. AVL Tree Example:

Let's insert the elements 64, 44, 26, 113, 109, 98, and 75 into an AVL tree.

Insertion of 64:

• Insert 64 as the root node.
• The height of the root node is 1.
• The tree satisfies the AVL conditions.

Insertion of 44:

• Insert 44 as the left child of 64.
• Update the height of the left subtree of 64 to 1.
• Check the balance condition for 64.
• The balance condition is still satisfied (|left_height - right_height| = 1 - 0 ≤ 1).
• The tree still satisfies the AVL conditions.

Insertion of 26:

• Insert 26 as the left child of 44.
• Update the height of the left subtree of 44 to 1.
• Check the balance condition for 44.
• The balance condition is still satisfied (|left_height - right_height| = 1 - 0 ≤ 1).
• The tree still satisfies the AVL conditions.

Insertion of 113:

• Insert 113 as the right child of 64.
• Update the height of the right subtree of 64 to 1.
• Check the balance condition for 64.
• The balance condition is still satisfied (|left_height - right_height| = 1 - 1 = 0 ≤ 1).
• The tree still satisfies the AVL conditions.

Insertion of 109:

• Insert 109 as the right child of 113.
• Update the height of the right subtree of 113 to 1.
• Check the balance condition for 113.
• The balance condition is violated (|left_height - right_height| = 0 - 1 = -1 > -1).
• Perform a left rotation on 113 to restore the balance.
• The tree now satisfies the AVL conditions.

Insertion of 98:

• Insert 98 as the left child of 109.
• Update the height of the left subtree of 109 to 1.
• Check the balance condition for 109.
• The balance condition is satisfied (|left_height - right_height| = 1 - 0 ≤ 1).
• The tree still satisfies the AVL conditions.

Insertion of 75:

• Insert 75 as the right child of 44.
• Update the height of the right subtree of 44 to 1.
• Check the balance condition for 44.
• The balance condition is violated (|left_height - right_height| = 0 - 1 = -1 > -1).
• Perform a right rotation on 44 to restore the balance.
• The tree now satisfies the AVL conditions.

The final AVL tree is:

       64
      /   \
     44    113
    / \    /  \
   26  75  109  98

This tree satisfies both the AVL conditions and the search tree property.