Red–black tree

A red-black tree (English red-black tree or RB tree ) is in the computer science derived from a binary search tree data structure, which guarantees very fast access to the values ​​stored in it. Red -black trees were first described in 1972 by Rudolf Bayer, which she called symmetric binary B -trees. The present name dates back to Leo J. Guibas and Robert Sedgewick, 1978, the red- black color convention introduced. The fast access times to the individual stored in the red-black tree elements are achieved by three demands, which together guarantee that a red-black tree is always balanced, so that the height of a red-black tree with n values ​​never greater than will. Thus, the most important operations can in search trees - are guaranteed to run in O ( n log ) - search, insert and delete.

Definition

In addition to the properties of the binary search tree, each node of the Red-Black tree is another attribute called color, with two values ​​, referred to as red and black. This coloring has to meet the following three requirements:

The latter uniform number of black nodes on paths is called the black depth of the tree. It should be in this article, the existing on each path and always a black NIL node is not counted, just as at the tree level.

These three most important quality requirements of red-black trees ensures: the number of nodes on a longest path from the root to a leaf is never more than twice as high as the number of nodes in a shortest path from the root to a sheet. This is a red-black tree is always roughly balanced. This is looking for the operations, insert and delete important as their runtime costs are proportional to the height of the tree. Since the amount of a red-black tree in that it is approximately balanced, is minimized, thus the term of the above-mentioned operations, is also minimized. Thus, one can look for red -black trees is an upper bound for the duration of the operations insert and delete guarantee.

In order to understand how these three requirements limit the height upwards, it is sufficient to demonstrate that two red nodes may follow each other due to the second requirement on any path, so there may be more red than black nodes on any path while on the shortest path in the extreme case, only black nodes are present. Since the third requirement specifies, however, that the number of black nodes must be the same on all paths, the path may be, on each of which a red alternating with a black node, at most twice as long as the path on which only black nodes are. A formal proof of this property of the red-black tree can be found at height evidence later in the article.

Note: This article takes up the article Binary search tree outlined in the Figure 2 and extremely common in red-black trees perspective, in which the internal nodes of the keys bear ( " node-centric storage ") and the ( external ) leaves as a wildcard function for the intervals between the keys ( see also fig with the example tree). Here, the key -bearing nodes have exactly two children, and the leaves without search key (so-called NIL - leaves) wear the color black. This view allows to use fewer case distinctions, and simplifies the description of the algorithm. But you prejudged the implementation does not really.

Operations

Search

The search operation inherit red -black trees of the general binary search trees. A detailed description of the algorithm is to be found there.

The insertion in the red-black tree works like inserting into a binary search tree. The new node is colored red so that the black depth of the tree is preserved. After insertion, the second requirement of the red-black tree can be injured. Therefore, it may be necessary to repair the tree. A distinction total of five cases which are considered in more detail below.

Note: If the following from Father (P for parent), grandfather (G for grandparent ) and uncle (U for uncle ) is mentioned, these are relative to each newly inserted node (N ) can be seen.

Showing a piece of C- code is given in each of the five cases, which shows how the resulting tree is being repaired.

The grandfather and the uncle of a node can be determined as follows:

Grandparent node (node ​​n ) {       return n- > parent - > parent;   }     uncle node (node ​​n ) {       if ( n- > parent == grandparent (s) - > left )           return grandparent (s) - > right;       else           return grandparent (s) - > left;   } Case 1: The newly inserted node is the first in the tree.

Void insert_case1 (node ​​n ) {       if ( n- > parent == NULL)           n -> color = BLACK;       else           insert_case2 (s);   } As noted above, a red root without damage is immediately changed color from red to black.

Case 2: The father of the new node is black.

This could be the third requirement be violated because the new node itself again brings two black NIL node, and thus the black depth is increased to one of the paths by one.

Since the inserted node itself but is red, and has replaced a black NIL node when pasting, the black depth remains on all paths obtained, and it is nothing to do.

Void insert_case2 (node ​​n ) {       if ( n- > parent - > color == BLACK)           return; / * All claims of the tree are still met * /       else           insert_case3 (s);   } Note: In the following cases can now be assumed that the node being inserted has a grandfather because his father is red, and thus can not be the root itself. But since it is a binary tree with a red-black tree, the grandfather of a child has definitely still (even though it may be at this a NIL node).

Case 3: Both the uncle and the father of the new node are red.

