Register

#Test_series

468 views
1 votes
1 votes
 

The height h of an AVL tree with n nodes lies in the interval:

1.

log2(n+1) ≤ h < c log2(n+2)+b

 

2.

log10(n) ≤ h < c log10(n+1)+b

 

3.

log10(n+1) ≤ h < c log10(n+2)+b

 

4.

log2(n) ≤ h < c log2(n+1)+b
User Avatar

1 Answer

0 votes
0 votes
ANS 1

the max no of node of given hight h is 2^(h+1)-1 for BT or BST or AVL tree that is equal to the min hight  h of tree for given these many nodes 2^(h+1)-1.

now let take node 2^(h+1)-1=n   where n is no of node in tree

2^(h+1)=n+1

take log both side

h+1=log(n+1) base 2

h=log(n+1) base 2 -1  we get lower bound
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
1 answer
1
himgta asked Apr 21, 2018
328 views
#test_series
Find the output of the c program below, assume base address of the array is 1500. The size of int is 4 bytes
Find the output of the c program below, assume base address of the array is 1500. The size of int is 4 bytes
User Avatar
0 votes
0 votes
0 answers
2
himgta asked Apr 30, 2018
403 views
#Test_Series
Consider the below given C code: Void main() { int x=5,y=2; int *p; p=&x; y=*p; x=*y; printf("y is %d x is %d\n",y,x); } Choose the correct option: A) The following program has 1 lexical error, 1 syntax error. B) The following program has 1 lexical error only. C) The following program has 1 lexical error, 1 semantic error. D) No error
Consider the below given C code:Void main(){int x=5,y=2;int *p;p=&x;y=*p;x=*y;printf("y is %d x is %d\n",y,x);}Choose the correct option:A) The following program has 1 le...
User Avatar
2 votes
2 votes
2 answers
3
himgta asked Apr 30, 2018
872 views
#Test_Series
Consider implementation of stack using queue by following algorithm. Let $x$ be an element to be pushed in the stack push(q1,x) { EQ(q1,x) while(q1 does not contain 1 element) { k=DQ(q1) EQ(q1,k) } } pop(q1) { DQ(q1) } How many enqueue and dequeue operations required to push $2$ and pop $2$ elements in the empty stack?
Consider implementation of stack using queue by following algorithm.Let $x$ be an element to be pushed in the stackpush(q1,x) { EQ(q1,x) while(q1 does not contain 1 eleme...
User Avatar
3 votes
3 votes
1 answer
4
tapzo asked Jan 17, 2018
401 views
#test_series
let L be a set of binary string whose integer equivalent is congruent to 10 (mod 16) Then minimal DFA that accept L contains how many states ? plz explain
let L be a set of binary string whose integer equivalent is congruent to 10 (mod 16) Then minimal DFA that accept L contains how many states ? plz explain
User Avatar
Link Copied!