1
$\begingroup$

The worst case height of AVL tree is $1.44 \log n$. How do we prove that? I read somewhere about Fibonacci quicks but did not understand it.

$\endgroup$
  • 1
    $\begingroup$ Can you recall where you read about Fibonacci quick? Have you tried proving it by yourself? Please edit the question to show what research you have done and how much progrogress you have made. $\endgroup$ – Apass.Jack Mar 21 at 13:05
  • 1
    $\begingroup$ Possible duplicate of AVL trees are not weight-balanced?. Although the two questions are different, the answer to that question contains a nice explanation of the worst-case height of an AVL tree. $\endgroup$ – Apass.Jack Mar 21 at 18:18
0
$\begingroup$

Try and create the "worst" AVL tree, that is, the AVL tree in which the height is as large as possible, with as least nodes as possible.

Once you get to the Fibonacci sequence (the answer to the question above), you can use the fact the the $n$-th Fibonacci number is $O(\phi ^n)$ (where $\phi = 1.618\ldots$), it should be easy to conclude that the worst case height of the tree is $\log_\phi n = O(\log n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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