Improving the Red-Black tree delete algorithm

doi:10.21203/rs.3.rs-1194654/v1

Today, Red-Black trees are becoming a popular data structure typically used to implement dictionaries, associative arrays, symbol tables within some compilers (C++, Java …) and many other systems. In this paper, we present an improvement of the delete algorithm of this kind of binary search tree. The proposed algorithm is very promising since it colors differently the tree while reducing color changes by a factor of about 29%. Moreover, the maintenance operations re-establishing Red-Black tree balance properties are reduced by a factor of about 11%. As a consequence, the proposed algorithm saves about 4% on running time when insert and delete operations are used together while conserving search performance of the standard algorithm.

Data structures

balanced binary search trees

Red-Black trees

Today, Red-Black trees [1] are becoming one of the most popular data structures. Indeed, they are included as an entire chapter in many books on data structures [2, 3, 4] and they are implemented and integrated in many programming languages (JAVA, C…). They are also used to implement dictionaries and associative arrays.

Red-Black trees are balanced binary search trees. Maintenance operations are mainly restructurings (rotations) and recolorings (color changes). The insert operation performs at most one restructuring and the delete operation at most two restructurings. On the other hand, the two algorithms perform at most lg (N) recolorings. In the entire paper, N designates the number of nodes in the tree and lg the base-two logarithm.

Recall that a Red-Black tree is in fact a new version of a SBB (Symmetric Binary B-tree) proposed by Bayer [5]. A SBB is simply the binary search tree representation of a 2-4 tree.

The main objective of Red-Black trees was to replace AVL trees [6]. These latter trees are more rigidly balanced than Red-Black trees, leading to slower insertion and removal but faster retrieval. Recall that the AVL tree delete algorithm can perform until lg (N) restructurings and it consumes thus more time.

Until now and due to their importance, many applications use Red-Black trees. Recently, a new variant [7] of Red-Black trees is appeared in order to reduce the code for the insert and delete operations.

More details can be found in the web presenting either Red-Black trees or different implementations through many programming languages.

As similar data structures, we can cite AA trees [8], splay trees [9], scapegoat trees [10] and many others. [11] makes a good analysis on performance behavior of such balanced binary search trees. [12] introduces rank balanced tree as a new common framework of balanced search trees.

It is also interesting to mention the paper [13], in which the author compares twenty variants on the binary search trees (BST) data structure. He combines BSTs, AVL trees, Red-Black trees and splay trees with five different node representations. He shows that, according to the expected patterns in the input and the operations to be performed, one or several variants can be used in practice.

So far, the AVL and Red-Black trees continue to attract the interest of researchers. In [14], the authors comparatively evaluate the performance of these two structures by means of simulation with a synthetic workload model.

Furthermore, Red-Black trees are still subject of current research. In [15], the authors use Red-Black trees to explore databases in real time. In [16], Red-Black trees are used as a concurrent data structure in multi-core multi-processor systems.

We want, through this paper, to present an improvement of the Red-Black tree delete algorithm. We will particularly show that the new delete algorithm is more efficient than the standard delete algorithm. This is due to the fact that the new delete algorithm colors differently the tree and considerably reduces the number of color changes. As a result, it saves a significant number of maintenance operations. Consequently, it saves running time while preserving search and insert performance.

Section 2 recalls the insert and delete algorithms for the Red-Black tree structure. Section 3 demonstrates how the delete algorithm can be improved and then presents the new algorithm. Experimental results are presented in section 4. Finally, section 5 concludes the paper.

Figure 1 shows an example of a Red-Black tree where items are integers. It is a binary search tree consisting of two kinds of nodes: black nodes (denoted as squares) and red nodes (denoted as circles). The two following main properties characterize the Red-Black trees:

(i) None of the paths must contain two adjacent red nodes.

(ii) All the paths from root to bottom of the tree have the same number of black nodes.

Null pointers are in bottom of the tree and are considered to be black nodes. Furthermore, the root is black. Tree balance is ensured thanks to property (ii). It is easy to observe that the shortest possible path has only black nodes, and the longest possible path alternates between red and black nodes. Furthermore, no path is more than twice as long as any other path. In other words, the sense in which a Red-Black tree is balanced is expressed by the relationship

lg (N) < Height(x) ≤ 2 lg (N + 1)

where x is any path in the tree and Height(x) is the number of nodes in path x.

In the rest of the paper, we define the black height (Bh) of node Node as the number of black nodes from Node to any leaf in the tree.

The insert and delete operations are somewhat complex and involve several cases. Note that we always start by inserting or deleting any new node in the tree just as we would for any other binary search tree. For the insert operation, the new inserted node is a red one, and possibly produces two red adjacent nodes. For the delete operation, the deleted node can be black. In order to keep Red-Black tree properties, special algorithms are invoked. These algorithms use mainly restructurings and recolorings. The former consist in one or two rotations. The latter consist in one, two or three color changes.

