A binary tree with the property that the value of any node is greater than the largest value in its left subtree and less than the smallest value in its right subtree. Useful, in that one can perform a binary search on one.

Take a sorted list. This list has 1,099,511,627,776 elements in it. (That's over a trillion!) A sequencial search would have to make at most 1,099,511,627,776 comparisons to find any given element. Searching through the list sorted in a binary tree would require 40 comparisons or less to find any given element. That's 27,487,790,694.4 times less the number of comparisons required. Surely you see the usefulness of binary trees. Binary trees are our friends indeed.

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):

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
                      .
                       .
                        .
And searching for a particular element would take O(n) time!

Log in or register to write something here or to contact authors.