Explain AVL tree insert method and explain why its insertion time complexity is still of the order of a binary tree.

Q.) Explain AVL tree insert method and explain why its insertion time complexity is still of the order of a binary tree.

 Subject: Data Structures - II

An AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. If at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

AVL Tree Insertion

The insertion operation in an AVL tree is performed as follows:

  1. Standard BST Insert: Like all other Binary Search Trees, an AVL tree maintains the property of Binary Search Tree (BST) that the value of a node is greater than all values on its left and less than all values on its right. So, the first step in AVL tree insertion is to perform a normal BST insertion.

  2. Update Height: After standard BST insertion, we update the height of the current node.

  3. Get the Balance Factor: Next, we get the balance factor of the current node (height of left subtree – height of right subtree) and check for imbalance.

  4. Balance the Tree: If the balance factor is greater than 1, then the current node is unbalanced and we are either in Left-Left case or Left-Right case. To check whether it is Left-Left case or not, compare the newly inserted key with the key in left subtree root. Similarly, if balance factor is less than -1, then the current node is unbalanced and we are either in Right-Right case or Right-Left case. To check whether it is Right-Right case or not, compare the newly inserted key with the key in right subtree root.

  5. Left-Left and Right-Right Cases (Single Rotation): If it is Left-Left case (i.e., the newly inserted key is less than the key in left subtree root), then a single right rotate is needed. On the other hand, if it is Right-Right case (i.e., the newly inserted key is greater than the key in right subtree root), then a single left rotate is needed.

  6. Left-Right and Right-Left Cases (Double Rotation): If it is Left-Right case (i.e., the newly inserted key is greater than the key in left subtree root), then a double rotation (first left rotate, then right rotate) is needed. On the other hand, if it is Right-Left case (i.e., the newly inserted key is less than the key in right subtree root), then a double rotation (first right rotate, then left rotate) is needed.

Time Complexity of AVL Tree Insertion

The time complexity of AVL tree insert operation is still O(log n), same as that of a binary search tree. Here's why:

  • The BST insert operation itself takes O(log n) time. This is because you're essentially traversing down the tree from root to leaf, and the maximum number of nodes you'll traverse is equal to the height of the tree, which is log n for a balanced binary search tree.

  • After the insert operation, you need to update the height of the ancestors of the inserted node and check each of them for imbalance (i.e., whether the balance factor is greater than 1 or less than -1). This again takes O(log n) time because there are log n ancestors of a node in a binary search tree.

  • Finally, you may need to perform a single or double rotation to balance the tree. This operation takes constant time, i.e., O(1).

Therefore, the overall time complexity of the AVL tree insert operation is O(log n) + O(log n) + O(1), which is O(log n). This is the same as the time complexity of the insert operation in a binary search tree.