Figure 1.1 A very balanced tree
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.