Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Basics

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.




next up previous contents index

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