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$
3
  • $\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
    Commented May 30, 2017 at 23:35
  • $\begingroup$ I couldn't find the exact result there, it is given as range. $\endgroup$
    – ozdemir
    Commented May 30, 2017 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
    Commented May 31, 2017 at 0:44

1 Answer 1

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

$\endgroup$
1
  • $\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
    Commented May 31, 2017 at 11:25

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