32 votes 32 votes Which of the following is TRUE? The cost of searching an AVL tree is $\Theta (\log n)$ but that of a binary search tree is $O(n)$ The cost of searching an AVL tree is $\Theta (\log n)$ but that of a complete binary tree is $\Theta (n \log n)$ The cost of searching a binary search tree is $O (\log n )$ but that of an AVL tree is $\Theta(n)$ The cost of searching an AVL tree is $\Theta (n \log n)$ but that of a binary search tree is $O(n)$ DS gateit-2008 data-structures binary-search-tree easy avl-tree + – Ishrat Jahan asked Oct 27, 2014 • edited Dec 21, 2017 by kenzou Ishrat Jahan 12.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply Chaithu555 commented Feb 4 reply Follow Share 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?) 2 votes 2 votes Please log in or register to add a comment.
Best answer 45 votes 45 votes 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)$. Happy Mittal answered Oct 28, 2014 • edited Dec 21, 2017 by kenzou Happy Mittal comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Pranavpurkar commented Aug 5, 2021 reply Follow Share @mansingh hansda if we find the maximum height with minimum no of nodes then the height H = n/2 , without violating the property of the AVL tree . Then the cost of searching in AVL tree could be O(n/2) . Not always necessary to be Log(n) . But in AVL tree the max difference possible between the ht of right and left subtrees is |1| so we cannot construct a left or right skewed tree so how can the height be (n/2) in any case? 0 votes 0 votes Abhrajyoti00 commented Nov 2, 2022 reply Follow Share 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) 1 votes 1 votes shikhar500 commented Dec 14, 2022 reply Follow Share @ASNR1010 how did u get it can u plz explain it to me also ? 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes option A is right RAJESHWAR YADAV answered Nov 27, 2016 RAJESHWAR YADAV comment Share Follow See all 0 reply Please log in or register to add a comment.