template<class T>
   class LinkedList {
     void Insert(const T&);
     T *Query(const T&) const;
   };

Templates are especially well-suited to implementing container classes. As an example, I have implemented a balanced binary tree class template. Balanced binary trees are tremendously useful data structures for keeping track of dynamic collections of ordered objects. Almost all operations on a balanced binary tree require only O(logN) time where N is the number of nodes in the tree. These operations include insertion, deletion, query, minimum, and maximum. In addition, if you have a pointer to a node in the binary tree, you can find the predecessor or successor of that node in O(logN) time. The balanced binary tree in this article is a red-black tree as described by Cormen et al. (1990).

The binary tree implementation makes use of three class templates: BinaryNode, Binarytree, and BinaryTreeIter. BinaryNode implements the node of a binary tree. Since a binary tree node is really the root of a subtree, BinaryNode implements most of the functionality required for binary trees. It contains some member functions that are protected, including LeftRotate, RightRotate, and DeleteFixup. These functions are used to balance the tree after an insertion or deletion, so they are usable only by classes that inherit from instances of BinaryNode.

BinaryTree encapsulates a single, balanced binary tree. It contains a pointer to a BinaryNode (the root of the tree), and makes available member functions such as Insert that are implemented in terms of BinaryNode.

BinaryTreeIter, an iterator class for BinaryTree, makes it unnecessary for users of BinaryTree to deal directly with BinaryNodes. Its constructors take a tree as input; the iterator then has a pointer to the root node of the binary tree. Subsequent operations operate on the subtree pointed to by this root node; the Min function, for example, finds the minimum node in the subtree and points the iterator at it. The Contents member function returns a pointer to the contents of the root node in the subtree, or 0 if the iterator is not pointing at anything.

BinaryTree, like the InsertionSort function template given earlier, has been designed to work with any class as long as operator< is defined.

An order statistics tree supports all the operations that a binary tree supports, plus a very efficient Selection operation. The Selection operation chooses the ith element in the sorted order of an N-element array. For example, numbering from zero, the median of an array for odd N is the (N—1)/2th element. For a single selection operation, optimal O(N) algorithms have been derived. The order statistics tree supports selection in O(logN) time, where N is the number of elements in the tree. Since N elements must be inserted into the order statistics tree before performing selection, the order statistics tree takes O(NlogN) time for a single selection operation. This asymptotic runtime is not efficient compared to the linear algorithms; however, when the number of selection operations grows, the advantage offered by the O(logN) time for a single selection gets more noticeable.

The order statistics tree works well when the data sets from which it selects do not change very much between selections. A good application is the median neighborhood operation in image processing. The median operation performs noise reduction by replacing each pixel with the median of its neighbors (including itself, so a total of nine pixels are considered). You might implement this algorithm by reading the pixel values for each pixel of its neighbors and itself, computing the median, and replacing the pixel value. But the data set for the next pixel is similar to the data set for the pixel just computed. (They share three elements.) If you maintain an order statistics tree to compute the median values, pseudocode for a single pixel would look like:

Compute median using O(lgN) selection of the OS tree
Delete leftmost 3 pixel values from OS tree
Insert rightmost 3 pixel values from OS tree

   template<class T>
   class OSNode : public BinaryNode<T> {
   // class definition
   };

This implementation is inconvenient because the left, right, and parent pointers are declared as BinaryNode<T> *s in the BinaryNode class template. C++ will not automatically promote a pointer to an inherited class to a pointer to its base class. So, because the OSNode class template considers these pointers to point to OSNode<T>s, the code for OSNode member functions contains many typecasts from BinaryNode<T> * to OSNode<T> *.

OSTree inherits from BinaryTree just like OSNode inherits from BinaryNode. OSTree does not need to overload as many functions, however, since the node templates do most of the work. For example, the BinaryTree version of DeleteItem works just fine for OSTree.

(C) 1993 Nicholas Wilt.

Bentley, J. 1986. Programming Pearls. Reading, MA: Addison-Wesley.

Cormen, T., C. Leiserson and R. Rivest. 1990. Introduction to Algorithms. Cambridge, MA: MIT Press.

Paeth, A. 1990. "Median finding on a 3x3 grid,". Graphics Gems. Boston: Academic Press.

Preparata, F. P. and M. I. Shamon. 1985. Computational Geometry. New York: Springer-Verlag.