Chapter 13 showed that a binary search tree of height *h* can implement any of the basic dynamic-set operations--such as SEARCH, PREDECESSOR, SUCCESSOR, MINIMUM, MAXIMUM, INSERT, and DELETE--in *O*(*h*) time. Thus, the set operations are fast if the height of the search tree is small; but if its height is large, their performance may be no better than with a linked list. Red-black trees are one of many search-tree schemes that are "balance" in order to guarantee that basic dynamic-set operations take *O*(lg *n*) time in the worst case.

A * red-black tree* is a binary search tree with one extra bit of storage per node: its

A binary search tree is a red-black tree if it satisfies the following **red-black properties:**

1. Every node is either red or black.

3. If a node is red, then both its children are black.

4. Every simple path from a node to a descendant leaf contains the same number of black nodes.

An example of a red-black tree is shown in Figure 14.1.

We call the number of black nodes on any path from, but not including, a node *x* to a leaf the * black-height* of the node, denoted bh(

The following lemma shows why red-black trees make good search trees.

A red-black tree with *n* internal nodes has height at most 21g(*n* + 1).

n22 - 1.^{h/}

An immediate consequence of this lemma is that the dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR can be implemented in *O*(lg *n*) time on red-black trees, since they can be made to run in *O*(*h*) time on a search tree of height *h* (as shown in Chapter 13) and any red-black tree on *n* nodes is a search tree with height *O*(lg *n*). Although the algorithms TREE-INSERT and TREE-DELETE from Chapter 13 run in *O*(lg *n*) time when given a red-black tree as input, they do not directly support the dynamic-set operations INSERT and DELETE, since they do not guarantee that the modified binary search tree will be a red-black tree. We shall see in Sections 14.3 and 14.4, however, that these two operations can indeed be supported in *O*(lg *n*) time.

The search-tree operations TREE-INSERT and TREE-DELETE, when run on a red-black tree with *n* keys, take *O*(lg *n*) time. Because they modify the tree, the result may violate the red-black properties enumerated in Section 14.1. To restore these properties, we must change the colors of some of the nodes in the tree and also change the pointer structure.

The pseudocode for LEFT-ROTATE assumes that *right*[*x*] NIL.

Figure 14.3 shows how LEFT-ROTATE operates. The code for RIGHT-ROTATE is similar. Both LEFT-ROTATE and RIGHT-ROTATE run in *O*(l) time. Only pointers are changed by a rotation; all other fields in a node remain the same.

Write pseudocode for RIGHT-ROTATE.

Argue that rotation preserves the inorder key ordering of a binary tree.

Let *a, b*, and *c* be arbitrary nodes in subtrees *, *, and , respectively, in the left tree of Figure 14.2. How do the depths of *a, b*, and *c* change when a left rotation is performed on node *x* in the figure?

Insertion of a node into an *n*-node red-black tree can be accomplished in *O*(lg *n*) time. We use the TREE-INSERT procedure (Section 13.3) to insert node *x* into the tree *T* as if it were an ordinary binary search tree, and then we color *x* red. To guarantee that the red-black properties are preserved, we then fix up the modified tree by recoloring nodes and performing rotations. Most of the code for RB-INSERT handles the various cases that can arise as we fix up the modified tree.

In line 18 of RB-INSERT, we set the root's color to black. What is the advantage of doing so?

Like the other basic operations on an *n*-node red-black tree, deletion of a node takes time *O*(lg *n*). Deleting a node from a red-black tree is only slightly more complicated than inserting a node.

In order to simplify boundary conditions in the code, we use a sentinel to represent NIL (see page 206). For a red-black tree *T,* the sentinel *nil*[*T*]* *is an object with the same fields as an ordinary node in the tree. Its *color* field is BLACK, and its other fields--*p, left, right,* and *key*--can be set to arbitrary values. In the red-black tree, all pointers to NIL are replaced by pointers to the sentinel *nil*[*T*]*.*

The procedure RB-DELETE is a minor modification of the TREE-DELETE procedure (Section 13.3). After splicing out a node, it calls an auxiliary procedure RB-DELETE-FIXUP that changes colors and performs rotations to restore the red-black properties.

RB-DELETE (T, z)

1ifleft[z] = nil[T] or right[z] = nil[T]

2theny z

3elsey TREE-SUCCESSOR(z)

4ifleft[y] nil[T]

5thenx left[y]

6elsex right[y]

7 p[x] p[y]

8ifp[y] = nil[T]

9thenroot[T] x

10else ify = left[p[y]]

11thenleft[p[y]]x

12elseright[p[y]]x

13ifyz

14thenkey[z]key[y]

15 Ifyhas other fields, copy them, too.

16ifcolor[y] = BLACK

17thenRB-DELETE-FIXUP (T,x)

18returny

Argue that the root of the red-black tree is always black after RB-DELETE executes.

In which lines of the code for RB-DELETE-FIXUP might we examine or modify the sentinel *nil*[*T*]?

Simplify the code for LEFT-ROTATE by using a sentinel for NIL and another sentinel to hold the pointer to the root.

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. Such a set is called * persistent.* One way to implement a persistent set is to copy the entire set whenever it is modified, but this approach can slow down a program and also consume much space. Sometimes, we can do much better.

* b. *Write a procedure PERSISTENT-TREE-INSERT that, given a persistent tree

14-2 Join operation on red-black trees

The * join *operation takes two dynamic sets

* e.* Argue that the running time of RB-JOIN is

The idea of balancing a search tree is due to and Landis [2], who introduced a class of balanced search trees called "AVL trees" in 1962. Balance is maintained in AVL trees by rotations, but as many as (lg *n*) rotations may be required after an insertion to maintain balance in an *n*-node tree. Another class of search trees, called "2-3 trees," was introduced by J. E. Hopcroft (unpublished) in 1970. Balance is maintained in a 2-3 tree by manipulating the degrees of nodes in the tree. A generalization of 2-3 trees introduced by Bayer and McCreight [18], called B-trees, is the topic of Chapter 19.

Of the many other variations on balanced binary trees, perhaps the most intriguing are the "splay trees" introduced by Sleator and Tarjan [177], which are "self-adjusting." (A good description of splay trees is given by Tarjan [188].) Splay trees maintain balance without any explicit balance condition such as color. Instead, "splay operations" (which involve rotations) are performed within the tree every time an access is made. The amortized cost (see Chapter 18) of each operation on an *n*-node tree is *O*(lg *n*).