# AVL-tree insertion complexity proof

I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how. I also tried to find it somewhere on the Internet, but I could not find any good results. Do you guys have any ideas how do we proof that?

• Take a look at Section 6.2.3 (Balanced Trees) in Volume III (Sorting and Searching) of "The Art of Computer Programming" by Donald Knuth. Feb 9, 2021 at 17:48
• We start by proving that if an AVL tree has a path of length $h$ then the tree has at least $2^{h/2}$ nodes, see this site AVL tree height log n proof. Feb 9, 2021 at 22:55
• At worst, an insertion could cause a rebalancing of every node it traverses, and this is bounded by the tree height. A balanced tree has a height $O(\log n)$.
– user16034
Mar 10, 2022 at 14:32

As an immediate consequence of this lemma, we can implement the dynamic-set operations SEARCH , MINIMUM , MAXIMUM , SUCCESSOR , and PREDECESSOR in $$O(\log n)$$ time on red-black trees, since each can run in $$O(h)$$ time on a binary search tree of height $$h$$ (as shown in Chapter 12) and any red-black tree on n nodes is a binary search tree with height $$O(\log n)$$.
Regarding a pure understanding of why the INSERTION is $$O(\log n)$$, check this implementation example. There you can clearly see that what makes an AVL differ from a standard BST are the rotations, that can be performed in constant time. With those you get a balanced tree, and with a balanced tree you get $$O(\log n)$$ INSERTION.
An insertion could at worse cause a rotation on every level, hence with complexity $$O(h)$$ where $$h$$ stands for the height.
Now thanks to balancing, $$h=O(\log n)$$.