The Gateway to Computer Science Excellence
0 votes
58 views

$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?

in DS by Veteran (119k points) | 58 views

1 Answer

+2 votes
Best answer

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.

by Loyal (5.9k points)
selected by
+1
Take example of binary heap which is a complete tree but not AVL there searching takes (n) time
0
yes , you're right

Related questions

+8 votes
5 answers
3
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,324 answers
198,405 comments
105,169 users