Grokking Algorithms, Second Edition

Appendix A. Performance of AVL trees

This appendix discusses the performance of AVL trees, which were introduced in chapter 8. You will need to read that chapter before reading this.

Remember that AVL trees offer O(log n) search performance. But there is something misleading going on. Here are two trees. Both offer O(log n) search performance, but their heights are different!

(Dashed nodes show the holes in the tree.)

AVL trees allow a difference of one in heights. That’s why, even though both these trees have 15 nodes, the perfectly balanced ...