Page 2 of 4
All a question of balance
You might at first think that the solution is always to order the nodes so that the search tree a perfect example of the complete tree in Figure 2a.
The first problem is that not all trees have enough nodes to be complete. For example, a tree with a single node is complete but one with two nodes isn't and so on. It doesn't take a genius to work out that complete trees always have one less than a power of two nodes. With other numbers of nodes the best we can do is to ask that a tree's terminal nodes are as nearly as possible on the same level.
You can think of this as trying to produce a tree with `branches' of as nearly the same length as possible. In practice it turns out to be possible always to arrange a tree so that the total number of nodes in each node's right and left sub-trees differ by one at most, see Figure 3.
Figure 3: A balanced tree
Such trees are called perfectly balanced trees because they are as in balance as it is possible to be for that number of nodes. If you have been following the argument it should be obvious that the search time is at a minimum for perfectly balanced trees.
At this point it looks as though all the problems are solved. All we have to do is make sure that the tree is perfectly balanced and everything will be as efficient as it can be. Well this is true but it misses the point that ensuring that a tree is perfectly balanced isn't easy. If you have all of the data before you begin creating the tree then it is easy to construct a perfectly balanced tree but it is equally obvious that this task is equivalent to sorting the data and so we might as well just use a sorted list and binary search approach.
The only time that a tree search is to be preferred is if the tree is built as data arrives because there is the possibility of building a well shaped search tree without sorting.
For example, if you already have the perfectly balanced tree in Figure 4a and the value 2 has to be added to it then the result is the perfectly balanced tree in Figure 4b.
Figure 4a: A perfectly balanced tree
Figure 4b: Adding (2) keeps the tree in balance.
However it isn't always possible to insert a new data value and keep the tree in perfect balance. For example, there is no way to add 9 to the tree in Figure 4a and keep it in perfect balance (Figure 4c) without reordering chunks of the tree. It turns out the effort expended in reorganising the tree to maintain perfect balance just isn't worth it.
Figure 4c: Adding (9) makes the tree unbalanced