Search

Generic Red-Black Tree and its C# Implementation

By: Richard Wiener

Abstract

A fascinating and important balanced binary search tree is the red-black tree. Rudolf Bayer invented this important tree structure in 1972, about 10 years after the introduction of AVL trees. He is also credited with the invention of the B-tree, a structure used extensively in database systems. Bayer referred to his red-black trees as “symmetric binary B-trees.” A full C# implementation of a constrained generic Red-Black tree is presented.

Cite as:

Richard Wiener, “Generic Red-Black Tree and its C# Implementation”, Journal of Object Technology, Volume 4, no. 2 (March 2005), pp. 59-80, doi:10.5381/jot.2005.4.2.c6.

PDF | HTML | DOI | BiBTeX | Tweet this | Post to CiteULike | Share on LinkedIn