binary search tree (idea)

Kefabi's explaination isn't quite correct. His search example would only requre 40 compairisons if the tree was well balanced. There are other specialized BST data structures that more acurately capture his idea by making sure that this is the case. Some of them are (in no particuar order):

• AVL trees
• Red-Black trees
• Random BSTs
• Treaps

In a balanced tree, the time to search for any particular element is O(log n) (that's where the 40 comes from: 40 is log base 2 of 1,099,511,627,776). But if the tree is not balanced, it could take significantly longer. Imagine if the 1,099,511,627,776 elements were inserted into the tree in increasing order, then the tree would look like this:

               1
                \
                 2
                  \
                   3
                    \
                     4
                      .
                       .
                        .