540 views
0 votes
0 votes

$A)$ Rotation operation of AVL tree always preserves the inorder numbering.

$B)$ If every node of BST has either $0$ or $2$ children , then searching time is $O(log n)$

Which statement is correct?


Given $A)$ is correct but $B)$ is not. Plz explain how?

1 Answer

Best answer
3 votes
3 votes

A. Rotation in AVL trees , keeps the AVL tree still a binary search tree , thus the inorder numbering doesn't change .

B. Let's come to the second statement , the description given is of a full binary tree.

Now if we imagine a  full binary tree , 

In binary search tree , we know that time to search is $O(h)$ , where $h$ is the height of the binary tree.

Let's calculate the height in this case of full binary tree,

Total number of nodes = $n = 1+2+2+2+.... h$ times (2 nodes at each level) = $1+2h$.

$1+2h=n => h=\frac{n-1}{2}$ .

Thus in this case , time to search = $O(h) = O(\frac{n-1}{2}) = O(n).$

Thus the statement is false.

selected by

Related questions

0 votes
0 votes
0 answers
3
Overflow04 asked Oct 2, 2022
297 views
Not able to understand the last option.
9 votes
9 votes
5 answers
4
target2017 asked Jan 7, 2017
2,959 views
How it is 24? I'm not getting it.