The Gateway to Computer Science Excellence
+2 votes
119 views
Which of the following statements is/are TRUE?
I. Suppose there are $n$ nodes are present in a binary search tree. The height of any binary search tree is $\theta (\log n)$
II. $\theta (\log n)$ rotations are required to insert into AVL tree with n nodes.
  1. Only I
  2. Only II
  3. Both I and II
  4. Neither I nor II
in Unknown Category by Junior | 119 views

1 Answer

+1 vote
I. False. In the best case, the height of a BST is $O(\log n)$ if it is balanced. In the worst case, however, it can be $\theta(n)$.
II. False. There were two ways you can show this.
1. There are cases where inserting into an AVL tree requires no rotation $\theta (\log n)$ rotations implies $\Omega (\log n)$ rotations. Since we have insertions that require no rotations, this means that inserting into an AVL tree does not require $\Omega (\log n)$ rotations and thus it does not require $\theta ( \log n)$ rotations.
2. Inserting into an AVL tree may look at $O( \log n)$ nodes, but it only needs to perform at most $2$ rotations to fix the imbalance. Thus inserting into an AVL tree requires $O(1)$ rotations, which is not $\theta (\log n)$.
by Junior
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
52,222 questions
59,853 answers
201,033 comments
118,095 users