Red-black tree, a kind of balanced binary tree, is best known for its application in C++ STL map, which is one of the most ideal storage methods for ordered sets. In addition to the properties of binary trees, red-black trees have a “color” property for each node, which can be either red or black. A red-black tree should satisfy the following properties:
- Each node is red or black;
- The root node is black;
- Nil for each leaf node is black (it is much easier to remove adjustments using sentinel nodes);
- If one node is red, two of its children are black;
- For each node, the same number of black nodes are passed through to all subsequent leaf nodes.
By definition, we can write the data structure of a red-black tree node:
struct Node {
enum Color { RED, BLACK };
Color _color;
Key _key;
Value _value;
Node *_parent, *_left, *_right;
Node(): _color(BLACK) {}
Node(const Key &key, const Value &value, Node *left, Node *right, Node *parent):
_key(key), _value(value), _color(RED), _left(left), _right(right), _parent(parent) {}
};
Copy the codeThis article omitted the copy, destructor, assignment and other operations, the complete source code in Gist.
rotating
For red-black trees to be balanced, they need to be constantly tweaked as they insert and delete elements. Among them, the most basic operation is left and right rotation.
Taking left rotation as an example, the operation can be divided into three steps:
- Change the left child of Q to the right child of P;
- Change P to the left child of Q;
- Change Q to the root of the current subtree.
void leftRotate(Node *x)
{
Node *y = x->_right;
// remove y->left to x->right
x->_right = y->_left;
if(x->_right ! = nil) x->_right->_parent = x;// remove y up
y->_parent = x->_parent;
if (x->_parent == nil)
root = y;
else if (x->_parent->_left == x)
x->_parent->_left = y;
else
x->_parent->_right = y;
// remove x down
x->_parent = y;
y->_left = x;
}
Copy the codeinsert
Pollution first, treatment later. It is preferred to insert nodes into the binary tree in the same way as the binary tree and then adjust the red-black tree.
void insert(Node *nptr)
{
Node *it = root, *p = root;
// find insert position
while(it ! = nil) { p = it;if (nptr->_key < it->_key)
it = it->_left;
else if (nptr->_key > it->_key)
it = it->_right;
else {
// find target key-value
it->_value = nptr->_value;
return; }}// insert
nptr->_parent = p;
if (p == nil)
root = nptr;
else if (nptr->_key < p->_key)
p->_left = nptr;
else
p->_right = nptr;
// fixup
insertFixup(nptr);
}
Copy the codeAfter the insertion, there are six cases, and because of the left and right symmetry, there are really only three cases to consider.
In case 1, the parent node and tertiary node of the adjustment target node B are both red nodes, and the grandfather node is black node. We need to change the colors of the parent node and tertiary node to black, set the grandfather node to red node, and set the adjustment target to grandfather node.
In cases 2 and 3, the parent node of the newly inserted node is red, the grandfather node is black, and the tertiary node is black. The preferred option is to convert case 2 to case 3, making B the black node, A and C the red children of B, and setting the adjustment target to A. Often after these two cases are handled, the red-black tree is finished adjusting.
Since NIL counts as a black node, you also need to define a macro that gets the node’s color.
The adjustment process is bottom-up, a new node is inserted with a red color, and the goal of each adjustment is to preserve the red-black nature of each subtree. For cases 2 and 3, the root of the subtree is black after the adjustment, which does not affect the overall nature. In case 1, the root of the subtree is red, which affects the nature of the whole and requires further adjustment. This is the meaning of the cyclic condition.
void insertFixup(Node *ptr)
{
while (ptr->_parent->_color == Node::RED) {
if (ptr->_parent == ptr->_parent->_parent->_left) {
Node *y = ptr->_parent->_parent->_right;
// case 1
if (y->_color == Node::RED) {
ptr->_parent->_color = Node::BLACK;
y->_color = Node::BLACK;
ptr->_parent->_parent->_color = Node::RED;
ptr = ptr->_parent->_parent;
} else {
// case 2: switch case 2 to case 3
if (ptr == ptr->_parent->_right) {
ptr = ptr->_parent;
leftRotate(ptr);
}
// case 3ptr->_parent->_color = Node::BLACK; ptr->_parent->_parent->_color = Node::RED; rightRotate(ptr->_parent->_parent); }}else {
// with 'left' and 'right' exchanged
Node *y = ptr->_parent->_parent->_left;
if (y->_color == Node::RED) {
ptr->_parent->_color = Node::BLACK;
y->_color = Node::BLACK;
ptr->_parent->_parent->_color = Node::RED;
ptr = ptr->_parent->_parent;
} else {
if (ptr == ptr->_parent->_left) {
ptr = ptr->_parent;
rightRotate(ptr);
}
ptr->_parent->_color = Node::BLACK;
ptr->_parent->_parent->_color = Node::RED;
leftRotate(ptr->_parent->_parent);
}
}
}
root->_color = Node::BLACK;
}
Copy the codedelete
The process of deleting is much more complicated than the process of inserting. As with binary trees, we need a substitution operation to replace subtree U with subtree V.
void transplant(shared_ptr<Node> u, shared_ptr<Node> v)
{
if (u->_parent == nil)
root = v;
else if (u == u->_parent->_left)
u->_parent->_left = v;
else
u->_parent->_right = v;
v->_parent = u->_parent;
}
Copy the codeThe deletion process is similar to binary trees, with more processing of sentries and recording of colors.
void remove(Node *ptr)
{
Node *y = ptr, *x;
int y_original_color = y->_color;
if (y->_left == nil) {
x = ptr->_right;
transplant(ptr, ptr->_right);
} else if (y->_right == nil) {
x = ptr->_left;
transplant(ptr, ptr->_left);
} else {
y = min(ptr->_right);
y_original_color = y->_color;
x = y->_right;
if (y->_parent == ptr)
x->_parent = y; // change nil->_parent
else {
transplant(y, y->_right);
y->_right = ptr->_right;
y->_right->_parent = y;
}
transplant(ptr, y);
y->_left = ptr->_left;
y->_left->_parent = y;
y->_color = ptr->_color;
}
if (y_original_color == Node::BLACK)
deleteFixup(x);
}
Copy the codeLet’s first think about what we’re doing to the red-black tree when we delete a node. ** If a red node is deleted, the nature of the red-black tree will not be affected; If a black node is deleted, then it means that the black height is equal to the property no longer exists. Delete a black node. ** Then, similar to the idea of inserting adjustments, the goal of each adjustment is to preserve properties within the subtree.
The adjustment process needs to be divided into four cases of bilateral symmetry:
- Case 1: there is a red sibling node, by rotation and color swap, make the red node to adjust the target node side, become one of cases 2, 3, 4;
- Case 2: The two children of the sibling node are all black, so the sibling node is set to red node, so that the black height in the subtree is equal, but the deleted black node is not compensated, and it needs to be adjusted upward.
- Case 3: The brother node is red on the left and black on the right. At this time, the red node needs to be adjusted to the right of the tertiary node, which becomes case 4.
- Case 4: The right node of the sibling node is red. In this case, the red node needs to be adjusted to the side of the adjustment target node to make up for the deleted black node. After the adjustment, the subtree meets the red-black tree nature, and the adjustment process is complete.
For the cyclic condition. How do you understand that? If the adjustment process reaches the root node, then there is no black height missing one in a subtree and the loop can be ended. If a red node is encountered, the problem of unequal black heights can be solved by changing the red node to black.
void removeFixup(Node *ptr)
{
while(ptr ! = root && ptr->_color == Node::BLACK) {if (ptr == ptr->_parent->_left) {
Node *w = ptr->_parent->_right;
// case 1
if (w->_color == Node::RED) {
w->_color = Node::BLACK;
ptr->_parent->_color = Node::RED;
leftRotate(ptr->_parent);
w = ptr->_parent->_right;
}
// case 2
if (w->_left->_color == Node::BLACK && w->_right->_color == Node::BLACK) {
w->_color = Node::RED;
ptr = ptr->_parent;
} else {
// case 3
if (w->_right->_color == Node::BLACK) {
w->_left->_color = Node::BLACK;
w->_color = Node::RED;
rightRotate(w);
w = ptr->_parent->_right;
}
// case 4w->_color = ptr->_parent->_color; ptr->_parent->_color = Node::BLACK; w->_right->_color = Node::BLACK; leftRotate(ptr->_parent); ptr = root; }}else {
// with 'left' and 'right' exchanged
Node *w = ptr->_parent->_left;
if (w->_color == Node::RED) {
w->_color = ptr->_parent->_color;
ptr->_parent->_color = Node::RED;
rightRotate(ptr->_parent);
w = ptr->_parent->_left;
}
if (w->_left->_color == Node::BLACK && w->_right->_color == Node::BLACK) {
w->_color = Node::RED;
ptr = ptr->_parent;
} else {
if (w->_left->_color == Node::BLACK) {
w->_color = Node::RED;
w->_right->_color = Node::BLACK;
leftRotate(w);
w = ptr->_parent->_left;
}
w->_color = ptr->_parent->_color;
w->_left->_color = Node::BLACK;
ptr->_parent->_color = Node::BLACK;
rightRotate(ptr->_parent);
ptr = root;
}
}
}
ptr->_color = Node::BLACK;
}
Copy the codeTo find the
Node colors have no meaning for the search process, and the red-black tree search process is the same as binary trees.