On the one hand, recolorings allow the re-establishment of Red-Black properties. On the other hand, rotations allow equivalent transformations of the tree in order to reduce the height of the tree. Recall that a rotation is a local operation in a binary search tree that preserves the inorder traversal and its role is to maintain the tree balanced when items are inserted into or deleted from the tree. A rotation requires three pointer modifications for trees without parent pointers. Indeed, to perform a right rotation around node A with parent P and left child L, the following operations are needed: Left (A) ← Right (L); Right (L) ← A; Left (P) ← L or Right (P) ← L. To perform a left rotation around node A with parent P and right child R, the following operations are needed: Right (A) ← Left(R); Left(R) ← A; Left (P) ← R or Right (P) ← R. It is easy to see that a double rotation requires five pointer modifications.

It is important to note that at most one restructuring is performed per insertion, and at most two restructurings are performed per deletion. On the other hand, at most lg (N) recolorings are performed per insertion and deletion. As restructuring or recoloring requires O (1) time, the total time for an insert or a delete operation is O (lg (N)). This demonstrates why Red-Black trees provide good performance. We recall hereafter the insert and delete algorithms.

Red-Black tree insert algorithm

To insert an item in a Red-Black tree, we use the usual binary search tree insertion algorithm. The inserted node is always a leaf. In a Red-Black tree, we attribute it the color red. If its parent is also a red node the following actions are performed:

Let X be the red node and P its parent (supposed as a left child)

CASE 1: If P is red and has a red sibling node (S), transform P and S into black nodes and their parent (GP) into a red node. The process continues upward the tree.

CASE 2: If P is red and X is at its left and P has a black sibling node (S), restructure by a right rotation of their parent node (GP), then recolor: GP becomes red and P black. The process terminates.

CASE 3: If P is red and X is at its right and P has a black sibling node (S), restructure by a left rotation of node P followed by a right rotation of the parent of P (GP), then recolor: GP becomes red and X black. The process terminates.

If a red node, when propagating upward the tree, reaches the root of the tree, it then becomes black. It is the only case that increases the black height of the tree. The process terminates. Let us observe that cascading effect is triggered by case 1. The cases where P is a right child are symmetric.

Red-Black tree delete algorithm

To remove an item from a Red-Black tree, we also use the usual binary search tree deletion algorithm. The node to really remove is always either a leaf or a node with one child. Indeed, when the item to remove has two children, we first replace its value by the one of its inorder successor and then we remove that node instead. This inorder successor must be either a leaf or a node with only a right child. In all cases, if the removed node is black, we consider the node which replaces the deleted node. If this node is red, it becomes black and the algorithm terminates. Otherwise, it is considered to be a doubly-black node and the actions in the box below are performed. Naturally, a doubly-black node is typically implemented not by recoloring the node, but rather by keeping track of which black node is temporarily treated as if it were doubly black. Diagrams in Figure 2, in which the triangle denotes a red or black node and the double square a doubly-black node, make the actions easy to understand.

Let X be the doubly-black node and S its sibling node (X is supposed here as a left child). Let P be the X’s parent.

CASE 1: If the sibling node (S) is black and has two black children, transform it into a red node. If their parent P is black, the process continues upward the tree. X becomes that node and it is now considered to be a doubly-black. Otherwise, Transform P into a black node and the process terminates.

CASE 2: If the sibling node (S) is black and has a red right child (RS), restructure by a left rotation of their parent node P, then recolor: P and RS become black and the color of S is the one of the parent node P before the restructuring. The process terminates.

CASE 3: If the sibling node (S) is black and has a red left child (LS), restructure by a right rotation of S then by a left rotation of their parent node P, then recolor: the color of P becomes black and the color of LS is the one of the parent node P before the restructuring. The process terminates.

CASE 4: If the sibling node (S) is red, restructure by a left rotation of the parent node P. Swap color of P and S. The process continues according to case 1, 2 or 3.

If a doubly-black node, when propagating upward the tree, reaches the root of the tree, it simply becomes a singly-black node. It is the only case that decreases the black height of the tree. The process terminates.

Let us observe that cascading effect is triggered by case 1.

The cases where the doubly-black node is a right child are symmetric.

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 Figure 3. Since RB does not take into account the color of the parent node, it generates two black children (Figures 3(b1) and 3(b2)) while RB⁺ generates two red children (Figures 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 Figure 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 Figure 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 Figures 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 Figure 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 Figure 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 Figure 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 (Table 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)

Color( S ) ← Color( P )
Color( P) ← Black
Color(Right_Child (S))⇓ Black

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)

