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
| 119 views

+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