runtime - Search times for binary search tree

Question

Does anyone know how to figure out search time for a binary search tree(i.e. worst-case, best-case, and average-case)?

Answer 1

For a non-self-balancing tree (possible but unusual for a search tree), worst case is O(n), which is for the degenerate binary tree (a linked list).

In this case, you have to search, on average, half the list before finding your desired element.

Best case is O(log₂ n) for a perfectly balanced tree, since you cut the search space in half for every tree level.

Average case is somewhere in between those two and depends entirely on the data :-)

Since you rarely get to control the sequence in which data is inserted into a tree, self-balancing trees are usually preferable since, while they add a small amount of time to each insertion or deletion, they greatly speed up searching. Their worst case is so much better than unbalanced trees.

                 8
         _______/ \_______
        /                 
       4                  12
    __/ \__             __/ \__
   /                  /       
  2         6        10        14
 /        /        /        / 
1   3     5   7     9  11    13  15

In this perfectly balanced tree, you can see that you get 2ⁿ-1 nodes for every n levels. That means for 15 nodes, you never have to search more than four nodes to find it (e.g., to find 13, you search 8, 12, 14 and 13). That's where the log₂n figure comes from.

A degenerate unbalanced tree, as already stated, is a linked list. If your data arrived in sequence and you inserted it into an unbalanced binary tree, you'd get:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
                                           |
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15

To find 13 in that case, you'd need to search 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 and 13, hence O(n).