Color(Right_Child (S))← Black

Else

if (Color(Left_Child (S))=Red)

Color( S ) ← Red
Color( P) ← Black
Color(Right_Child (S)) ← Black

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 C₂ runs of the RB code for case 2, the total number of color changes is close to 3C₂ and for C₂ runs of the RB⁺ code for case 2 it is close to C₂ (α₁ + 3 α₂). α₁ designates the satisfiability rate of the test "P.Color=Black" and α₂ the one of the test "S.Left_child.Color=Red". We will show in the next section how to determine α₁ and α₂. 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 α₁, and the second test at the rate of α₂, we have in total C₂α₁ + 3 C₂α₂ color changes.

For C₂ runs of the RB⁺ code for case 2, the total number of tests done by the RB⁺ code for case 2 is close to C₂ (2- α1). Indeed, for α₁C₂ deleted items, only one test is made. For the rest, i.e. C₂ (1- α₁), two tests are made. The total number of tests is then α₁C₂ + 2 C₂ (1- α₁).

Likewise, for C₃ runs of the RB code for case 3, the total number of color changes is close to 2C₃, and for C₃ runs of the RB code⁺ for case 3 it is close to C₃ (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 C₃ + β C₃. It is easy to see that the total number of tests done by the RB⁺ code for case 3 is close to C₃. Table1 sums up our study.

Table1: Color changes and tests: RB versus RB ⁺

	C₂ runs / Case 2		C₃ runs / Case 3
	RB	RB⁺	RB	RB⁺
Color changes	3C₂	C₂ (α₁ + 3 α₂)	2C₃	C₃ (1 + β)
Tests	0	C₂ (2- α1)	0	C₃

We will show through simulation that we can determine α₁, α₂ 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: α₁, α₂ 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.

To conduct the performance comparison, the search, insert and delete algorithms on Red-Black trees and the new delete algorithm were implemented in Delphi. We focused our simulation mainly on the delete process. The two delete algorithms were exposed to the same scenario. We based our simulation essentially on the following deletion pattern: both random insertions and deletions are performed on an existing tree. This model scenario seems a typical case for the comparative analysis of data structures. In our simulation work we start with Red-Black trees built with N random integer values. Tree nodes hold integers in the range [0, 999 999 999].

We applied M insert/delete operations randomly generated on an existing Red-Black tree with N items. N and M are large numbers. For our purpose, we considered N close to M. There are exactly the same number of insert and delete operations. An insertion adds a new random item into the tree. A deletion removes an existing item from the tree.

On the positive side, the proposed delete algorithm reduces substantially color changes. It also significantly reduces maintenance operations. Furthermore, the number of rotations slightly decreases. So, we observed color changes, maintenance operations and rotations.

On the negative side, the proposed change to the delete algorithm adds three tests in order to reduce color changes. So, we separately showed that the added tests improve running time of the standard delete algorithm.

We also studied the impact of the new tree coloring on the insert algorithm. To prove that the new algorithm does not hurt search performance, a study is also made on the tree heights produced by the two delete algorithms.

Finally, to confirm that the new delete algorithm outperforms the standard one, the running time is computed when both insert and delete operations are performed on an existing tree.

In our simulations, we considered the following experiment (EXP 1):

1. Build a Red-Black tree with N random integer values.

2. Build a random sequence of M/2 insert and M/2 delete operations.

3. (a) Run the same sequence of operations separately (with RB and RB ⁺ ) on the same tree to insert a new item in the tree or to remove an existing item randomly chosen from the tree.

(b) - Compute the number of color changes, the number of operation maintenances and the number of rotations made by each delete algorithm.

- Compute α ₁, α₂ and β as defined in the previous section.

- Compute the number of color changes, the number of operation maintenances and the number of rotations made by the insert algorithm when each delete algorithm is used.

- Compute the overall time when each delete algorithm is used.

- Compute the average number of comparisons to find an existing item in the tree.

4. Repeat 1 – 3 three times for N= 100 000 to 1000 000 by step of 100 000 nodes.

In the random sequence, the elements to insert or to delete are known in step 2.

In all the tables below:

Column "Tree size" denotes the exact sizes of Red-Black trees initially generated.
Column "Oper" denotes the exact number of insert operations as well as the one of delete operations.
Values denote the average values of three tests.
The last lines of the tables show the average values of the corresponding columns.

In the entire section, the expression "Delete/insert X items" means delete X items and insert X items in any order. We organize this section as follows:

We first give the main contributions of the new delete algorithm. Then, we perform a deep analysis of the new codes for cases 2 and 3. Finally, we make a synthesis both on our simulation works shown with tables and on our work not shown due to space reasons. In particular, coloring change consequences on the other operations and characteristics will be considered as the impact of the new delete algorithm on the insert and search algorithm and on the overall effects.

4.1 Main contributions

The main contributions of the new delete algorithm reside at several levels. As we outlined it before, the new delete algorithm substantially reduces color changes. It also reduces maintenance operations and increases the delete operations that do not require any maintenance operation. Moreover, the Red-Black tree resulting of the new coloring decreases slightly the number of rotations. All these contributions are the main cause of the improvement of the new delete algorithm compared to the standard delete algorithm.

Color changes

Table 2 shows in columns "RB⁺" and "RB" the numbers of color changes performed by RB⁺ and RB respectively.

Column "(RB - RB⁺) /RB" gives the gain in percentage. The gain is very important since the average percentage of gain is 28.93% (Last column in Table 2). To delete/insert 250 082 items in a tree with 499 909 nodes (the underlined row in Table 2), RB performs 339 475 color changes while RB⁺ performs 241 334. In other words, the new algorithm saves 98 141 color changes. This confirms well our analysis done in section 3.

Table2: Color changes – RB versus RB ⁺

Tree Size	Oper	RB	RB⁺	(RB - RB⁺) /RB
99996	50160	68450	48643	28.94%
199986	100102	136119	96689	28.97%
299966	149845	202707	144164	28.88%
399943	200059	271256	192620	28.99%
499909	250082	339475	241334	28.91%
599858	300204	407730	289863	28.91%
699807	349884	474647	337414	28.91%
799737	399746	541993	385255	28.92%
899686	449964	610793	433936	28.96%
999613	499404	677450	481523	28.92%
				28.93%

Maintenance operations

Table 3 shows in columns "RB⁺" and "RB" the numbers of maintenance operations completed by applying RB⁺ and RB respectively. Column "(RB - RB⁺) /RB" gives the gain in percentage. The number of maintenance operations is reduced by a factor of about 10.98% on average. To delete/insert 250 082 items in a tree with 499 909 nodes (the underlined row in Table 3), RB performs 129 923 maintenance operations while RB⁺ performs 115 688. In other words, the new delete algorithm saves 14 235 maintenance operations.

Table3: Maintenance operations - RB versus RB ⁺

Tree Size	Oper	RB	RB⁺	(RB-RB⁺)/RB
99996	50160	26248	23342	11.07%
199986	100102	52111	46376	11.01%
299966	149845	77483	68987	10.96%
399943	200059	103733	92326	11.00%
499909	250082	129923	115688	10.96%
599858	300204	156124	139015	10.96%
699807	349884	181636	161655	11.00%
799737	399746	207263	184543	10.96%
899686	449964	233671	208017	10.98%
999613	499404	259188	230813	10.95%
				10.98%

Table 4 shows in columns "RB⁺" and "RB" the numbers of delete operations performed without using any maintenance operation by RB and RB⁺respectively. Column "(RB - RB⁺) /RB" gives the gain in percentage. The number of delete operations performed without maintenance operations is reduced by a factor of about 6.07 % on average. To delete/insert 250 082 items in a tree with 499 909 nodes (the underlined row in Table 4), RB performs 158 929 delete operations without using maintenance operations while RB⁺ performs 169 137. In other words, with the new delete algorithm, 10 208 additional delete operations will not require any maintenance operation.

Table4: Delete operations without maintenance operations - RB versus RB⁺

Tree size	Oper	RB	RB⁺	(RB-RB⁺)/RB
99996	50160	31784	33874	6.17%
199986	100102	63537	67659	6.09%
299966	149845	95337	101461	6.04%
399943	200059	127291	135488	6.05%
499909	250082	158929	169137	6.04%
599858	300204	190686	203011	6.07%
699807	349884	222315	236707	6.08%
799737	399746	254180	270536	6.05%
899686	449964	285837	304316	6.07%
999613	499404	317284	337685	6.04%
				6.07%

Rotations

Having a tree differently colored will certainly affect the number of rotations to be made. Table 5 shows in columns "RB⁺" and "RB" the numbers of rotations performed by RB⁺ and RB respectively.

Table5: Rotations – RB versus RB ⁺

Tree size	Oper	RB	RB⁺	(RB-RB⁺)/RB
99996	50160	19879	19688	0.96%
199986	100102	39563	39180	0.97%
299966	149845	58854	58260	1.01%
399943	200059	78719	78000	0.91%
499909	250082	98709	97742	0.98%
599858	300204	118612	117453	0.98%
699807	349884	137686	136309	1.00%
799737	399746	157220	155706	0.96%
899686	449964	177549	175869	0.95%
999613	499404	196938	195011	0.98%
				0.97%

Column "(RB – RB⁺)/RB" gives this gain in percentage. Although the gain is minor, since it is about 0.97% on average, the proposed algorithm reduces the number of rotations.

4.2 Deep analysis on the new codes

To properly compare in more details the two delete algorithms, we conducted statistical work on the various cases of the deletion algorithm that are applied when items are removed from an existing tree. We first show that both cases 2 and 3 cover an important percentage of total cases. Then, we find the satisfiability rates of the added tests: α₁, α₂ and β as defined in the previous section. Finally, we present a simulation program showing that the new proposed codes (Figure 5, right side) run faster than the codes of the standard algorithm (Figure 5, left side).

Distribution of maintenance operations

We studied for RB and RB⁺ how the maintenance operations are distributed over the four cases to determine the corresponding percentages in relation to the total number of cases.

For the standard delete algorithm, when items are randomly removed from a Red-black tree, the distribution of maintenance operations is, on average, as follows: cases 1, 2, 3 and 4 occur with 40.71%, 28.00%, 16.61% and 14.69% of total cases respectively. Note that both cases 2 and 3 cover 44.61%. For the new delete algorithm, the distribution is, on average, as follows: 33.94%, 32.16%, 18.39% and 15.51%. Thus, cases 2 and 3 together cover 50.55%.

Recall that in case 2, the standard delete algorithm performs one rotation always followed by three color changes while the new delete algorithm performs one rotation possibly followed by one or three color changes. As case 2 is more frequent with the new algorithm (32.16% on average versus 28.00% in the standard algorithm), so there are far fewer color changes.

Likewise, for case 3, the standard delete algorithm performs two rotations always followed by two color changes while the new delete algorithm also performs two rotations possibly followed by one or two color changes. As case 3 is more frequent with the new algorithm (18.39% on average versus 16.61% in the standard algorithm), so there are less color changes.

Finding α1, α2 and β

To determine α₁ and α₂, it suffices to find the distribution of sub cases inside case 2 of RB⁺.

We determined by simulation:

- Nb_case2: the total number of cases 2 performed when items are inserted into or deleted from a Red-Black tree previously built.

- Nb_Case2_a: the number of times the first test of case 2 is true (see Figure 5). It is also the number of times where only one color change is performed.

-NB_Case2_b: the number of times the first test of case 2 is false but the second test of case 2 is true, i.e. the number of times where three color changes are performed.

"α₁" and "α₂" are then the ratios (Nb_Case 2_a / Nb_Case2) and (Nb_Case2_b /Nb_ Case2) respectively.

Our simulation results give α₁ = 29.79% and α₂ = 29.31%. This means that, on average, for 29.79% of case 2, only one color change is performed per operation and for 29.31% of case 2 three color changes are performed per operation. This implies that for about 40.9% (100% – (29.79% + 29.31%)) of case 2, no color change is made.

As an example from our simulation tests, to delete/insert 250 082 items in a tree with 499 909 nodes, Case 2 occurs 37 156 times. For 11 084 cases, only one color change is performed. For 10 853 cases, three color changes are performed. Thus, in total 43 643 (11 084 + 10 853 X 3) color changes are performed. For the rest, i.e. 15 219 (37 156 – (11 084 + 10 853)), no color change is made. Another way to estimate the number of color changes is to apply formula C₂ (α₁ + 3 α₂) (see Table 1) where C₂ is the number of occurrences of case 2. Indeed, 37 156 X (29.79% + 3 X 29.31%) gives 43 740 color changes, which is close to 43 643.

Similarly, to determine β it suffices to find the distribution of sub cases inside the case 3 of RB⁺.

We also determined by simulation:

- Nb_Case3: the total number of cases 3 achieved when items are inserted into or deleted from a Red-black tree previously built.

- Nb_Case3_a: the number of times the unique test in case 3 is true (see Figure 5). It is also the number of times where two color changes are performed.

"β" is then the ratio (Nb_Case3_a / Nb_Case3).

Our simulation results give β = 73.84%. This means that for 73.84% of case 3 on average two color changes are performed per operation. This implies that for about 26.16% (100%-73.84%) of case 3, only one color change is made.

Likewise, as an example from our simulation tests to find, to delete/insert 250 082 items in a tree with 499 909 nodes, case 3 occurs 21 341 times. For 15 770 cases, two color changes are performed. For the rest, i.e. 5 571 (21 341 – 15 770), only one color change is made. The total number of color changes is then 37 111 (2 X 15 770 + 5 571). This can also be estimated by formula C₃ (1 + β) (see Table 1). Indeed, 21 341 X (1+ 0.7384) gives 37 099 which is near to 37 111. C₃ being the number of occurrences of case 3.

RB codes versus RB ⁺ codes

Once values α₁, α₂ and β are known, we can now show that RB⁺ codes of cases 2 and 3 (see Figure 5) are faster than the corresponding RB codes. Indeed, this allows us to evaluate the compromise "Adding test -Reducing color changes" and the use of simple and read-dependent writes in the codes.

For case 2, we just need to apply the following experiment (EXP2) in which "RB code for case 2", "RB⁺ code for case 2", "RB code for case 3", "RB⁺ code for case 3" are described in Figure 5.

1. Create a binary search tree rooted at P with a left child X (supposed a doubly black node) and a right child S. Add also to node S a left child Ls and a right child Rs.

2. Run the code {Assign any color to P and Ls; RB code for case 2} C₂ times.

3. Run the RB ⁺ code for case 2 M times but in three steps as follows:

(a) Run the code {Assign color Black to P and color Red to Ls; RB ⁺ code for case 2} α₁ C₂ times.

(b) Run the code {Assign color Red to both P and Ls; RB ⁺ code for case 2} α₂ C₂ times.

(c) Run the code {Assign color Red to P and color Black to Ls; RB ⁺ code for case 2} (1- α₁- α₂) C₂ times.

4. Compute the time consumed by the RB and RB ⁺ codes for case 2.

5. Repeat 2 – 4 three times for C ₂ = 10 000 000 to 100 000 000 by step of 10 000 000 nodes.

Likewise, for case 3, we use the same algorithm except that C₃ replaces C₂ and case 3 replaces case 2 and in 3 the three steps are replaced by the two following steps:

(a) Run the code {Assign color Red to P and any color to Ls; RB ⁺ code for case 3 } β C₃ times

(b) Run the code {Assign color Black to P and any color to Ls; RB ⁺ code for case 3 } (1-β) C₃ times

Note that color assignments before codes allow tests to be true or false.

RB code for case 2 versus RB⁺ code for case 2

Table 6 gives the running times in milliseconds consumed by the RB code for case 2 (Column "RB") and by the RB⁺ code for case 2 (Column "RB⁺"). Column "(RB-RB⁺)/RB" shows the gain in percentage. As the table shows it, this gain is very important since it is close to 30.81% on average. This confirms well our expectation, i.e. adding tests to reduce color changes is preferable to perform directly color changes.

Table6: Case 2 – RB code versus RB⁺ code - Running time

C₂ X 10²	RB	RB⁺	(RB-RB⁺)/RB
100000	155	109	29.74%
200000	296	203	31.34%
300000	447	312	30.22%
400000	609	411	32.49%
500000	739	515	30.32%
600000	890	615	30.91%
700000	1036	729	29.67%
800000	1174	812	30.83%
900000	1343	927	30.98%
1000000	1484	1016	31.55%
			30.81%

RB code for case 3 versus RB⁺ code for case 3

Table 7 gives the running times in milliseconds consumed by the RB code for case 3 (Column "RB") and by RB⁺ code for case 3 (Column "RB⁺"). Column "(RB-RB⁺)/RB" shows the gain in percentage. A 5.04% gain is completed by the new code of case 3.

Table7: Case 3 – RB code versus RB⁺ code - Running time

C₃ X 10²	RB	RB⁺	(RB-RB⁺)/RB
100000	125	118	5.60%
200000	249	235	5.62%
300000	359	344	4.18%
400000	499	468	6.21%
500000	609	578	5.09%
600000	734	703	4.22%
700000	860	811	5.70%
800000	968	937	3.20%
900000	1108	1047	5.51%
1000000	1218	1156	5.09%
			5.04%

4.3 Recapitulation

To sum up, Table 8 recapitulates test results with the average values. When values are prefixed by sign "+", it is in favor of the new delete algorithm. When values are prefixed by sign" –", it is in favor of the standard delete algorithm.

Table8: Result recapitulation

Main contributions
Color changes	+ 29%
Rotations	+ 0.97%
Maintenance operations	+ 10. 98%
Deletions without maintenance operations	+ 6.07%
RB codes versus RB⁺ codes
RB case distribution	40,71%	28,00%		16,61%		14,69%
RB⁺ case distribution	33.94%	32.16%		18.39%		15.51%
RB⁺ case 2 distribution	α1=29.79% α2=29.31%
RB⁺ case 3 distribution	β = 73.84%
RB case 2 versus RB⁺ Case 2 - Time	+ 30,81%
RB case 3 versus RB⁺ case 3 - Time	+ 5.04%
Impact on insert algorithm
Color changes (Insert algorithm)	-7.17%
Rotations(Insert algorithm)	-1.32%
Maintenance operations (Insert algorithm)	- 6.21%
Insertions without maintenance operations (Insert algorithm)	- 7.96%
Cascading in the insert algorithm
Case distribution – Insert algorithm with RB	48.81%		25.46%		25.73%
Case distribution – Insert algorithm with RB⁺	51.32%		24.23%		24.45%
Cascade length - Insert algorithm with RB	1.42
Cascade length - Insert algorithm with RB⁺	1.36
Overall effects
Color changes (Insert and delete algorithms)	+8.79%
Rotations (Insert and delete algorithms )	-0.32%
Overall time (Insert and delete algorithms)	+ 4.04%
Time of an operation ( insert or delete algorithm)	+ 0.29µs
Impact on search algorithm
Search algorithm – Largest difference	0.001677

Main contributions and performance of the RB ⁺ code compared to the RB code

The main contributions of the proposed delete algorithm can be summarized in what follows. A substantial gain in color changes is observed since this gain is about 29%. Results also reveal that the new coloring of the tree implies a diminution of the number of maintenance operations by a factor of 10.98%. Moreover, the new delete algorithm includes two advantages. Case 1 is less frequent (33.94% in RB⁺ versus 40.71% in RB) and case 2 is more frequent (32.16% in RB⁺ versus 28% in RB).The former reduces cascading effects since these can be triggered only by this case. The latter decreases color changes. Another advantage of the new algorithm lies in the fact that there are more delete operations (6.07%) that are performed without maintenance operations compared to the standard algorithm. The new coloration of the tree also implies a slight decrease in rotations. Indeed, a gain of about 0.97% is observed.

The price to pay for these advantages is the addition, in the standard algorithm, of only two tests in case 2 and one test in case 3. Recall that both cases 2 and 3 cover 44.61% and 50.55% for RB and RB⁺ respectively. Our deep analysis allowed us to determinate le percentage of cases on the total number of case 2 for which only one color change is performed per operation (α1=29.79%) and the one for which three color changes are performed per operation(α2=29.31%). This implies that for about 40.9% of case 2, no color change is made.

Our deep analysis also allowed us to determinate le percentage of cases on the total number of case 3 for which only two color changes are performed per operation (β = 73.84%.)

This implies that for about 26.16% of case 3, only one color change is made. On the basis of α1, α2 and β parameters, the simulation results revealed that the "Adding test-Reducing color changes" tradeoff is interesting since the RB⁺ code for case 2 saves 30.81% of running time compared to the corresponding RB code and the RB⁺ code for case 3 saves 5.04% of running time compared to the corresponding RB code.

Consequences on insert process and overall effects

As we pointed out before, we studied the impact of the new tree coloring - involved in the proposed delete algorithm - on the insert and search operations. The impact on overall effects was also studied. For space reasons we omited simulation tables. Below, we report some simulation results (Table 8).

In order to study the impact of the proposed delete algorithm on the insert algorithm we measured the same parameters. The insert algorithm used with RB⁺ generates 7.17% more color changes and 1.32% more rotations. Moreover, it increases maintenance operations by a factor of 6.21% and decreases the insert operations performed with maintenance operations by a factor of 7.96%. Certainly, these are not convenient. However, the proposed delete algorithm offers an attractive tradeoff between its advantages and the drawbacks of the insert algorithm used in conjunction with it.

To prove that the new delete algorithm does not deteriorate the insert process, we computed the average length of the cascade involved in case 1. First, we analyzed case distributions of the insert algorithm when it is used with RB and RB⁺. Case 1 occurs 48.81% of total cases when RB is used and 51.32% when RB⁺ is used. Case 1 then covers about 50% of maintenance operations. It was not expected that cascading in the insert algorithm would be shorter when the new delete algorithm is used. Indeed, the cascade length is close to 1.42 when RB is used and it is close to 1.36 when RB⁺ is used.

Let us consider an insert operation regardless of the delete algorithm used to remove items from a Red-Black tree. When an item is inserted into a Red-Black tree, either it requires a maintenance operation or not. If it requires such an operation, one of the three cases of the insert algorithm is performed. For case 2 one rotation and two color changes are performed and for case 3 two rotations and two color changes are performed (Red-Black tree properties). On the contrary, in case 1, the number of color changes depends on the length of the cascade. As the latter is shorter when RB⁺ is used, the insert algorithm should be then more efficient. The only drawback is that the insert algorithm used with RB ⁺ performs more the case 1 (51.32% against 48.81%). In contrast, the frequencies of cases 2 and 3 are slightly lower. Indeed, for case 2, we have 24.23% of total cases for RB against 25.46% for RB⁺ and for case 3, we have 24.45% of total cases for RB against 25.73% for RB⁺.

Of course, these improvements have an impact on the running time. Indeed, test results show an overall gain in running time of about 4.04% and a gain of about 0.29 microseconds per operation (insert/delete). This confirms well that the new delete algorithm works well with the insert process. Note also that, overall, there is an 8.79% gain in the total number of color changes performed by both the insert algorithm and RB⁺ and only a 0.32% loss in the total number of rotations performed by both the insert algorithm and RB⁺.

Furthermore, the new coloring of the tree resulting from the proposed delete algorithm does not deteriorate search performance. Indeed, the average lengths of paths of trees generated by the two delete algorithms are almost the same. The largest observed difference is about 0.001677.

In this paper, we exposed a variation of the Red-Black tree delete algorithm. We presented, in particular, the new transformations and then we showed their validity. The new delete algorithm avoids three color changes in one case and colors differently in another case. Thus, the resulting Red-Black tree is differently colored compared to the standard one. Benchmark results show essentially a 29% decrease in color changes and 10-11% reduction in maintenance operations. As a consequence, the proposed algorithm saves running time since it is reduced by a factor of about 4% compared to the standard algorithm while conserving search and insert performance of the standard algorithm. The proposed algorithm leads, a priori, to performance improvements to all applications of Red-Black trees.

The authors declare no competing interests.

Acknowledgments

We would like to express special thanks to my dear colleague Pr W.K HIDOUCI for his advice and helpful comments and suggestions.

[1] GUIBAS, L.J. and SEDGEWICK R (1978) “A dichromatic framework for balanced trees”. Proceedings of the 19th Annual Symposium on Foundations of Computer Science (1978).

[2] SEDGEWICK R. (2004)]: “Fundamentals data structures”. Addison – Wesley. 13th Printing.

