ISRO2020-20

Question

The minimum height of an AVL tree with $n$ nodes is

• A. $\text{Ceil } (\log_2(n+1))$
• B. $1.44\ \log_2n$
• C. $\text{Floor } (\log_2(n+1))$
• D. $1.64\ \log_2n$

Comments

https://www.geeksforgeeks.org/practice-questions-height-balancedavl-tree/

acoording to this option c match

 

Answer 1

$\underline{\textbf{Answer:}\Rightarrow}\;\textbf{(c)}$

$\text{Minimum height} =\color{magenta}{\mathbf{\bigg\lfloor  \log_2 \left ( n + 1  \right  )\bigg \rfloor}}$

$\text{Maximum height} =\color{blue}{\mathbf{1.44\log_2n}}$

Comments

What about 1.44logn?

---

It is maxheight 

1.44log(3)=1.44*2=2.88=floor(2.88)=1(if indexing starts from 0)

If indexing starts from 1 than max height should be 2.than we have to take floor(1.44log(n))+1. 

Actually I referred this link.https://www.geeksforgeeks.org/practice-questions-height-balancedavl-tree/

---

actually the unnecessarily added $+1$ for trying to make the answer different from the standard  $\log \mathbf n$ and failed miserably to justify now. :D

Answer 2

If there are n nodes in AVL tree, minimum height of AVL tree is floor(log2n). Option C

Explanation : Please refer the link below

https://www.geeksforgeeks.org/practice-questions-height-balancedavl-tree/

Comments

For $7$ nodes, minimum height = $2$.

Options B and D give fractional heights. So, they’re wrong.

Options A and C give $3$.

 

So, the question assumes the root to be at height $1$.

Rewriting: For $7$ nodes, maximum height = $3$.

For $6$ nodes, it will still be $3$.

 

Only Option A satisfies this.

 

The answer is also Option A in the official answer key.

---

Edit: Meant to comment on the question, lol. Not on this answer.

Answer 3

As we know there are minimum of 4 node in height 2 in avo tree because minimum height is h(no of node-1) and h(no of node -2)

So putting n=4 in all option we will obtain h=2 in floor(log2(n+1))