Red-black tree properties are maintained by means of rotations and color changes by using assignment operations. A simple rotation, for trees without parent pointers, requires in the common case three assignment operations while a color change requires one assignment operation. Reducing the number of assignment operations will certainly increase performance. This is the main purpose of the proposed delete algorithm. The improvement of the Red-Black tree delete algorithm is also due to the difference in coloring. Indeed, the coloring of the resulting tree is favorable for future deletions as the new delete algorithm generates less black nodes. In order to show this improvement, we denote, in the rest of the paper, the Red-Black delete algorithm by RB and the new delete algorithm by RB+. In what follows, we first give the new transformations and then we demonstrate their validity. Thereafter, we describe the new delete algorithm and we compare it with the standard delete one.
New Transformations
Figures 3(a1) and 3(a2) show two situations representing cases 2 and 3 of the delete algorithm given above (with the assumption that the parent node is red). Two symmetrical cases exist when the doubly-black node is on the right of node P.
The conflicts are differently solved by the two algorithms as shown in Fig. 3. Since RB does not take into account the color of the parent node, it generates two black children (Figs. 3(b1) and 3(b2)) while RB+ generates two red children (Figs. 3(c1) and 3(c2)).
On the one hand, RB+ does not modify colors of nodes when the parent is red and the left child of S is black. This is very worthwhile since no color is modified and no black node is thus added. It is the case of Fig. 3(a1). On the other hand, RB+ modifies two colors only in the case where both the parent and the left child of S are red. It is the case of Fig. 3(a2). However, in case 3, only one color is modified if the parent of S is black. Thus, RB+ saves color changes.
It is certainly better to keep two red nodes instead of generating two black ones. This is particularly true for future delete operations. Indeed, it is easy to see that red nodes stop the cascade involved in the case 1of the delete process. Furthermore, when there are more black nodes, there will be certainly more restructurings and thus more rotations to perform during the delete process since the tree’s balance is guaranteed by black nodes. Certainly the fact that case 2 can preserve the red nodes – in some situations – means that this is not worse for future insert operations. This will be confirmed later by simulation.
It is also important to notice that the new transformations preserve the numbers of red and black nodes whereas the standard transformations eliminate one red node and add one black node.
Validity of the transformations
Recall that Bh (Node) denotes the number of black nodes from node Node to any leaf in the tree. Let us demonstrate now that the new transformations maintain Red-Black tree properties. The situations in Figs. 3(a1) and 3(a2) involve Bh(S) – Bh(X) = 1 since X is a doubly-black node. If we assume that Bh(X) = n then Bh(S) = n + 1. We can easily deduce that Bh (LS) = Bh (RS) = n. After a simple left rotation of node P as depicted in Fig. 3(c1), P will have n as black height since P is red and both their new children (X and LS) have each one a black height equal to n. As node RS has also a black height equal to n, we can conclude that node S is perfectly balanced considering only black nodes. After a double rotation around node LS (a right rotation of node S followed by a left rotation of node P) as shown in Fig. 3(c2), node LS remains also perfectly balanced considering only black nodes. First, node P will have, at its left, node X with a black height equal to n and, at its right, the left child of node LS which has also a black height equal to n since its parent LS is red. As P is red, it has thus a black height equal to n. Second, node S will have, at its right, node RS with a black height equal to n and, at its left, the right child of LS that has a black height equal to n since its parent LS is red. Node S has thus also a black height equal to n. We conclude that the children of node LS have the same black height.
The proposed delete algorithm
On the basis of the transformations above, we suggest that cases 2 and 3 of the Red-Black tree delete algorithm be modified as described in Fig. 4. The change concerns only node coloration. The new proposition is given in the right column. The text in capital letters shows the difference.
The new code can be justified as follows:
Figure 3(c1) implies that we do not modify colors of nodes S, P and RS if condition [(P is Red) AND (LS is Black)] holds. In all other cases, we must modify colors of these nodes, i.e. when condition NOT [(P is Red) AND (LS is Black)] holds. Note that the latter condition is equivalent to [(P is Black) OR (LS is Red)].
Figure 3(c2) shows a different coloring that eliminates one black color compared to the standard transformation.
For case 2, the new delete algorithm colors with the same manner but only when condition [(P is Black) OR (LS is Red)] holds. For case 3, the coloration is totally different. Indeed, instead of coloring two times as this is done by the standard algorithm, the new algorithm always modifies one color but another color is modified only when condition (P is Red) holds. Therefore, the new delete algorithm can save three color changes in case 2 and one color change in case 3. As cases 2 and 3 together cover about 50% of all cases with the new delete algorithm and about 44% with the standard deletion algorithm (Tables 6 and 7 in the section Simulation), this change will certainly save a large number of color changes.
Let us now show that case 2 can be refined in order to save more color changes and thus to reduce running time. Indeed, considering only color changes, the code of case 2 is the following:
(i)
If (Color(P) = Black) OR (Color(Left_Child(S)) = Red)
We use Color (Node) to refer to the color field of node Node, Left_child(Node) and Right_child(Node) to refer to the left and right pointer field of node Node respectively.
It is easy to deduce that the code above can be rewritten as
(ii)
If (Color(P) = Black)
Else
if (Color(Left_Child (S)) = Red)
The three color changes in (i) are performed when one of the two conditions (Color (P) = Black) or (Color(Left_Child (S)) = Red) holds. In the case where (Color (P) = Black) we can eliminate the first two color changes since, for the first, S is already black (condition for case 2), and for the second, P is also already black (condition in (i)).
If Color (P) is not black, we can also perform the three color changes if condition (Color (Left_Child (S)) = Red) holds. As Color (P) is Red, we can replace Color (P) by Red in the first color change. We thus obtain code (ii).
We are doing the same for the symmetric case by replacing Right_Child by Left_Child and vice-versa in codes (i) and (ii).
In summary, the new delete algorithm proposes only a minor alteration in the standard Red-Black tree delete algorithm. Only some tests are added to the standard delete algorithm and thus the code size is almost the same. This involves, however, a new coloring of the tree that is favorable for future deletions and a gain of a great percentage of color changes. Furthermore, this alteration has significant performance benefits. Indeed, we will see in the rest of the paper that the number of maintenance operations is reduced and the number of rotations decreases. Certainly, all these features improve the standard delete algorithm. The examination of the running times made by the two algorithms will confirm more this improvement.
New delete algorithm versus standard delete algorithm
Let us recall that the Red-Black delete algorithm always begins by removing a node from a tree. Considering only color changes, the algorithm works as follows: if the deleted node is black, either the algorithm modifies one color and terminates or it applies a maintenance operation (one of the 4 cases) in order to preserve Red-Black tree properties.
For our purpose, let us examine cases 2 and 3.
Figure 5 gives the Pascal implementation of cases 2 and 3 for RB and RB+ by considering only color changes. Here, the codes explicitly show color changes and tests, with an emphasis on simple and read-dependant writes.
For C2 runs of the RB code for case 2, the total number of color changes is close to 3C2 and for C2 runs of the RB+ code for case 2 it is close to C2 (α1 + 3 α2). α1 designates the satisfiability rate of the test "P.Color = Black" and α2 the one of the test "S.Left_child.Color = Red". We will show in the next section how to determine α1 and α2. The last formula can be justified as follows: for each run of the RB+ code for case 2, if the first test is true then one color change is performed. Otherwise, if the second test is true then three color changes are performed. As the first test is satisfied at the rate of α1, and the second test at the rate of α2, we have in total C2α1 + 3 C2α2 color changes.
For C2 runs of the RB+ code for case 2, the total number of tests done by the RB+ code for case 2 is close to C2 (2- α1). Indeed, for α1C2 deleted items, only one test is made. For the rest, i.e. C2 (1- α1), two tests are made. The total number of tests is then α1C2 + 2 C2 (1- α1).
Likewise, for C3 runs of the RB code for case 3, the total number of color changes is close to 2C3, and for C3 runs of the RB code+ for case 3 it is close to C3 (1 + β). β designates the satisfiability rate of the test "P.Color = Red". Indeed, for each run of the RB+ code for case 3, one color change is always performed. Moreover, if the test is true then another color change is made. We therefore have C3 + β C3. It is easy to see that the total number of tests done by the RB+ code for case 3 is close to C3. Table 1 sums up our study.
Table 1
Color changes and tests: RB versus RB+
|
C2 runs / Case 2
|
C3 runs / Case 3
|
|
RB
|
RB+
|
RB
|
RB+
|
Color changes
|
3C2
|
C2 (α1 + 3 α2)
|
2C3
|
C3 (1 + β)
|
Tests
|
0
|
C2 (2- α1)
|
0
|
C3
|
We will show through simulation that we can determine α1, α2 and β. We could then write a separated program that compares the running times of the two codes for case 2 and the ones for case 3. The proposed change to the delete algorithm is simple and can be beneficial a priori to all applications of Red-Black trees. The new delete algorithm may avoid three color changes in case 2 and colors differently in case 3 possibly avoiding one color change. This implies a new coloring of the tree and a gain of an enormous amount of color changes. Consequently, the total number of maintenance operations (the four cases) and the one of rotations decreases. On the contrary, some tests are added to the new delete algorithm. However, we will show that the tradeoff between the gain in color changes and the added tests is useful as it saves running time while preserving the insert and search operation performance. In the next section, we justify our simulation work as follows:
-
- As the new delete algorithm offers a new coloring of the tree, we begin by giving the gain in color changes. Consequently, we will show that the new coloring decreases substantially maintenance operations and reduces slightly rotations.
-
- The new delete algorithm adds tests to reduce color changes. To convince that this compromise saves running time, we conducted the following steps:
(a) We first showed that cases 2 and 3 together cover an important percentage of total cases.
(b) We determined in cases 2 and 3 of RB+, the satisfiability rates of the added tests: α1, α2 and β.
(c) We developed a separated simulation program showing that the new changes are beneficial in running time.
-
- The insert operation is as important as the delete one. We will show that the new delete algorithm does not disfavor the insert operation. In contrast, we will show that the new coloring reduces the cascading effect involved in case 1 of the insert algorithm.
-
- The running time is a significant factor to confirm that the new delete algorithm outperforms the standard one. So, we will show that the new algorithm saves running time.
-
- The performance of the search algorithm is required in the vast majority of applications of Red-Black trees. So, we will show that it is not degraded by the new delete algorithm.