in DS edited by
5,667 views
5 votes
5 votes

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

  1. $\text{Ceil } (\log_2(n+1))$
  2. $1.44\ \log_2n$
  3. $\text{Floor } (\log_2(n+1))$
  4. $1.64\ \log_2n$
in DS edited by
by
5.7k views

1 comment

1
1

3 Answers

3 votes
3 votes
$\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}}$
edited by
by

4 Comments

What about 1.44logn?
0
0

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/

0
0
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
0
0
0 votes
0 votes

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/

1 comment

edited by

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.

2
2
0 votes
0 votes
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))
by
Answer:

Related questions