The worst case time complexity of AVL tree is better in comparison to binary…

Concept — In a binary search tree every dictionary operation is carried out by walking a single comparison path between the root and one node, so the cost of an operation is governed by the height h of the tree rather than by the key count n on its own. A plain binary search tree puts no bound on that height: for n keys it may be as small as about log2n or as large as n − 1, because the shape depends entirely on the order in which the keys arrive. An AVL tree adds a balance invariant, namely that at every node the heights of the two subtrees differ by at most 1, and that invariant forces h ≤ 1.44 log2(n + 2) while an update is repaired by O(1) rebalancing work at each level of the path it disturbed.

Application — trace the keys 10, 20, 30, 40, 50, inserted in that order, through both structures.

1. Plain binary search tree: 10 becomes the root, 20 is larger so it becomes its right child, and 30, 40 and 50 each follow the whole existing path and hang off the rightmost node. The tree degenerates into a right chain of five nodes whose height is 4.

2. Searching that chain for 50 compares the target against 10, 20, 30, 40 and 50 in turn, one comparison per stored key, so a search costs Θ(n) time in the worst case.

3. Inserting 60 walks the same full chain before attaching the new leaf, so an insert also costs Θ(n) time in the worst case.

4. Deleting 50 must first locate it, and it sits at the far end of the chain, so a delete costs Θ(n) time in the worst case as well.

5. AVL tree with the same keys: after 10, 20, 30 the node 10 has a balance factor of −2 with the taller subtree on its right-right side, so one left rotation lifts 20 to the root. Adding 40 and 50 breaks the invariant once more and a second left rotation at 30 repairs it, leaving a tree of height 2.

6. Every root-to-node walk in that balanced tree is at most h ≤ 1.44 log2(n + 2) edges long. An insertion is repaired by a single rebalancing step — one single rotation for an LL or RR imbalance, one double rotation for an LR or RL one — while a deletion may need such a step at every ancestor up to the root, each costing O(1); so all three operations run in O(log n) time no matter what order the keys arrive in.

Cross-check — compare the worst case of each dictionary operation in the two structures.

Result — every one of the three dictionary operations falls from O(n) in the worst case to O(log n), so the worst-case gain of an AVL tree over a plain binary search tree covers search, insertion and deletion together. The gain is specifically a worst-case one: on a randomly built binary search tree the expected cost is already O(log n), and it is the adversarial insertion order that the AVL balance invariant defends against.