## Background

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