8,025 views
2 votes
2 votes

What is the worst case possible height of an AVL tree??

a.   2logn  (Assume base of log is 2) 

 b. 1.44log n  (Assume base of log is 2)

c. Depends upon implementation

d. Theta(n)

1 Answer

Best answer
4 votes
4 votes

What is the minimum number of nodes (sparsest possible AVL tree) an AVL tree of height h can have ?

| Fh| = | Fh - 1| + | Fh - 2| + 1
| Fh| + 1 = (| Fh - 1| + 1) + (| Fh - 2| + 1)
| Fh| + 1 $\displaystyle \approx$ $\displaystyle {\frac{1}{\sqrt{5}}}$ $\displaystyle \left(\vphantom{\frac{1+\sqrt{5}}{2}}\right.$ $\displaystyle {\frac{1+\sqrt{5}}{2}}$ $\displaystyle \left.\vphantom{\frac{1+\sqrt{5}}{2}}\right)^{h+3}_{}$
$ \Rightarrow$
$h  \approx 1.44 \log| Fn|$
$ \Rightarrow$
The sparsest possible AVL tree with n nodes has height 
$$h \displaystyle \approx 1.44\log n$$
$ \Rightarrow$
The worst case height of an AVL tree with n nodes is
$$1.44\log n$$
B is the correct answer
selected by

Related questions

4 votes
4 votes
1 answer
2
Manu Thakur asked Jul 27, 2017
6,897 views
What is the max possible height of an AVL tree with 20 nodes?a. 4b.5c.6d.7 In my opinion answer should be b.5 because height of a tree with 1 node is 0 not 1, and recurre...
1 votes
1 votes
1 answer
3
neha singh asked May 2, 2016
12,088 views
1 votes
1 votes
0 answers
4
Rohit Gupta 8 asked Dec 25, 2017
1,110 views
If the average depth of a node in an $n$-node binary search tree is $O(\log{n})$, then the height of the tree is$O(n\log{n})$$O(n)$$O(\log{n})$$O(\sqrt(n\log{n}))$