GATE IT 2008 | Question: 12

Question

Which of the following is TRUE?

• A. The cost of searching an AVL tree is $\Theta (\log n)$ but that of a binary search tree is $O(n)$
• B. The cost of searching an AVL tree is $\Theta (\log n)$ but that of a complete binary tree is $\Theta (n \log n)$
• C. The cost of searching a binary search tree is $O (\log n )$ but that of an AVL tree is $\Theta(n)$
• D. The cost of searching an AVL tree is $\Theta (n \log n)$ but that of a binary search tree is $O(n)$

Comments

What would be the cost of searching an element in the complete binary tree (considering the worst case) ??(like how can we modify option B to be correct?)

---

@Chaithu555 for searching cost in CBT will be O(n) in worst case u've to traverse all the nodes . 

---

Since AVL is self balancing and it's balance factor is either -1, 0 or 1 it can never be skewed but BST can if all values are sorted. Therefore AVL search is "logn" and BST search is "n"

---

@Tushar Rana Is there any type of binary tree whose worst-case search exceeds O(n) ? i think no 

---

@js__ Yes it's obvious that when you take the worst case just become a linear thing that is an array. So it is just the number of elements, now apply linear search on it, and it's evident that we can't/ do not need more than n-1 comparisons and it will be O(n), also we can say it in theta terms as max cap is n so theta can be used. You have used O(n) that means at most but since you are considering the worst case like the ultimate case therefore it's better to use theta that is "equal to".

---

AVL IS SELF BALANCING SO EVEN THOUGH THE BEST AND AVG CASE ARE SAME FOR BST AND AVL TREE IN WORST CASE BST BECOMES O(n) due to skewed trees while incase of AVL trees due to the balancing factor the skewed case does not exist where all elements are either in left or right subtree alone so worst case for AVL tree is STILL logn only!

Answer 1

A) is true as AVL tree is a balanced search tree that has time complexity of searching $\Theta ( \log n)$, but in binary search tree, we can have a completely left/right skewed tree, in which search is $O(n)$.

Comments

Proof that AVL tree is always of height O(log n):-

If $n(h)$ is the minimum number of internal nodes of an AVL tree of height $h$.

We know that $n(h) = 1 + n(h-1) + n(h-2)$; $n(0) = 1, n(1) = 2$

Also, $n(h-1) > n(h-2)$

$\implies n(h) > 2n(h-2). $

So $n(h) > 2n(h-2)$

$ n(h) > 4n(h-4)$,

$n(h) > 8n(n-6)$ … ,

$n(h) > 2^i n(h-2i)$

Solving the base case we get: $n(h) > 2 ^{h/2-1}$

Taking logarithms: $h < 2.log n(h) +2$

$\implies h = O(log (n))$

 

Good read: AVLTrees.pdf (uci.edu)

---

@ASNR1010 how did u get it can u plz explain it to me also ?

---

@shikhar500, I think what he meant was in some cases, the search might finish earlier than the worst-case scenario. So it's best to use O(n) insead of theta(n). Please correct me if I'm wrong.

Answer 2

option A is right

Answer 3

AVL trees guarantee height Θ(log⁡n)\Theta(\log n)Θ(logn), so search is Θ(log⁡n)\Theta(\log n)Θ(logn). A BST can be skewed with height Θ(n)\Theta(n)Θ(n), so worst-case search is O(n)O(n)O(n).

Answer 4

(A) The cost of searching in AVL Tree is O(log n) because the height of AVL Tree is ⌈log n⌉ and The cost of searching in Binary Search Tree is O(n) because in worst case BST can be left/right Skewed , So we have to traverse all nodes for searching
So, Option(A) is correct

For Complete Binary Tree cost of serching is O(n) there is no ordering. So, for searching an element we have to traverse all nodes