A tree which supports efficient search, insertion, and withdrawal
operations is called a *search tree* .
In this context the tree is used to store a finite set of keys
drawn from a totally ordered set of keys *K*.
Each node of the tree contains one or more keys
and all the keys in the tree are unique,
i.e., no duplicate keys are permitted.

What makes a tree into a search tree is that the keys
do not appear in arbitrary nodes of the tree.
Instead, there is a
*data ordering criterion*
which determines where a given key may appear in the tree
in relation to the other keys in that tree.
The following sections present two related types of search trees,
*M*-way search trees and binary search trees.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.