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

Binary Search Trees

Just as the binary tree is an important category of N-ary trees, the binary search tree  is an important category of M-way search trees.

Definition (Binary Search Tree)  A binary search tree    T is a finite set of keys. Either the set is empty, tex2html_wrap_inline63628; or the set consists of a root r and exactly two binary search trees tex2html_wrap_inline63784 and tex2html_wrap_inline63786, tex2html_wrap_inline63788, such that the following properties are satisfied:
  1. All the keys contained in left subtree, tex2html_wrap_inline63784, are less than r, i.e., tex2html_wrap_inline64454.
  2. All the keys contained in the right subtree, tex2html_wrap_inline63786, are greater than r, i.e., tex2html_wrap_inline64460.

Figure gif shows an example of a binary search tree. In this case, since the nodes of the tree carry alphabetic rather than numeric keys, the ordering of the keys is alphabetic. I.e., all the keys in the left subtree of a given node precede alphabetically the root of the that node, and all the keys in the right subtree of a given node follow alphabetically the root of that node. The empty trees are shown explicitly as boxes in Figure gif. However, in order to simplify the graphical representation, the empty trees are often omitted from the diagrams.

   figure18764
Figure: A Binary Search Tree


next up previous contents index

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