A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.[2] Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently. The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.[3] Tracking the color of each node requires only 1 bit of information per node because there are only two colors. The tree does not contain any other data specific to its being a red–black tree so its memory footprint is almost identical to a classic (uncolored) binary search tree. In many cases, the additional bit of information can be stored at no additional memory cost. Contents 1 History 2 Terminology 3 Properties 4 Analogy to B-trees of order 4 5 Applications and related data structures 6 Operations 6.1 Insertion 6.2 Removal 7 Proof of asymptotic bounds 8 Set operations and bulk operations 9 Parallel algorithms 10 Popular culture 11 See also 12 References 13 Further reading 14 External links History[edit]
In 1972, Rudolf Bayer[4] invented a data structure that was a special
order-4 case of a B-tree. These trees maintained all paths from root
to leaf with the same number of nodes, creating perfectly balanced
trees. However, they were not binary search trees. Bayer called them a
"symmetric binary B-tree" in his paper and later they became popular
as 2-3-4 trees or just 2-4 trees.[5]
In a 1978 paper, "A Dichromatic Framework for Balanced Trees",[6]
An example of a red–black tree In addition to the requirements imposed on a binary search tree the following must be satisfied by a red–black tree:[16] Each node is either red or black. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis. All leaves (NIL) are black. If a node is red, then both its children are black. Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: the number of black nodes from the root to a node is the node's black depth; the uniform number of black nodes in all paths from root to the leaves is called the black-height of the red–black tree.[17] These constraints enforce a critical property of red–black trees: the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf. The result is that the tree is roughly height-balanced. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red–black trees to be efficient in the worst case, unlike ordinary binary search trees. To see why this is guaranteed, it suffices to consider the effect of properties 4 and 5 together. For a red–black tree T, let B be the number of black nodes in property 5. Let the shortest possible path from the root of T to any leaf consist of B black nodes. Longer possible paths may be constructed by inserting red nodes. However, property 4 makes it impossible to insert more than one consecutive red node. Therefore, ignoring any black NIL leaves, the longest possible path consists of 2*B nodes, alternating black and red (this is the worst case). Counting the black NIL leaves, the longest possible path consists of 2*B-1 nodes. The shortest possible path has all black nodes, and the longest possible path alternates between red and black nodes. Since all maximal paths have the same number of black nodes, by property 5, this shows that no path is more than twice as long as any other path. Analogy to B-trees of order 4[edit] The same red–black tree as in the example above, seen as a B-tree. A red–black tree is similar in structure to a
^ Using Knuth's definition of order: the maximum number of children Applications and related data structures[edit]
Red–black trees offer worst-case guarantees for insertion time,
deletion time, and search time. Not only does this make them valuable
in time-sensitive applications such as real-time applications, but it
makes them valuable building blocks in other data structures which
provide worst-case guarantees; for example, many data structures used
in computational geometry can be based on red–black trees, and the
struct node *parent(struct node *n) return n->parent; struct node *grandparent(struct node *n) struct node *p = parent(n); if (p == NULL) return NULL; // No parent means no grandparent return parent(p); struct node *sibling(struct node *n) struct node *p = parent(n); if (p == NULL) return NULL; // No parent means no sibling if (n == p->left) return p->right; else return p->left; struct node *uncle(struct node *n) struct node *p = parent(n); struct node *g = grandparent(n); if (g == NULL) return NULL; // No grandparent means no uncle return sibling(p); void rotate_left(struct node *n) struct node *nnew = n->right; assert(nnew != LEAF); // since the leaves of a red-black tree are empty, they cannot become internal nodes n->right = nnew->left; nnew->left = n; nnew->parent = n->parent; n->parent = nnew; // (the other related parent and child links would also have to be updated) void rotate_right(struct node *n) struct node *nnew = n->left; assert(nnew != LEAF); // since the leaves of a red-black tree are empty, they cannot become internal nodes n->left = nnew->right; nnew->right = n; nnew->parent = n->parent; n->parent = nnew; // (the other related parent and child links would also have to be updated) Diagram notes The label N will be used to denote the current node in each case. At the beginning, this is the insertion node or the replacement node and a leaf, but the entire procedure may also be applied recursively to other nodes (see case 3). P will denote N's parent node, G will denote N's grandparent, S will denote N's sibling, and U will denote N's uncle (i.e., the sibling of a node's parent, as in human family trees). In between some cases, the roles and labels of the nodes are shifted, but within each case, every label continues to represent the same node throughout. In the diagrams a blue border rings the current node N in the left (current) half and rings the node that will become N in the right (target) half. In the next step, the other nodes will be newly assigned relative to it. Red or black shown in the diagram is either assumed in its case or implied by those assumptions. White represents either red or black, but is the same in both halves of the diagram. A numbered triangle represents a subtree of unspecified depth. A black circle atop a triangle means that black-height of that subtree is greater by one compared to a subtree without this circle. Insertion[edit] Insertion begins by adding the node in a very similar manner as a standard binary search tree insertion and by coloring it red. The big difference is that in the binary search tree a new node is added as a leaf, whereas leaves contain no information in the red–black tree, so instead the new node replaces an existing leaf and then has two black leaves of its own added. struct node *insert(struct node *root, struct node *n) // insert new node into the current tree insert_recurse(root, n); // repair the tree in case any of the red-black properties have been violated insert_repair_tree(n); // find the new root to return root = n; while (parent(root) != NULL) root = parent(root); return root; void insert_recurse(struct node *root, struct node *n) // recursively descend the tree until a leaf is found if (root != NULL && n->key < root->key) if (root->left != LEAF) insert_recurse(root->left, n); return; else root->left = n; else if (root != NULL) if (root->right != LEAF) insert_recurse(root->right, n); return; else root->right = n; // insert new node n n->parent = root; n->left = LEAF; n->right = LEAF; n->color = RED; What happens next depends on the color of other nearby nodes. There are several cases of red–black tree insertion to handle: N is the root node, i.e., first node of red–black tree N's parent (P) is black P is red (so it can't be the root of the tree) and N's uncle (U) is red P is red and U is black void insert_repair_tree(struct node *n) if (parent(n) == NULL) insert_case1(n); else if (parent(n)->color == BLACK) insert_case2(n); else if (uncle(n)->color == RED) insert_case3(n); else insert_case4(n); Note that: Property 1 (every node is either red or black) and Property 3 (all leaves are black) always holds. Property 2 (the root is black) is checked and corrected with case 1. Property 4 (red nodes have only black children) is threatened only by adding a red node, repainting a node from black to red, or a rotation. Property 5 (all paths from any given node to its leaves have the same number of black nodes) is threatened only by adding a black node, repainting a node, or a rotation. Case 1: The current node N is at the root of the tree. In this case, it is repainted black to satisfy property 2 (the root is black). Since this adds one black node to every path at once, property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not violated. void insert_case1(struct node *n) if (parent(n) == NULL) n->color = BLACK; Case 2: The current node's parent P is black, so property 4 (both children of every red node are black) is not invalidated. In this case, the tree is still valid. Property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not threatened, because the current node N has two black leaf children, but because N is red, the paths through each of its children have the same number of black nodes as the path through the leaf it replaced, which was black, and so this property remains satisfied. void insert_case2(struct node *n) return; /* Do nothing since tree is still valid */ Note: In the following cases it can be assumed that N has a grandparent node G, because its parent P is red, and if it were the root, it would be black. Thus, N also has an uncle node U, although it may be a leaf in case 4. Note: In the remaining cases, it is shown in the diagram that the parent node P is the left child of its parent even though it is possible for P to be on either side. The code samples already cover both possibilities. Case 3: If both the parent P and the uncle U are red, then both of them can be repainted black and the grandparent G becomes red to maintain property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes). Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent G may now violate Property 2 (The root is black) if it is the root or Property 4 (Both children of every red node are black) if it has a red parent. To fix this, the tree's red-black repair procedure is rerun on G. Note that this is a tail-recursive call, so it could be rewritten as a loop. Since this is the only loop, and any rotations occur after this loop, this proves that a constant number of rotations occur. void insert_case3(struct node *n) parent(n)->color = BLACK; uncle(n)->color = BLACK; grandparent(n)->color = RED; insert_repair_tree(grandparent(n)); Case 4, step 1: The parent P is red but the uncle U is black. The ultimate goal will be to rotate the current node into the grandparent position, but this will not work if the current node is on the "inside" of the subtree under G (i.e., if N is the left child of the right child of the grandparent or the right child of the left child of the grandparent). In this case, a left rotation on P that switches the roles of the current node N and its parent P can be performed. The rotation causes some paths (those in the sub-tree labelled "1") to pass through the node N where they did not before. It also causes some paths (those in the sub-tree labelled "3") not to pass through the node P where they did before. However, both of these nodes are red, so property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not violated by the rotation. After this step has been completed, property 4 (both children of every red node are black) is still violated, but now we can resolve this by continuing to step 2. void insert_case4(struct node *n) struct node *p = parent(n); struct node *g = grandparent(n); if (n == g->left->right) rotate_left(p); n = n->left; else if (n == g->right->left) rotate_right(p); n = n->right; insert_case4step2(n); Case 4, step 2: The current node N is now certain to be on the "outside" of the subtree under G (left of left child or right of right child). In this case, a right rotation on G is performed; the result is a tree where the former parent P is now the parent of both the current node N and the former grandparent G. G is known to be black, since its former child P could not have been red without violating property 4. Once the colors of P and G are switched, the resulting tree satisfies property 4 (both children of every red node are black). Property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) also remains satisfied, since all paths that went through any of these three nodes went through G before, and now they all go through P. void insert_case4step2(struct node *n) struct node *p = parent(n); struct node *g = grandparent(n); if (n == p->left) rotate_right(g); else rotate_left(g); p->color = BLACK; g->color = RED; Note that inserting is actually in-place, since all the calls above use tail recursion. In the algorithm above, all cases are called only once, except in Case 3 where it can recurse back to Case 1 with the grandparent node, which is the only case where an iterative implementation will effectively loop. Because the problem of repair in that case is escalated two levels higher each time, it takes maximally h⁄2 iterations to repair the tree (where h is the height of the tree). Because the probability for escalation decreases exponentially with each iteration the average insertion cost is practically constant. Removal[edit] In a regular binary search tree when deleting a node with two non-leaf children, we find either the maximum element in its left subtree (which is the in-order predecessor) or the minimum element in its right subtree (which is the in-order successor) and move its value into the node being deleted (as shown here). We then delete the node we copied the value from, which must have fewer than two non-leaf children. (Non-leaf children, rather than all children, are specified here because unlike normal binary search trees, red–black trees can have leaf nodes anywhere, so that all nodes are either internal nodes with two children or leaf nodes with, by definition, zero children. In effect, internal nodes having two leaf children in a red–black tree are like the leaf nodes in a regular binary search tree.) Because merely copying a value does not violate any red–black properties, this reduces to the problem of deleting a node with at most one non-leaf child. Once we have solved that problem, the solution applies equally to the case where the node we originally want to delete has at most one non-leaf child as to the case just considered where it has two non-leaf children. Therefore, for the remainder of this discussion we address the deletion of a node with at most one non-leaf child. We use the label M to denote the node to be deleted; C will denote a selected child of M, which we will also call "its child". If M does have a non-leaf child, call that its child, C; otherwise, choose either leaf as its child, C. If M is a red node, we simply replace it with its child C, which must be black by property 4. (This can only occur when M has two leaf children, because if the red node M had a black non-leaf child on one side but just a leaf child on the other side, then the count of black nodes on both sides would be different, thus the tree would violate property 5.) All paths through the deleted node will simply pass through one fewer red node, and both the deleted node's parent and child must be black, so property 3 (all leaves are black) and property 4 (both children of every red node are black) still hold. Another simple case is when M is black and C is red. Simply removing a black node could break Properties 4 (“Both children of every red node are black”) and 5 (“All paths from any given node to its leaf nodes contain the same number of black nodes”), but if we repaint C black, both of these properties are preserved. The complex case is when both M and C are black. (This can only occur when deleting a black node which has two leaf children, because if the black node M had a black non-leaf child on one side but just a leaf child on the other side, then the count of black nodes on both sides would be different, thus the tree would have been an invalid red–black tree by violation of property 5.) We begin by replacing M with its child C. We will relabel this child C (in its new position) N, and its sibling (its new parent's other child) S. (S was previously the sibling of M.) In the diagrams below, we will also use P for N's new parent (M's old parent), SL for S's left child, and SR for S's right child (S cannot be a leaf because if M and C were black, then P's one subtree which included M counted two black-height and thus P's other subtree which includes S must also count two black-height, which cannot be the case if S is a leaf node). Note: In order for the tree to remain well-defined, we need every null leaf to remain a leaf after all transformations (that it will not have any children). If the node we are deleting has a non-leaf (non-null) child N, it is easy to see that the property is satisfied. If, on the other hand, N would be a null leaf, it can be verified from the diagrams (or code) for all the cases that the property is satisfied as well. We can perform the steps outlined above with the following code, where the function replace_node substitutes child into n's place in the tree. For convenience, code in this section will assume that null leaves are represented by actual node objects rather than NULL (the code in the Insertion section works with either representation). void delete_one_child(struct node *n) /* * Precondition: n has at most one non-leaf child. */ struct node *child = is_leaf(n->right) ? n->left : n->right; replace_node(n, child); if (n->color == BLACK) if (child->color == RED) child->color = BLACK; else delete_case1(child); free(n); Note: If N is a null leaf and we do not want to represent null leaves as actual node objects, we can modify the algorithm by first calling delete_case1() on its parent (the node that we delete, n in the code above) and deleting it afterwards. We do this if the parent is black (red is trivial), so it behaves in the same way as a null leaf (and is sometimes called a 'phantom' leaf). And we can safely delete it at the end as n will remain a leaf after all operations, as shown above. In addition, the sibling tests in cases 2 and 3 require updating as it is no longer true that the sibling will have children represented as objects. If both N and its original parent are black, then deleting this original parent causes paths which proceed through N to have one fewer black node than paths that do not. As this violates property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes), the tree must be rebalanced. There are several cases to consider: Case 1: N is the new root. In this case, we are done. We removed one black node from every path, and the new root is black, so the properties are preserved. void delete_case1(struct node *n) if (n->parent != NULL) delete_case2(n); Note: In cases 2, 5, and 6, we assume N is the left child of its parent P. If it is the right child, left and right should be reversed throughout these three cases. Again, the code examples take both cases into account. Case 2: S is red. In this case we reverse the colors of P and S, and then rotate left at P, turning S into N's grandparent. Note that P has to be black as it had a red child. The resulting subtree has a path short one black node so we are not done. Now N has a black sibling and a red parent, so we can proceed to step 4, 5, or 6. (Its new sibling is black because it was once the child of the red S.) In later cases, we will relabel N's new sibling as S. void delete_case2(struct node *n) struct node *s = sibling(n); if (s->color == RED) n->parent->color = RED; s->color = BLACK; if (n == n->parent->left) rotate_left(n->parent); else rotate_right(n->parent); delete_case3(n); Case 3: P, S, and S's children are black. In this case, we simply repaint S red. The result is that all paths passing through S, which are precisely those paths not passing through N, have one less black node. Because deleting N's original parent made all paths passing through N have one less black node, this evens things up. However, all paths through P now have one fewer black node than paths that do not pass through P, so property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is still violated. To correct this, we perform the rebalancing procedure on P, starting at case 1. void delete_case3(struct node *n) struct node *s = sibling(n); if ((n->parent->color == BLACK) && (s->color == BLACK) && (s->left->color == BLACK) && (s->right->color == BLACK)) s->color = RED; delete_case1(n->parent); else delete_case4(n); Case 4: S and S's children are black, but P is red. In this case, we simply exchange the colors of S and P. This does not affect the number of black nodes on paths going through S, but it does add one to the number of black nodes on paths going through N, making up for the deleted black node on those paths. void delete_case4(struct node *n) struct node *s = sibling(n); if ((n->parent->color == RED) && (s->color == BLACK) && (s->left->color == BLACK) && (s->right->color == BLACK)) s->color = RED; n->parent->color = BLACK; else delete_case5(n); Case 5: S is black, S's left child is red, S's right child is black, and N is the left child of its parent. In this case we rotate right at S, so that S's left child becomes S's parent and N's new sibling. We then exchange the colors of S and its new parent. All paths still have the same number of black nodes, but now N has a black sibling whose right child is red, so we fall into case 6. Neither N nor its parent are affected by this transformation. (Again, for case 6, we relabel N's new sibling as S.) void delete_case5(struct node *n) struct node *s = sibling(n); if (s->color == BLACK) /* this if statement is trivial, due to case 2 (even though case 2 changed the sibling to a sibling's child, the sibling's child can't be red, since no red parent can have a red child). */ /* the following statements just force the red to be on the left of the left of the parent, or right of the right, so case six will rotate correctly. */ if ((n == n->parent->left) && (s->right->color == BLACK) && (s->left->color == RED)) /* this last test is trivial too due to cases 2-4. */ s->color = RED; s->left->color = BLACK; rotate_right(s); else if ((n == n->parent->right) && (s->left->color == BLACK) && (s->right->color == RED)) /* this last test is trivial too due to cases 2-4. */ s->color = RED; s->right->color = BLACK; rotate_left(s); delete_case6(n); Case 6: S is black, S's right child is red, and N is the left child of its parent P. In this case we rotate left at P, so that S becomes the parent of P and S's right child. We then exchange the colors of P and S, and make S's right child black. The subtree still has the same color at its root, so Properties 4 (Both children of every red node are black) and 5 (All paths from any given node to its leaf nodes contain the same number of black nodes) are not violated. However, N now has one additional black ancestor: either P has become black, or it was black and S was added as a black grandparent. Thus, the paths passing through N pass through one additional black node. Meanwhile, if a path does not go through N, then there are two possibilities: It goes through N's new sibling SL, a node with arbitrary color and the root of the subtree labeled 3 (s. diagram). Then, it must go through S and P, both formerly and currently, as they have only exchanged colors and places. Thus the path contains the same number of black nodes. It goes through N's new uncle, S's right child. Then, it formerly went through S, S's parent, and S's right child SR (which was red), but now only goes through S, which has assumed the color of its former parent, and S's right child, which has changed from red to black (assuming S's color: black). The net effect is that this path goes through the same number of black nodes. Either way, the number of black nodes on these paths does not change. Thus, we have restored Properties 4 (Both children of every red node are black) and 5 (All paths from any given node to its leaf nodes contain the same number of black nodes). The white node in the diagram can be either red or black, but must refer to the same color both before and after the transformation. void delete_case6(struct node *n) struct node *s = sibling(n); s->color = n->parent->color; n->parent->color = BLACK; if (n == n->parent->left) s->right->color = BLACK; rotate_left(n->parent); else s->left->color = BLACK; rotate_right(n->parent); Again, the function calls all use tail recursion, so the algorithm is in-place. In the algorithm above, all cases are chained in order, except in delete case 3 where it can recurse to case 1 back to the parent node: this is the only case where an iterative implementation will effectively loop. No more than h loops back to case 1 will occur (where h is the height of the tree). And because the probability for escalation decreases exponentially with each iteration the average removal cost is constant. Additionally, no tail recursion ever occurs on a child node, so the tail recursion loop can only move from a child back to its successive ancestors. If a rotation occurs in case 2 (which is the only possibility of rotation within the loop of cases 1–3), then the parent of the node N becomes red after the rotation and we will exit the loop. Therefore, at most one rotation will occur within this loop. Since no more than two additional rotations will occur after exiting the loop, at most three rotations occur in total. Mehlhorn & Sanders (2008) point out: "AVL trees do not support constant amortized deletion costs", but red-black trees do.[24] Proof of asymptotic bounds[edit] A red black tree which contains n internal nodes has a height of O(log n). Definitions: h(v) = height of subtree rooted at node v bh(v) = the number of black nodes from v to any leaf in the subtree, not counting v if it is black - called the black-height Lemma: A subtree rooted at node v has at least 2 b h ( v ) − 1 displaystyle 2^ bh(v) -1 internal nodes. Proof of Lemma (by induction height): Basis: h(v) = 0 If v has a height of zero then it must be null, therefore bh(v) = 0. So: 2 b h ( v ) − 1 = 2 0 − 1 = 1 − 1 = 0 displaystyle 2^ bh(v) -1=2^ 0 -1=1-1=0 Inductive Step: v such that h(v) = k, has at least 2 b h ( v ) − 1 displaystyle 2^ bh(v) -1 internal nodes implies that v ′ displaystyle v' such that h( v ′ displaystyle v' ) = k+1 has at least 2 b h ( v ′ ) − 1 displaystyle 2^ bh(v') -1 internal nodes. Since v ′ displaystyle v' has h( v ′ displaystyle v' ) > 0 it is an internal node. As such it has two children each of which have a black-height of either bh( v ′ displaystyle v' ) or bh( v ′ displaystyle v' )-1 (depending on whether the child is red or black, respectively). By the inductive hypothesis each child has at least 2 b h ( v ′ ) − 1 − 1 displaystyle 2^ bh(v')-1 -1 internal nodes, so v ′ displaystyle v' has at least: 2 b h ( v ′ ) − 1 − 1 + 2 b h ( v ′ ) − 1 − 1 + 1 = 2 b h ( v ′ ) − 1 displaystyle 2^ bh(v')-1 -1+2^ bh(v')-1 -1+1=2^ bh(v') -1 internal nodes. Using this lemma we can now show that the height of the tree is logarithmic. Since at least half of the nodes on any path from the root to a leaf are black (property 4 of a red–black tree), the black-height of the root is at least h(root)/2. By the lemma we get: n ≥ 2 h ( root ) 2 − 1 ↔ log 2 ( n + 1 ) ≥ h ( root ) 2 ↔ h ( root ) ≤ 2 log 2 ( n + 1 ) . displaystyle ngeq 2^ h( text root ) over 2 -1leftrightarrow ;log _ 2 (n+1) geq h( text root ) over 2 leftrightarrow ;h( text root )leq 2log _ 2 (n+1) . Therefore, the height of the root is O(log n). Set operations and bulk operations[edit] In addition to the single-element insert, delete and lookup operations, several set operations have been defined on red-black trees: union, intersection and set difference. Then fast bulk operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, Split and Join. With the new operations, the implementation of red-black trees can be more efficient and highly-parallelizable.[25] This implementation allows a red root. Join: The function Join is on two red-black trees t1 and t2 and a key k and will return a tree containing all elements in t1, t2 as well as k. It requires k to be greater than all keys in t1 and smaller than all keys in t2. If the two trees have the same black height, Join simply create a new node with left subtree t1, root k and right subtree t2. If both t1 and t2 have black root, set k to be red. Otherwise k is set black. Suppose that t1 has larger black height than t2 (the other case is symmetric). Join follows the right spine of t1 until a black node c which is balanced with t2. At this point a new node with left child c, root k (set to be red) and right child t1 is created to replace c. The new node may invalidate the red-black invariant because at most three red nodes can appear in a row. This can be fixed with a double rotation. If double red issue propagates to the root, the root is then set to be black, restoring the properties. The cost of this function is the difference of the black heights between the two input trees. Split: To split a red-black tree into two smaller trees, those smaller than key x, and those larger than key x, first draw a path from the root by inserting x into the red-black tree. After this insertion, all values less than x will be found on the left of the path, and all values greater than x will be found on the right. By applying Join, all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is asymmetric. The cost of Split is order of O ( log n ) displaystyle O(log n) , the height of the tree. The union of two red-black trees t1 and t2 representing sets A and B, is a red-black tree t that represents A ∪ B. The following recursive function computes this union: function union(t1, t2): if t1 = nil: return t2 if t2 = nil: return t1 t<, t> ← split t2 on t1.root return join(t1.root, union(left(t1), t<), union(right(t1), t>)) Here, Split is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is non-destructive, but an in-place destructive version exists as well.) The algorithm for intersection or difference is similar, but requires the Join2 helper routine that is the same as Join but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the red-black tree. Since Split calls Join but does not deal with the balancing criteria of red-black trees directly, such an implementation is usually called the "join-based" implementation. The complexity of each of union, intersection and difference is O ( m log ( n m + 1 ) ) displaystyle Oleft(mlog left( n over m +1right)right) for two red-black trees of sizes m displaystyle m and n ( ≥ m ) displaystyle n(geq m) . This complexity is optimal in terms of the number of comparisons. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed in parallel with a parallel depth O ( log m log n ) displaystyle O(log mlog n) .[25] When m = 1 displaystyle m=1 , the join-based implementation has the same computational DAG as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree. Parallel algorithms[edit] Parallel algorithms for constructing red–black trees from sorted lists of items can run in constant time or O(log log n) time, depending on the computer model, if the number of processors available is asymptotically proportional to the number n of items where n→∞. Fast search, insertion, and deletion parallel algorithms are also known.[26] Popular culture[edit] A red-black-tree was referenced correctly in an episode of Missing (Canadian TV series)[27] as noted by Robert Sedgewick in one of his lectures:[28] Jess: "It was the red door again." Pollock: "I thought the red door was the storage container." Jess: "But it wasn't red anymore, it was black." Antonio: "So red turning to black means what?" Pollock: "Budget deficits, red ink, black ink." Antonio: "It could be from a binary search tree. The red-black tree tracks every simple path from a node to a descendant leaf that has the same number of black nodes." Jess: "Does that help you with the ladies?" See also[edit] List of data structures
Tree data structure
Tree rotation
AA tree, a variation of the red-black tree
AVL tree
References[edit] ^ a b c d e f James Paton. "Red-Black Trees".
^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.;
Stein, Clifford (2001). "Red–Black Trees". Introduction to
Algorithms (second ed.). MIT Press. pp. 273–301.
ISBN 0-262-03293-7.
^ John Morris. "Red–Black Trees".
^
Further reading[edit] Mathworld: Red–Black Tree San Diego State University: CS 660: Red–Black tree notes, by Roger Whitney Pfaff, Ben (June 2004). "Performance Analysis of BSTs in System Software" (PDF). Stanford University. External links[edit] A complete and working implementation in C[dead link]
Red–Black Tree Demonstration
OCW MIT Lecture by Prof.
v t e Tree data structures Search trees (dynamic sets/associative arrays) 2–3 2–3–4 AA (a,b) AVL B B+ B* Bx (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red-black Scapegoat Splay T Treap UB Weight-balanced Heaps Binary Binomial Brodal Fibonacci Leftist Pairing Skew Van Emde Boas Weak Tries Ctrie
Spatial data partitioning trees Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X Other trees Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top v t e
Types Collection Container Abstract Associative array Multimap List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set Arrays Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix Linked Association list Linked list Skip list Unrolled linked list XOR linked list Trees B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree Graphs Binary decision diagram Directed acyclic graph Directed acyclic word graph List |