Very often in Computer Science applications, there is a need to discover if a collection contains a specific element. These types of problems are called search problems, and specially for large data sets it is very important that search algorithms be as efficient as possible.

Whereas binary search is an appropriate technique for the problem of static searching, where the data values are known in advance and it is not possible to add or delete elements from the collection (or where addition and removal of elements is very infrequent), the more general case involves dynamic searching schemes. In these cases a vector may not be an appropriate structure, since it requires O(n) operations in the worst case. Using alternative data structures, we can reduce this complexity significantly. One such data structure is the binary search tree.

A binary search tree is organized, as the name suggests, in a binary tree, as shown in Figure 1.1. Such a tree can be represented by a linked data structure in which each node is an object. In addition to a key field, each node contains fields left and right that point to the nodes corresponding to its left and its right child respectively. If a child is missing, the appropriate field contains the value NIL.

Figure 1.1 A very balanced tree

Next Page
Return to Main Page