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?

  • $\begingroup$ 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. $\endgroup$
    – Steven
    Feb 9, 2021 at 17:48
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 9, 2021 at 22:55
  • $\begingroup$ 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)$. $\endgroup$
    – user16034
    Mar 10, 2022 at 14:32

2 Answers 2


Interesting question. For a better theoretical understanding of the whole theory I would suggest you to re-read "Introduction to Algorithms, Third Edition, Cormen" Chapter 12 (Trees) and Chapter 13 (Red-Black Trees). Since it is stated there that (page 311):

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)$.

Red-Black trees do not differ from AVL-trees from a strict computational point of view: https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/. An AVL tree is a subset of a Red-Black tree: http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948. So from a theoretical point of view, you can map them together (computational-complexity wise).

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.