In this case, one can both nodes simply black color, and color in turn, the grandfather red, making the third demand is restored. By this action, the problem is shifted by two levels upwards, as by the now red-colored grandfather the second requirement could be violated, so the grandfather must be considered now. This procedure is continued recursively continues until all demands are met.

Void insert_case3 (node ​​n ) {       if (! uncle (n) = NULL && uncle (s) - > color == RED) {           n- > parent -> color = BLACK;           uncle (s) -> color = BLACK;           grandparent (s) -> color = RED;           insert_case1 ( grandparent (s) );       }       else           insert_case4 (s);   } Note: In both cases, the remaining is assumed for simplicity that the father node, the left child of its parent (ie, the grandfather of the inserted node ) is. Should he be the right child of his father, so must be reversed in the following two cases the left and right. The sample code takes this case already.

Case 4: The new node has a black or no uncle and is the right child of his father's red while the father but left sitting on grandfather.

In this case, one can perform a left rotation by the father, which interchanges the role of the inserted node and its father. Then you can edit the former parent node with the help of the fifth case. Due to the rotation outlined above, a path has been changed (in the picture labeled 1 ) that he now performs an additional node, while another path was changed (in the picture with 3 marks ) so that it now has a node less. However, since it is red knots in both cases, persists at the Black Depth nothing to the third requirement is met.

