Unsuccessful binary tree search

Question

I know that for a successful search, the average search time over all inputs containing n keys, using binary trees , is in Big O (lg n), but will it this result hold for an unsuccessful research?

Answer 1

Strictly speaking you may not attain O(log n) even for a successful search if your binary tree is unbalanced.

For a balanced binary tree it's easy to see that the result will hold even if it's unsuccessful, as at any generic step you are allowed to rule out significant fraction (around a half) of the remaining tree.

Answer 2

Yes, the binary tree structure allows you to essentially throw away half the data set at each check.

Just think about how many of the nodes you actually have to visit in order to make that determination that it's not in there.

Example:

     5
     /\
    3  8
   /\  /\
  1 4  6 9

Say you want 2. Start at the root, go left, throwing away 8 and its children. Smaller than 3 so go left throwing away 4. Larger than 1 so it's not there.

In this case you visited only 5, 3, and 1. You can think of it as the same as inserting a new node.