3.1 Binary search tree

A binary search tree is used to search for items. We define a function v for a binary tree (N,P_L,P_R) so that for all n ∈ N, v(n) represents a value that is associated with node n. Note that this function does not need to be injective. Multiple nodes may map to the same value.

Let us consider a binary search tree (N,P_L,P_R). We can pick any element (a,b) in P_L, then consider the subtree T((N,P_L,P_R),b) = (N′,P_L′,P_R′). A binary search tree guarantees that ∀n′∈ N′ : v(n′) ≤ v(a). Similarly, if we pick an element (a,b) ∈ P_R, then the subtree T((N,P_L,P_R),b) = (N′,P_L′,P_R′) has the special property that ∀n′∈ N′ : v(n′) > v(a).

Of course, you can reverse the relationship, and move the equality to either side. In other words, you can have a binary search of any one of the following left-right ordering: (≤,>),(<,≥),(>,≤),(≥,<). For our discussions in this module, however, we use the first option (left tree is ≤, right tree is >).

The following subsubsections describe the tree ADT interface.