what is the height of avl tree with n nodes ? Can you explain it with formula ? I couldn't find any formula to solve this problem.


closed as unclear what you're asking by Evil, David Richerby, Rick Decker, Juho, hengxin Jun 8 '17 at 1:35

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ After fast search "avl n nodes height", the first result was wiki, and it is there, with an equation. Oh, also here $\endgroup$ – Evil May 30 '17 at 23:35
  • $\begingroup$ I couldn't find the exact result there, it is given as range. $\endgroup$ – ozdemir May 30 '17 at 23:40
  • $\begingroup$ Yes, because it depends on data added. The given range estimates the height and there cannot exist one exact equation. If this is not what you are looking for, well, if you have a particular tree the shape may vary with different insertions order, so either the range is your answer or given a tree the height should be calculated. Maybe try here to build some trees from the same elements? $\endgroup$ – Evil May 31 '17 at 0:44

AVL trees are self-balancing binary search trees (another example is red-black trees). By definition, a self-balancing binary tree maintains the property that its height is $\Theta(\log n)$, where $n$ is the number of leaves or vertices (the two properties corresponding to the two different definitions of $n$ are equivalent).

Usually it is costly to have a data-independent height, and so the height depends on the history of the data structure (it depends on the exact order in which values were inserted and deleted), but it is always $O(\log n)$. (Note that every binary tree has height $\Omega(\log n)$.)

  • $\begingroup$ While maximizing the height with given number of nodes in an AVL we can get some function related to fibbonacci(h) (may be fib(h+1)+1 but i don't remember exactly) related terms in which is approximately power of golden ratio so can we make the tighter using $log_{\phi}n$ $\endgroup$ – Deep Joshi May 31 '17 at 11:25

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