[3] BRASS P. (2008]: “Advanced data structures”. Cambridge University Press.

[4] DROZDEK, A. (2001) “Data structures and algorithms in C++”. Brooks/Cole.

[5] BAYER, R (1972) “Symmetric Binary B-Trees”: Data structure and maintenance algorithms. Acta Informatica 1(4):290-306, 1972.

[6] ADEL’son - VELSKII, G. M., and Y. M. LANDIS (1962) “An algorithm for the organization of information”. Dokl. Akad. Nauk SSSR 146, pp. 263-266. English translation in Soviet Math. Dokl. 3, pp. 1259-1262.

[7] SEDGEWICK R. (2008): “Left leaning Red Black trees." http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

[8] ANDERSON A. (1993) “Balanced Search trees made simple”. Workshop on algorithms and data structures, pages 60-71, Springer Verlag.

[9] Sleator, Daniel D.; Tarjan, Robert E. (1985) "Self-Adjusting Binary Search Trees", Journal of the ACM 32 (3): 652–686,

[10] Galperin, Igal; Rivest, Ronald L. (1993), "Scapegoat trees", Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms: 165–174, http://portal.acm.org/citation.cfm?id=313676

[11]HEGER, D.A (2004] “A disquisition on the performance behavior of binary search tree data structures”. Upgrade: the European journal for the informatics professional. Vol V, N° 5, pp. 67-76. October 2004.

