Constructing Red-Black Trees

This paper explores the structure of red-black trees by solving an apparently simple problem: given an ascending sequence of elements, construct a red-black tree which contains the elements in symmetric order. Several extreme red-black tree shapes are characterized: trees of minimum and maximum height, trees with a minimal and with a maximal proportion of red nodes. These characterizations are obtained by relating tree shapes to various number systems. In addition, connections to left-complete trees, AVL trees, and half-balanced trees are highlighted. 1 Introduction Red-black trees are an elegant search-tree scheme that guarantees O(log n) worstcase running time of basic dynamic-set operations. Recently, C. Okasaki (1998; 1999) presented an impressively simple functional implementation of red-black trees. In this paper we plunge deeper into the structure of red-black trees by solving an apparently simple problem: given an ascending sequence of elements, construct a red-black tree whic..