0
$\begingroup$

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.

$\endgroup$
  • $\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
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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.