[12] HAEUPLER, Bernhard, SEN, Siddhartha, et TARJAN, Robert E (2015). Rank-balanced trees. ACM Transactions on Algorithms (TALG), vol. 11, no 4, p. 30.

[13] Ben Plaff. "Performance Analysis of BSTs in system software". SIGMETRICS 2004: 410-411.

[14] Svetlana Štrbac-Savić; Milo Tomašević. "Comparative performance evaluation of the AVL and red-black trees". BCI '12 Proceedings of the Fifth Balkan Conference in Informatics. Pages 14-19. ACM New York, NY, USA.

[15] Liang Qiaoyu, Li Jianwei, Xu Yubin. "Performance Analysis of Data Organization of the Real-Time Memory Database Based on Red-Black Tree". CCIE '10: Proceedings of the 2010 International Conference on Computing, Control and Industrial Engineering - Volume 01 , June 2010. IEEE Computer Society.

[16] Aravind Natarajan, Lee Savoie, Neeraj Mittal. "Brief announcement: concurrent wait-free red-black trees". DISC'12: Proceedings of the 26th international conference on Distributed Computing. October 2012. Springer-Verlag

Improving the Red-Black tree delete algorithm

Status:

Version 1

Abstract

Figures

1. Introduction

2. Red-black Trees

3. Improving The Red-black Trees Delete Algorithm

4. Simulation Results

4.1 Main contributions

4.2 Deep analysis on the new codes

4.3 Recapitulation

5. Conclusion

Declarations

Acknowledgments

References

Status:

Version 1