Log In
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?

in DS 195 views

1 Answer

3 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.

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

Related questions

1 vote
2 answers
There is given a infix expression: ${\color{Red} {1}}$ $A+B\times C/\left ( \left ( D+E \right )+F\times G \right )$ While converting infix expression to postfix expression number of symbols in the stack at indicated ${\color{Red} {point-1}}$ infix expression (assume stack is initially empty) ______________ they told $5$, but is it correct? Can anyone give some explanation??
asked May 6, 2019 in DS srestha 385 views
0 votes
1 answer
Assume a Binary Search Tree is not allowed to have duplicates, there is more than one way to delete a node in the tree when the node has two children.If we resolve the situation in favor of choosing element for replacement from left substructure, then which ... too ?? If we resolve the situation in favor of choosing element for replacement from left substructure what this line exactly means?
asked Apr 30, 2019 in DS srestha 302 views
8 votes
5 answers
How it is 24? I'm not getting it.
asked Jan 7, 2017 in DS target2017 1.6k views
0 votes
0 answers
A stack based CPU executes the instruction. Memory location $500$ contain $0X 88$ and memory location $700$ contain $0X37$. The stack pointer is at $0X003F$ The instruction are as follows: $I_{1}:PUSH$ $500$ $I_{2}:PUSH$. $700$ $I_{3}:ADD$ $I_{4}:POP$ ... $0X88$ after execution of instruction. $C)$ Memory location $600$ contain $0XBF$ after execution of instruction. $D)$ Both $a)$ and $c)$
asked May 22, 2019 in DS srestha 293 views