Void insert_case4 (node ​​n ) {       / / node is the right of the father and father left the grandfather       if ( n == n- > parent - > right && n- > parent == grandparent (s) - > left ) {           rotate_left (n- > parent );           n = n- > left;       / / node is left of the father and grandfather on the father's right       } Else if ( n == n- > parent - > left && n- > parent == grandparent (s) - > right ) {           rotate_right (n- > parent );           n = n- > right;       }       insert_case5 (s);   } Case 5: The new node has a black uncle and is the left child of his father's red. The father left depends on the grandfather. Case 5: The new node has a black or no uncle and is the left child of his father's red; the father depends also on the left side grandfather.

In this case, one can perform a right rotation around the grandfather, so the original father is now the father of both the newly inserted node and the former grandfather. Since the father was red, must according to the second requirement ( No red node has a red child) the grandfather be black. We interchange the colors of the now former grandfather or father, the second requirement is again satisfied in the resulting tree. The third requirement is also fulfilled, since all paths that run through one of these three nodes, previously ran by the grandfather and now all run by the former father of the now - is the only one of the three black nodes - such as the grandfather before transformation.

Void insert_case5 (node ​​n ) {       n- > parent -> color = BLACK;       grandparent (s) -> color = RED;       / / node is left of the father and father left the grandfather       if ( n == n- > parent - > left && n- > parent == grandparent (s) - > left ) {           rotate_right ( grandparent (s) );       / / node is the right of the father and grandfather on the father's right       Else { }           / * From here applies, n == n- > parent - > right and n- > parent == grandparent (s) -> right * /           rotate_left ( grandparent (s) );       }   } delete

Deleting a node from a red-black tree is analogous to deleting a node from binary trees. If the node to be deleted has two children ( no NIL node), so you are looking for either the largest value in the left subtree or the smallest value in the right subtree of the deleted node copies this value to the actual node to be deleted, and removes the found node from the red-black tree. Since the found node can have more than one child, because its value would not otherwise have been maximum or minimum, as can be simplified to the deletion of a node with at most one child's problem.

Note: In the following we will therefore only consider nodes with more than a real child, and this child is an ' his child '. If the node has no real children, is one of the two NIL nodes play the role of the child.

If you want to delete a red node, so you can replace it with his child, which according to the second requirement ( No red node has a red child) must be black. As the father of the deleted node for the same claim must also have been black, the second requirement is thus no longer violated. Since all paths that originally ran through the deleted node red, now run by a red node less changes on the Black depth is also nothing to the third requirement is met.

Also still easy to solve is the case when the node to be deleted is black, but a red child. If this happens, just the black nodes are deleted, this could be hurt both the second and the third requirement. However, this can be circumvented by the child is black. So make no guarantees two red nodes to each other ( the red may father the deleted node and its red child) and all paths that ran through the deleted black node, now run by his black child, which both requirements remain satisfied.

The above mentioned deletion of a node with a child can be realized by the following program, which replaces the node n means replace_node by the node child.

Void delete_one_child (node ​​n ) {       / * Precondition: n has at most one real child (no NIL node) * /       node child = is_leaf (n- > right )? n- > left: n - > right;       replace_node (s, child);       if ( n- > color == BLACK) {           if ( child - > color == RED)               child -> color = BLACK;           else               delete_case1 ( child);       }       free (s );   } Note: This code assumes that any NIL nodes are represented by actual node and are not simple null pointer.

More difficult to resolve is the case when both the node to be deleted and his child are black. First, we replace the node to be deleted with his child, and then deletes the node. Now, however, violated this Incoming child node, hereafter called conflict node, the demands of a red-black tree, since there is now a path which led by two black nodes before, but now leads by only one. Thus, the third requirement (the number of black node from any node to a leaf is the same on all paths ) fails. Depending on the situation six different cases are now distinguished as the tree is to be repaired again, which are considered in more detail below.

Note: If the following from Father (P for parent), brother (S for sibling ), grandfather (G for grandparent ) and uncle (U for uncle ) is mentioned, as they are to see each relative to the conflict node. This conflict node itself, we call in the diagrams with N. For clarity, is a piece of C code indicated in each of the cases, showing how the resulting tree is repaired.

The brother ( sibling ) of a node can be determined as follows:

Sibling node (node ​​n ) {        if ( n == n- > parent - > left )            return n- > parent - > right;        else            return n- > parent -> left;   } Case 1: The conflict nodes ( N) is the new root. In this case, you are done, as a black node was removed from each path and the new root is black, so that all requirements are still met.

Void delete_case1 (node ​​n ) {       if ( n- > parent == NULL)           return;       else           delete_case2 (s);   } Note: For cases 2, 5 and 6 of the conflict node is (N), the left child of its parent. Should he be the right child, so must be reversed in the three cases left and right. The sample code takes this case already.

Case 2: The brother ( S) of the conflict node is red. In this case, one can invert and then perform a left rotation around his father, which the brother of the conflict node to whose grandfather is the color of the father and the brother of the conflict node. All paths still have the same number of black nodes, but the conflict node now has a black brother and father a red, so you can now go to Case 4, 5, or 6.

Void delete_case2 (node ​​n ) {       if ( sibling ( n ) - > color == RED) {           n- > parent -> color = RED;           sibling (s) -> color = BLACK;           if ( n == n- > parent - > left )               rotate_left (n- > parent );           else               rotate_right (n- > parent );       }       delete_case3 (s);   } Case 3: The father ( P) of the conflict node ( N), his brother (S ) and the children of his brother (SL or SR ) are black Case 3: The father ( P) of the conflict node, his brother (S ) and the children of his brother (SL or SR ) are all black. In this case, you can simply color the red brother, which all paths lead through this brother - which are exactly the paths that do not lead by the conflict node itself - a black nodes have less, thus restoring the original inequality is again balanced. However, all paths that run through the father, now a black node than paths that do not run less by the Father, so that the third requirement is still injured. To fix this, you now trying to repair the father nodes by trying one of the six cases - from Case 1 - apply.

Void delete_case3 (node ​​n ) {       if ( n- > parent - > color == BLACK &&           sibling (s) - > color == BLACK &&           sibling (s) - > left - > color == BLACK &&           sibling (s) - > right - > color == BLACK)       {           sibling (s) -> color = RED;           delete_case1 (n- > parent );       }       else           delete_case4 (s);   } Case 4: Both the brother ( s ) of the conflict node ( N ) and the children of the brother (SL or SR ) are black, but the father ( P) of the conflict node is red Case 4: Both the brother of the conflict node and the children of the brother ( SL and SR ) are black, but the father ( P) of the conflict node red. In this case it is sufficient to swap the color of the father and brother. This keeps the number of black nodes on paths that do not pass through the conflict nodes unchanged, but adds a black nodes on all paths that lead through the conflict node to, and thus resembles the deleted black node on these paths.

Void delete_case4 (node ​​n ) {       if ( n- > parent - > color == RED &&           sibling (s) - > color == BLACK &&           sibling (s) - > left - > color == BLACK &&           sibling (s) - > right - > color == BLACK)       {           sibling (s) -> color = RED;           n- > parent -> color = BLACK;       }       else           delete_case5 (s);   } Case 5: The left child (SL) of brother (S ) is red, the right child (SR ) and the brother ( s ) of the conflict node ( N), however, are black and the conflict node itself is the left child of its parent (P ) Case 5: The left child (SL) of brother (S ) is red, the right child (SR ) as well as the brother of the conflict node ( N), however, are black and the conflict node itself is the left child of its parent. In this case, one can perform a right rotation about the brother, so the left child (SL ) of the brother whose father is new, and so is the brother of the conflict node. Then we interchange the colors of his brother and his new father. Now all paths still have the same number of black nodes, but the conflict node has a black brother whose right child is red, which you can now go on to the sixth case. Neither the conflict node itself nor his father are affected by this transformation.

Void delete_case5 (node ​​n ) {       if ( n == n- > parent - > left &&           sibling (s) - > color == BLACK &&           sibling (s) - > left - > color == RED &&           sibling (s) - > right - > color == BLACK)       {           sibling (s) -> color = RED;           sibling (s) - > left -> color = BLACK;           rotate_right ( sibling (s) );       }       else if ( n == n- > parent - > right &&                sibling (s) - > color == BLACK &&                sibling (s) - > right - > color == RED &&                sibling (s) - > left - > color == BLACK)       {           sibling (s) -> color = RED;           sibling (s) - > right -> color = BLACK;           rotate_left ( sibling (s) );       }       delete_case6 (s);   } Case 6: The brother ( S) of the conflict node ( N) has black, the right child of the brother (SR ) red color, and the conflict node itself is the left child. The two white nodes P and S shown are the same color, red or black. Case 6: The brother ( S) of the conflict node ( N) is black, the right child of the brother (SR ) red and the conflict node itself is the left child of its parent. In this case, one can perform a left rotation around the father of the conflict node, such that S is grandfather of N. Now it is enough to replace the colors of S and P and SR to dye black. N still has the same color, so that the second requirement is fulfilled. But N now has another black ancestors: If P was not black before the transformation, he is black after the transformation, and if P was already black, so the conflict node now has S as a black grandfather, so the paths passing through the conflict node running now pass an additional black node.

In pathways that change and run the not by the conflict nodes ( N), there are two options:

• The path runs through his new brother (3). Then the path must run both before and after the transformation by S and P. Since the two nodes but have just exchanged their colors change on the black depth on the path nothing.
• The path runs through the new uncle (SR ) of N, which is the right child of the brother (S). In this case the path was before both S P and SR. After the transformation, but he only goes by (S) himself, who has taken on the color of P, and SR, which was recolored from red to black. So nothing has changed on the black depth of such a path.

In both cases, the number of black nodes does not change on the paths: the second demand is restored.

Void delete_case6 (node ​​n ) {       sibling (s) -> color = n- > parent - > color;       n- > parent -> color = BLACK;       if ( n == n- > parent - > left ) {           / * Here, sibling ( n ) - > color == BLACK &&                    sibling (s) - > right - > color == RED * /           sibling (s) - > right -> color = BLACK;           rotate_left (n- > parent );       }       else       {           / * Here, sibling ( n ) - > color == BLACK &&                    sibling (s) - > left - > color == RED * /           sibling (s) - > left -> color = BLACK;           rotate_right (n- > parent );       }   } level of evidence

As motivated in the introduction, is the special property of red-black trees, that they in logarithmic time - search for an item in the tree, delete or paste - or more precisely in O ( log2 n ), where n is the number of keys. These operations are dependent on all binary search trees of the height h of the tree. Now, the lower the height of the tree, the faster the operation. Can we prove now that a binary search tree with n elements (in the case of the red-black tree 2 log2 ( n 2) -2) never exceeds a certain level, then one has proved that the above operations in the worst case have logarithmic costs, namely the costs presented by 2 log2 ( n 2) -2) stored for a tree in the n elements. Thus, it must be shown that the following statement is true:

The height h of a red-black tree that stores n key applies: h ≤ 2 log2 ( n 2 ) -2.

Preliminary remark:

Minimum number of nodes in a straight Height: If h is even, then there is a red-black tree of height h with nodes and no less. His black depth.

Proof of just height:

Minimum number of nodes with an odd height: If h is odd, then there is a red-black tree of height h with nodes and no less. His black depth.

Proof for odd height:

Because we have for odd h, the inequality

So that for all (even and odd) h

Results.

Since mh is the smallest number of nodes n is for all red-black trees of height h, then:

If at this point still the summand -2 to the other side and logarithms, as follows:

Thus the assertion follows, that a red-black tree has a maximum height h of, and thus seek operations, insert and delete in logarithmic time can do. Expressing this result in the O notation, so is obtained for the costs of the above operations that they are all in O ( log n) lie with n as the number of keys.

Other Trees

• 2-3 4- tree
• AVL tree
• B- tree
• Heap (data structure )
• Search tree