red–black tree
self-balancing binary search tree data structure
≈ 15 min read
Names in other languages
- PolskiDrzewo czerwono-czarne
- Españolárbol rojo-negro
- Englishred–black tree
- Françaisarbre bicolore
- עבריתעץ אדום שחור
- 한국어레드-블랙 트리
- 简体中文红黑树
- 繁體中文紅黑樹
- 中文紅黑樹
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, a red–black tree is a self-balancing binary search tree data structure noted for fast storage and retrieval of ordered information. The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, which help ensure that the tree is always approximately balanced.
When the tree is modified, the new tree is rearranged and "repainted" to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.
The (re-)balancing is not perfect, but guarantees searching in O(\log n) time, where n is the number of entries in the tree. The insert and delete operations, along with tree rearrangement and recoloring, also execute in O(\log n) time.
Tracking the color of each node requires only one bit of information per node because there are only two colors (due to memory alignment present in some programming languages, the real memory consumption may differ). The tree does not contain any other data specific to it being a red–black tree, so its memory footprint is almost identical to that of a classic (uncolored) binary search tree.
In some cases, the added bit of information can be stored at no added memory cost. typedef enum Color: char { BLACK, RED } Color; typedef enum Direction: char { LEFT, RIGHT } Direction; // red-black tree node typedef struct Node { struct Node* parent; // null for the root node union { // Union so we can use ->left/->right or ->child[0]/->child[1] struct { struct Node* left; struct Node* right; }; struct Node* child[2]; }; Color color; int key; } Node; typedef struct { struct Node* root; } Tree; static Direction direction(const Node* N) { return N == N->parent->right ? RIGHT : LEFT; } Node* rotate_subtree(Tree* tree, Node* sub, Direction dir) { Node* sub_parent = sub->parent; Node* new_root = sub->child[1 - dir]; // 1 - dir is the opposite direction Node* new_child = new_root->child[dir]; sub->child[1 - dir] = new_child; if (new_child) { new_child->parent = sub; } new_root->child[dir] = sub; new_root->parent = sub_parent; sub->parent = new_root; if (sub_parent) { sub_parent->child[sub == sub_parent->right] = new_root; } else { tree->root = new_root; } return new_root; } The variable N denotes the current node, which is labeled N or N in the diagrams.
A diagram contains three columns and two to four actions. The left column shows the first iteration, the right column the higher iterations, the middle column shows the segmentation of a case into its different actions. The action "entry" shows the constellation of nodes with their colors which defines a case and mostly violates some of the requirements.
A blue border rings the current node N and the other nodes are labeled according to their relation to N. If a rotation is considered useful, this is pictured in the next action, which is labeled "rotation". If some recoloring is considered useful, this is pictured in the next action, which is labeled "color".
If there is still some need to repair, the cases make use of code of other cases and this after a reassignment of the current node N, which then again carries a blue ring and relative to which other nodes may have to be reassigned also. This action is labeled "reassign".
For both, insert and delete, there is (exactly) one case which iterates one black level closer to the root; then the reassigned constellation satisfies the respective loop invariant. A possibly numbered triangle with a black circle atop represents a red–black subtree (connected to its parent according to requirement 3) with a black height equal to the iteration level minus one, i.e. zero in the first iteration.
Its root may be red or black. A possibly numbered triangle represents a red–black subtree with a black height one less, i.e. its parent has black height zero in the second iteration. Remark For simplicity, the sample code uses the disjunction: U
NULL || U->color
BLACK // considered black and the conjunction: U != NULL && U->color
RED // not considered black Thereby, it must be kept in mind that both statements are not evaluated in total, if U
NULL . Then in both cases U->color is not touched (see Short-circuit evaluation). (The comment considered black is in accordance with requirement 2.)
The related if -statements have to occur far less frequently if the proposal is realised. // parent is optional void insert(Tree* tree, Node* node, Node* parent, Direction dir) { node->color = RED; node->parent = parent; if (!parent) { tree->root = node; return; } parent->child[dir] = node; // rebalance the tree do { // Case #1 if (parent->color == BLACK) { return; } Node* grandparent = parent->parent; if (!grandparent) { // Case #4 parent->color = BLACK; return; } dir = direction(parent); Node* uncle = grandparent->child[1 - dir]; if (!uncle || uncle->color
BLACK) { if (node
parent->child[1 - dir]) { // Case #5 rotate_subtree(tree, parent, dir); node = parent; parent = grandparent->child[dir]; } // Case #6 rotate_subtree(tree, grandparent, 1 - dir); parent->color = BLACK; grandparent->color = RED; return; } // Case #2 parent->color = BLACK; uncle->color = BLACK; grandparent->color = RED; node = grandparent; } while ((parent = node->parent)); // Case #3 return; } The rebalancing loop of the insert operation has the following invariants: Node is the current node, initially the insertion node. Node is red at the beginning of each iteration.
Requirement 3 is satisfied for all pairs node←parent with the possible exception node←parent when parent is also red (a red-violation at node). All other properties (including requirement 4) are satisfied throughout the tree.
In case 2 the problem of rebalancing is escalated \Delta h=2 tree levels or 1 black level higher in the tree, in that the grandfather G becomes the new current node N. So it takes maximally \tfrac{h}2 steps of iteration to repair the tree (where is the height of the tree). Because the probability of escalation decreases exponentially with each step the total rebalancing cost is constant on average, indeed amortized constant.
Rotations occur in cases I6 and I5 + I6 – outside the loop. Therefore, at most two rotations occur in total. 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 for maintaining requirement 4.
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 requirement 3, if it has a red parent.
After relabeling G to N the loop invariant is fulfilled so that the rebalancing can be iterated on one black level (= 2 tree levels) higher. void remove(Tree* tree, Node* node) { Node* parent = node->parent; Node* sibling; Node* close_nephew; Node* distant_nephew; Direction dir = direction(node); parent->child[dir] = NULL; goto start_balance; do { dir = direction(node); start_balance: sibling = parent->child[1 - dir]; distant_nephew = sibling->child[1 - dir]; close_nephew = sibling->child[dir]; if (sibling->color == RED) { // Case #3 rotate_subtree(tree, parent, dir); parent->color = RED; sibling->color = BLACK; sibling = close_nephew; distant_nephew = sibling->child[1 - dir]; if (distant_nephew && distant_nephew->color == RED) { goto case_6; } close_nephew = sibling->child[dir]; if (close_nephew && close_nephew->color == RED) { goto case_5; } // Case #4 sibling->color = RED; parent->color = BLACK; return; } if (distant_nephew && distant_nephew->color
RED) { goto case_6; } if (close_nephew && close_nephew->color
RED) { goto case_5; } if (parent->color == RED) { // Case #4 sibling->color = RED; parent->color = BLACK; return; } // Case #2 sibling->color = RED; node = parent; } while (parent = node->parent); // Case #1 return; case_5: rotate_subtree(tree, sibling, 1 - dir); sibling->color = RED; close_nephew->color = BLACK; distant_nephew = sibling; sibling = close_nephew; case_6: rotate_subtree(tree, parent, dir); sibling->color = parent->color; parent->color = BLACK; distant_nephew->color = BLACK; return; } The rebalancing loop of the delete operation has the following invariant: At the beginning of each iteration the black height of N equals the iteration number minus one, which means that in the first iteration it is zero and that N is a true black node in higher iterations. The number of black nodes on the paths through N is one less than before the deletion, whereas it is unchanged on all other paths, so that there is a black-violation at P if other paths exist.
All other properties (including requirement 3) are satisfied throughout the tree. The loop is where the problem of rebalancing is escalated \Delta h=1 level higher in the tree in that the parent P becomes the new current node N. So it takes maximally iterations to repair the tree (where is the height of the tree).
Because the probability of escalation decreases exponentially with each iteration the total rebalancing cost is constant on average, indeed amortized constant. (Just as an aside: Mehlhorn & Sanders point out: "AVL trees do not support constant amortized update costs."
This is true for the rebalancing after a deletion, but not AVL insertion. ) Out of the body of the loop there are exiting branches to the cases 3, 6, 5, 4, and 1; section "Delete case 3" of its own has three different exiting branches to the cases 6, 5 and 4. Rotations occur in cases 6 and 5 + 6 and 3 + 5 + 6 – all outside the loop. Therefore, at most three rotations occur in total.
P, S, and S’s children are black. After painting S red all paths passing through S, which are precisely those paths not passing through N, have one less black node. Now all paths in the subtree rooted by P have the same number of black nodes, but one fewer than the paths that do not pass through P, so requirement 4 may still be violated.
After relabeling P to N the loop invariant is fulfilled so that the rebalancing can be iterated on one black level (= 1 tree level) higher. The RB tree of height h=1 with red root is minimal. This is in agreement with m_1 = 2^{\lfloor (1+1)/2\rfloor} \!+\!2^{\lfloor 1/2 \rfloor} \!\!-\!\!2 = 2^1\!+\!2^0\!\!-\!\!2 = 1~.
A minimal RB tree (RB h in figure 2) of height h>1 has a root whose two child subtrees are of different height. The higher child subtree is also a minimal RB tree, containing also a longest path that defines its height it has m_{h-1} nodes and the black height \lfloor(h\!\!-\!\!1)/2\rfloor =: s . The other subtree is a perfect binary tree of (black) height s having 2^s\!\!-\!\!1=2^{\lfloor(h-1)/2\rfloor}\!\!-\!\!1 black nodes—and no red node.
Then the number of nodes is by induction The graph of the function m_h is convex and piecewise linear with breakpoints at (h=2k\;|\;m_{2k}=2 \cdot 2^k\!-\!2) where k \in \N . The function has been tabulated as m_h= A027383(h–1) for h\geq 1 Solving the function for h The inequality 9>8=2^3 leads to 3 > 2^{3/2} , which for odd h leads to m_h = 3 \cdot 2^{(h-1)/2}-2 = \bigl(3\cdot 2^{-3/2}\bigr) \cdot 2^{(h+2)/2}-2 > 2 \cdot 2^{h/2}-2 . So in both, the even and the odd case, h is in the interval with n being the number of nodes.
Conclusion A red–black tree with n nodes (keys) has tree height h \in O(\log n) . if (T L .color=black) and (T L .blackHeight=T R .blackHeight): return Node(T L ,⟨k,red⟩,T R ) T'=Node(T L .left,⟨T L .key,T L .color⟩,joinRightRB(T L .right,k,T R )) if (T L .color=black) and (T'.right.color=T'.right.right.color=red): T'.right.right.color=black; return rotateLeft(T') return T' /* T [recte T'] */ function joinLeftRB(T L , k, T R ): /* symmetric to joinRightRB */ function join(T L , k, T R ): if T L .blackHeight>T R .blackHeight: T'=joinRightRB(T L ,k,T R ) if (T'.color=red) and (T'.right.color=red): T'.color=black return T' if T R .blackHeight>T L .blackHeight: /* symmetric */ if (T L .color=black) and (T R .color=black): return Node(T L ,⟨k,red⟩,T R ) return Node(T L ,⟨k,black⟩,T R ) The split algorithm is as follows: function split(T, k): if (T = NULL) return (NULL, false, NULL) if (k = T.key) return (T.left, true, T.right) if (k 1 , t 2 ): if t 1 = NULL return t 2 if t 2 = NULL return t 1 (L 1 ,b,R 1 )=split(t 1 ,t 2 .key) proc1=start: T L =union(L 1 ,t 2 .left) proc2=start: T R =union(R 1 ,t 2 .right) wait all proc1,proc2 return join(T L , t 2 .key, T R ) 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 also.)
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\left(m \log \left({n\over m}+1\right)\right) for two red–black trees of sizes m and n(\ge 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) . When m=1 , the join-based implementation has the same computational directed acyclic graph (DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree. Next the tree must be split into parts \langle T_1, \cdots, T_k \rangle in a way, so that the ranges of I_m and T_n overlap for corresponding parts only ( m=n ); in other words, thanks to the ordering, for every j \in \mathbb{N}^+ | \, 1 \leq j following constraints hold: \text{last}(I_j) \text{last}(T_j) Now the algorithm inserts each element of I_j into T_j sequentially.
This step must be performed for every , which can be done by up to processors in parallel. Finally, the resulting trees will be joined to form the final result of the entire operation. Note that in Step 3 the constraints for splitting assure that in Step 5 the trees can be joined again and the resulting sequence is sorted.
The pseudo code shows a simple divide-and-conquer implementation of the join-based algorithm for bulk-insert. Both recursive calls can be executed in parallel.
The join operation used here differs from the version explained in this article, instead join2 is used, which misses the second parameter k. bulkInsert(T, I, k): I.sort() bulklInsertRec(T, I, k) bulkInsertRec(T, I, k): if k = 1: forall e in I: T.insert(e) else m := ⌊size(I) / 2⌋ (T 1 , _, T 2 ) := split(T, I[m]) bulkInsertRec(T 1 , I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T 2 , I[m + 1 .. size(I) - 1], ⌊k / 2⌋) T ← join2(T 1 , T 2 )
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374580875 under CC BY-SA 4.0; modifications have been made.