Applied Course | Mock GATE | Test 1 | Question: 34

Question

Which of the following statements is/are TRUE?

1. Suppose there are $n$ nodes are present in a binary search tree. The height of any binary search tree is $\theta (\log n)$
2. $\theta (\log n)$ rotations are required to insert into AVL tree with n nodes.

 

• A. Only I
• B. Only II
• C. Both I and II
• D. Neither I nor II

Answer 1

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)$.