Searching in a balanced binary search tree

Question

I was reading about balanced binary search tree. I found this statement about searching in such tree:

It is not true that when you are looking for something in a balanced binary search tree with n elements, it can in worst case needed n/2 comparisons.

Why it is not true?

Isn't it that we look either to the right side or the left side of the tree so the comparisons should be n/2?

Answer 1

The search worst case of Balanced Binary Search tree is governed by its height. It is O(height) where the height is log2(n) since it is balanced.

In worst case, the node that we looking for resides in a leaf or doesn't exist at all, and hence we need to traverse the tree from the root to its leafs which is O(lgn) and not O(n/2)

Answer 2

Imagine the tree with 10 nodes: 1,2,3,4,5..10. If you are looking for 5, how many comparisons would it take? How about if you look for 10? It's actually never N/2.

Answer 3

The worst case scenario is that the element you are searching for is a leaf (or isn't contained in a tree), and the number of comparisons then is equal to tree height which is log2(n).

Answer 4

Consider the following balanced binary tree for n=7 (this is in fact a complete binary search tree, but lets leave that out of this discussion, as a complete binary search tree is also a balanced binary search tree).

          5                    depth 1 (root)
     /----+----\ 
    2           6              depth 2
 /--+--\     /--+--\ 
1       3   4       7          depth 3

For searching of any number in this tree, the worst case scenario is that we reach the maximum depth of the tree (e.g., 3 in this case), until we terminate the search. At depth 3, we have performed 3 comparisons, hence, at arbitrary depth l, we would have performed l comparisons.

Now, for a complete binary search tree as the one above, of arbitrary size, we can hold 1 + 2^(maxDepth-1) different numbers. Now, let's say we have a complete binary search tree with exactly n (distinct) numbers. Then the following holds

n = 1 + 2^(maxDepth-1)  (+)

Hence

(+) <=> 2^(maxDepth-1) = n - 1 
    <=> log2(2^(maxDepth - 1)) = log2(n - 1)
    <=> maxDepth - 1 = log2(n - 1)

        => maxDepth = log2(n - 1) + 1

Recall from above that maxDepth told us the worst case number of comparisons for us to find a number (or it's non-existance) in our complete binary tree. Hence

worst case scenario, n nodes : log2(n-1) + 1

For studying asymptotic or limiting behaviour of this search, n can be considered sufficiently large, and hence log2(n) ~= log2(n-1) holds, and subsequently, we can say that a quite good (tight) upper bound for the algorithm is O(log2(n)). Hence

The time complexity for searching in a complete binary tree, for n nodes, is O(log2(n))

For a non-complete binary search tree, an analogous reasoning as the one above leads to the same time complexity. Note that for a non-balanced search tree the worst case scenario for n nodes is n comparisons.

---

Answer: From above, it's clear that O(n/2) is not a proper bound for the time complexity of a binary search tree of size n; whereas however O(log2(n)) is. (Note that the prior might be a correct bound for sufficiently large n, but not a very good/tight one!)

Answer 5

The best balanced binary tree is the AVL tree. I say "the best" conditioned to the fact that their modifying operations are O(log(n)). If the tree is perfectly balanced, then its height is still less (but it is not known a way for modifying it in O(log(n)).

It could be shown that the maximum height of an AVL tree is less than

1.4404 log(n+2) - 0.3277

Consequently the worst case for a search in an AVL tree is an unsuccessful search whose path from the root ends in the deepest node. But by the previous result, this path cannot be longer than 1.4404 log(n+2) - 0.3277.

And since 1.4404 log(n+2) - 0.3277 < n/2, the statement is false (assuming a n enough large)

Answer 6

lets first see the BST(binary search tree) properties which tell that..

-- root must be > then left_child 

-- root must be < right child


                  10
                 /  \
               8     12
              / \    /  \ 
             5  9   11   15
            / \          / \
           1   7        14  25  

height of given tree is 3(number of edges in longest path 10-14).

suppose you query to search 14 in given balanced BST

          node--  10          14 > 10
                 /  \         go to right sub tree because all nodes  
               8     12       in right sub tree are > 10
              / \    /  \ 
             5  9   11   15    n = 11 total node
            / \          / \
           1   7        14  25  


        node--   12           14 > 12   
                /  \          again go to right sub tree..
              11   15
                   / \        n = 5   
                  14  25   


         node--  15       14 > 15 
                /  \      this time node value is > required value so 
               14  25       goto left sub tree
                           n = 3



             'node --  14       14 == 14 value find
                               n = 1'

from above example we can see that at every comparison size of problem(number of nodes) halve we can also say that at every comparison we switch to next level thus height of tree is increased by 1 .

as max height of balanced BST is log(N) in worst case we need to go to leaf of tree hence we take log(N) step to do so..

hence O of BST search is log(N).