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 11.9k 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 Arjun commented Nov 27, 2016 reply Follow Share In an AVL tree sometimes search can succeed in first or second try. So, it should be $O(\log n)$ and not $\Theta(\log n)$ rt? 52 votes 52 votes MANSINGH HANSDA commented Nov 27, 2016 reply Follow Share 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) . 2 votes 2 votes Chhotu commented Aug 2, 2017 reply Follow Share Q. -> In an AVL tree sometimes search can succeed in first or second try. So, it should be O(logn) and not Θ(logn) rt? Ans. -> Yes, You are correct. Thanks for your careful observation. Refer -> https://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent 17 votes 17 votes VIDYADHAR SHELKE 1 commented Nov 9, 2018 reply Follow Share For complete binary tree/Full binary tree insertion,deletion,searching =O(n)...right? 3 votes 3 votes Kiyoshi commented Apr 24, 2021 i edited by Kiyoshi Aug 26, 2021 reply Follow Share In an AVL tree sometimes search can succeed in first or second try. So, it should be O(logn) and not Θ(logn) rt? can anybody explain how?? I am not getting this... Look at the option (A) in the question itself. It is given Θ(logn) which is true option.. PS : Got it now... 0 votes 0 votes 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.