Redblack trees were first introduced by Guibas and Sedgewick [38].
Despite their high implementation complexity they are found in some of
the most commonly used libraries and applications. Most algorithms and
data structures textbooks discuss some variant of redblack trees.
Andersson [6] describes a leftleaning version of balanced trees
that is similar to redblack trees but has the additional constraint
that any node has at most one red child. This implies that these trees
simulate 23 trees rather than 24 trees. They are significantly simpler,
though, than the RedBlackTree structure presented in this chapter.
Sedgewick [64] describes two versions of leftleaning redblack
trees. These use recursion along with a simulation of topdown splitting
and merging in 24 trees. The combination of these two techniques makes
for particularly short and elegant code.
A related, and older, data structure is the AVL tree [3].
AVL trees are heightbalanced:
At each node , the height
of the subtree rooted at
and the subtree rooted at
differ by at most one. It follows immediately that, if is the
minimum number of leaves in a tree of height , then obeys the
Fibonacci recurrence
with base cases and . This means is approximately
, where
is the
golden ratio. (More precisely,
.)
Arguing as in the proof of Lemma 9.1, this implies
so AVL trees have smaller height than redblack trees. The height
balancing can be maintained during
and
operations
by walking back up the path to the root and performing a rebalancing
operation at each node
where the height of
's left and right
subtrees differ by two. See Figure 9.10.
Figure 9.10:
Rebalancing in an AVL tree. At most two rotations are required
to convert a node whose subtrees have a height of and into a node
whose subtrees each have a height of at most .

Andersson's variant of redblack trees, Sedgewick's variant of redblack
trees, and AVL trees are all simpler to implement than the RedBlackTree
structure defined here. Unfortunately, none of them can guarantee that
the amortized time spent rebalancing is per update. In particular,
there is no analogue of Theorem 9.2 for those structures.
Figure 9.11:
A redblack tree on which to practice.

Exercise 9..1
Illustrate the 24 tree that corresponds to the RedBlackTree in
Figure
9.11.
Exercise 9..2
Illustrate the addition of 13, then 3.5, then 3.3 on the RedBlackTree
in Figure
9.11.
Exercise 9..3
Illustrate the removal of 11, then 9, then 5 on the RedBlackTree in
Figure
9.11.
Exercise 9..4
Show that, for arbitrarily large values of
, there are redblack
trees with
nodes that have height
.
Exercise 9..5
Consider the operations
and
. What do
these operations do to the underlying 24 tree that is being simulated
by the redblack tree?
Exercise 9..6
Show that, for arbitrarily large values of
, there exist sequences
of
and
operations that lead to redblack trees
with
nodes that have height
.
Exercise 9..7
Why does the method
in the RedBlackTree implementation
perform the assignment
? Shouldn't this already
be done by the call to
?
Exercise 9..9
Suppose you are given a binary search tree with
nodes and a
height of at most
. Is it always possible to colour the
nodes red and black so that the tree satisfies the blackheight and
norededge properties? If so, can it also be made to satisfy the
leftleaning property?
Exercise 9..10
Suppose you have two redblack trees
and
that have the
same black height,
, and such that the largest key in
is smaller
than the smallest key in
. Show how to merge
and
into a single redblack tree in
time.
Exercise 9..11
Extend your solution to Exercise
9.10 to the case where the
two trees
and
have different black heights,
.
The runningtime should be
.
Exercise 9..12
Prove that, during an
operation, an AVL tree must perform
at most one rebalancing operation (that involves at most two rotations;
see Figure
9.10). Give an example of an AVL tree and a
operation on that tree that requires on the order of
rebalancing operations.
Exercise 9..13
Implement an AVLTree class that implements AVL trees as described
above. Compare its performance to that of the RedBlackTree
implementation. Which implementation has a faster
operation?
Exercise 9..14
Design and implement a series of experiments that compare the relative
performance of
,
, and
for the SSet implemeentations SkiplistSSet,
ScapegoatTree, Treap, and RedBlackTree. Be sure to include
multiple test scenarios, including cases where the data is random,
already sorted, is removed in random order, is removed in sorted order,
and so on.
opendatastructures.org