874 views
1 1 vote
Consider the following statements
I: The height of any binary search tree with n nodes is O(log n).
II : Inserting into an AVL tree with n nodes requires Θ(log n) rotations.
Which of the following statements is/are true ?

1 Answer

Best answer
4 4 votes

If a tree is left skewed or right skewed so in that case the height will be O(n) not O(logn).Hence statement 1 is false.

For insertion of a  node into an AVL tree, after insertion at most one problem can occur overall .So at most 2 rotations will be required (for LR or RL problem)..Hence statement 2 is also false.In case of deletion yes it is O(logn) 

Hence both of the statements are false.

• selected by
Position:
Show:

Related questions

1 1 vote
0 0 answers
406
406 views
ASUR asked Oct 31, 2025
406 views
In how many ways we can insert the elements {1, 2, . . . , 7} into an empty AVL tree so that we don‟t have to perform any rotations on it?
3 3 votes
1 answers 1 answer
3.6k
3.6k views
hrcule asked Jul 16, 2018
3,629 views
Let T be a binary search tree with n nodes and Sn be the average number of comparisons required for successful search and Un be the average number of comparison required ...
4 4 votes
0 0 answers
4.5k
4.5k views
AnilGoudar asked Jan 10, 2018
4,517 views
When node 50 will be deleted, what will be resultant AVL tree?
1 1 vote
0 0 answers
2.9k
2.9k views
atul_21 asked Jan 1, 2018
2,939 views
Can anyone please explain ?? What does R+1,L+1 or R+1,L-1 means ??