preface
Red black tree is widely used. It is essentially a special AVL tree, but it is better than AVL tree. The efficiency of query, insertion and deletion of red black tree is O(logN). The underlying implementation of set and map in C + + and event manager in Epoll is red black tree.
Characteristics of red black tree
In addition to the characteristics of AVL tree, red black tree also includes the following characteristics:
- The node is black or red
- The root is black
- Leaf nodes are black
- Each red node must have two black child nodes
- The simple path from any node to each leaf node contains the same number of black nodes
be careful:
In feature 3, the leaf node represents the empty node, that is, the empty node is black;
Feature 4 represents that there can be no continuous red nodes;
In feature 5, a simple path means that there can be no duplicate nodes. This sentence means that no path can be twice as long as other paths
Introduction to red black tree node
- node
struct TreeNode
{
int val;
bool color;
struct TreeNode *left;
struct TreeNode *right;
struct TreeNode *parent;
TreeNode(int val) : val(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
- Left and right rotation
void RBT::left_rotate(TreeNode* x)
{
TreeNode* y = x->right;
x->right = y->left;
if (y->left)
y->left->parent = x;
y->parent = x->parent;
if (_root == x)
_root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
void RBT::right_rotate(TreeNode* x)
{
TreeNode* y = x->left;
x->left = y->right;
if (y->right)
y->right->parent = x;
y->parent = x->parent;
if (_root == x)
_root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->right = x;
x->parent = y;
}
Red black tree insertion
Through the nature of red black tree, we know that the tree has strict requirements for black nodes, so we choose to insert red nodes when inserting.
Several situations of insertion:
- After inserting a node, the parent node is empty, which means that the tree is originally an empty tree. You only need to dye the node color black;
- After inserting a node, the parent node is black, which will not destroy the nature of the red black tree, so you don't have to do anything;
- After inserting a node, if the parent node is red and the tertiary node exists and is also red, flip the colors of the grandfather node, parent node and tertiary node, and check whether the grandfather node is the root node;
- After inserting a node, the parent node is red and the tertiary node does not exist. This situation is more complicated:
1) If the inserted node is on the left of the parent node, rotate the grandfather node to the right and flip the colors of the parent node and the grandfather node;
2) If the inserted node is on the right side of the parent node, rotate to the left of the parent node first, and then perform 1) operation.
Wikipedia and many blogs have also discussed the fifth case: the parent node is red and the tertiary node is black, but I personally don't think it is necessary, because the red black tree itself under this premise has violated its nature (Article 5).
- Illustration
Case 1 and case 2 are relatively simple and need not be elaborated too much.
Case 3:
Case 4:
1) Situation
2) Situation
- code
void RBT::insert_node(TreeNode* node)
{
TreeNode* curr = _root, *pre = nullptr;
while (curr)
{
pre = curr;
if (node->val < curr->val)
curr = curr->left;
else if (node->val > curr->val)
curr = curr->right;
else //You already have this value, so you don't need to add it
return;
}
node->parent = pre;
if (!pre)
_root = node;
else{
if (node->val < pre->val)
pre->left = node;
else
pre->right = node;
}
insert_fixup(node);
}
void RBT::insert_fixup(TreeNode* node)
{
TreeNode* parent, *gparent, *uncle;
//Only case 3 and case 4 need to be adjusted
while ((parent=node->parent)!=nullptr && parent->color==RED)
{
gparent = parent->parent;
if (parent == gparent->left){//The parent node is on the left and symmetrical. The other case below is the same
//Situation 3
if ((uncle=gparent->right)!=nullptr && uncle->color==RED){
parent->color = BLACK;
uncle->color = BLACK;
gparent->color = RED;
node = gparent;
continue; //Adjust the grandfather as a newly inserted node
}
//Situation 4
if (parent->right == node){//It may be case 2) in case 4, then make a rotation first
left_rotate(parent);
TreeNode* t = parent;
parent = node;
node = t;
}
//Case 1 of case 4
parent->color = BLACK;
gparent->color = RED;
right_rotate(gparent);
}else //Symmetrical operation
{
//Situation 3
if ((uncle=gparent->left)!=nullptr && uncle->color==RED){
parent->color = BLACK;
uncle->color = BLACK;
gparent->color = RED;
node = gparent;
continue; //Adjust the grandfather as a newly inserted node
}
//Situation 4
if (parent->left == node){//It may be case 2) in case 4, then make a rotation first
right_rotate(parent);
TreeNode* t = parent;
parent = node;
node = t;
}
//Case 1 of case 4
parent->color = BLACK;
gparent->color = RED;
left_rotate(gparent);
}
}
_root->color = BLACK;
}
Red black tree deletion
I Deleting a node has two child nodes, which can be transformed into deleting a single child node or leaf node;
II If the deleted node has a single child node, the node to be deleted must be black and the child node must be red. Top the child node and dye it black;
III Delete a leaf node. If the leaf node is red, you can delete it directly;
IV Delete a leaf node. The leaf node is black. The leaf node must have siblings. This situation is complex and needs to be discussed by situation: (at this time, only the leaf node on the left is discussed, and the right is symmetrical)
- If the sibling node is red, dye the sibling node black, dye the left son of the sibling node red, and then turn left.
-
If the sibling node is black and is a leaf node, dye the sibling node red. Because the number of black nodes is uneven at this time, it is necessary to adjust the parent node again;
-
If the sibling node is black and not a leaf node, the child of the sibling node must be red. There are three cases:
1) The sibling node has a red right child, which is transformed as follows:
Assign the color of the parent node to the brother node, then dye the right paper color of the parent node and brother node into black, and finally turn left
2) The sibling node has a red left child, which is transformed as follows:
Dye the brother node red, the left child of the brother node black, and finally turn right to the brother node, which returns to the situation of 1)
3) The sibling node has two red children, which are transformed as follows:
This case is essentially the same as case 1). Assign the color of the parent node to the brother node, then dye the right child paper color of the parent node and brother node into black, and finally turn left
- code
void RBT::delete_node(TreeNode* node)
{
//replace represents the node replaced after deletion
//Parent is the parent node of the replace node
TreeNode* replace = nullptr, *parent = nullptr;
//If the deleted node has left and right children, find the largest child in the left subtree or the smallest child in the right subtree for replacement
if (node->left && node->right){
TreeNode* succ = nullptr;
for (succ = node->left; succ->right; succ = succ->right);
node->val = succ->val;
delete_node(succ);
return;
}else{//Delete a node as a leaf node or have only one child
//If you delete the root
if (!node->parent){
_root = (node->left ? node->left : node->right);
replace = _root;
if (_root)
_root->parent = nullptr;
}else{//Deleted is not a root
TreeNode* child = (node->left ? node->left : node->right);
if (node->parent->left == node)
node->parent->left = child;
else
node->parent->right = child;
if (child)
child->parent = node->parent;
replace = child;
parent = node->parent;
}
}
//If the deleted node is red, it ends directly
if (node->color == BLACK)
delete_fixup(replace, parent);
}
void RBT::delete_fixup(TreeNode* replace, TreeNode* parent)
{
TreeNode* brother = nullptr;
// If the replacement node is black and not the root node.
//After the above deleteNode method, the parent must not be null
while ((replace == nullptr || replace->color == BLACK) && replace != this->_root){
//Everything about the left child's position,
if (parent->left == replace) {
brother = parent->right;
// case1 brother is black, parent is red, and parent is left-handed. The brother of replace has changed into the situation of brother black
if (brother->color == RED) {
brother->color = BLACK;
parent->color = RED;
left_rotate(parent);
brother = parent->right;
}
// Through the top, whether entering or not, the brothers became black
// Case 2 brother black, and both of his children are black
if ((brother->left == nullptr || brother->left->color == BLACK) && (brother->right == nullptr || brother->right->color == BLACK)) {
// If the parent is red at this time, transfer the brother's black to the parent
if (parent->color == RED) {
parent->color = BLACK;
brother->color = RED;
break;
} else {// If the parent is black at this time, that is, it is all black at this time, paint the brother red, resulting in one less black in the brother branch and one less black in the whole branch. It is necessary to adjust the parent again
brother->color = RED;
replace = parent;
parent = replace->parent;
}
} else {
// case3 brother black, the brother's left child is red
if (brother->left != nullptr && brother->left->color == RED) {
brother->left->color = parent->color;
parent->color = BLACK;
right_rotate(brother);
left_rotate(parent);
// case4 brother black, the brother's right child is red
} else if (brother->right != nullptr && brother->right->color == RED) {
brother->color = parent->color;
parent->color = BLACK;
brother->right->color = BLACK;
left_rotate(parent);
}
break;
}
} else {//In the case of symmetrical position, reverse the direction of rotation
brother = parent->left;
// case1 brother is black, parent is red, and parent is left-handed. The brother of replace has changed into the situation of brother black
if (brother->color == RED) {
brother->color = BLACK;
parent->color = RED;
right_rotate(parent);
brother = parent->left;
}
// Through the top, whether entering or not, the brothers became black
// Case 2 brother black, and both of his children are black
if ((brother->left == nullptr || brother->left->color == BLACK)
&& (brother->right == nullptr || brother->right->color == BLACK)) {
// If the parent is red at this time, transfer the brother's black to the parent
if (parent->color == RED) {
parent->color = BLACK;
brother->color = RED;
break;
} else {// If the parent is black at this time, that is, it is all black at this time, paint the brother red, resulting in one less black in the brother branch and one less black in the whole branch. It is necessary to adjust the parent again
brother->color = RED;
replace = parent;
parent = replace->parent;
}
} else {
// case3 brother black, the left child of the brother is red, and the right child is free
if (brother->right != nullptr && brother->right->color == RED) {
brother->right->color = parent->color;
parent->color = BLACK;
left_rotate(brother);
right_rotate(parent);
// case4 brother black, the right child of the brother is red, and the left child is optional
} else if (brother->left != nullptr && brother->left->color == RED) {
brother->color = parent->color;
parent->color = BLACK;
brother->left->color = BLACK;
right_rotate(parent);
}
break;
}
}
}
//Here we can deal with the case where the deleted node has only one child node. If it is a root, it will also be blackened.
if (replace != nullptr)
replace->color = BLACK;
}
Red black tree complete program
#include <iostream>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <vector>
#include <fstream>
#include <sstream>
#include <string.h>
#include <memory>
#include <limits>
#include <list>
#include <regex>
#include <functional>
#include <math.h>
#include <unordered_set>
#define RED 0
#define BLACK 1
using namespace std;
struct TreeNode
{
int val;
bool color;
struct TreeNode *left;
struct TreeNode *right;
struct TreeNode *parent;
TreeNode(int val) : val(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
class RBT
{
TreeNode* _root;
public:
RBT();
~RBT();
void left_rotate(TreeNode* n);
void right_rotate(TreeNode* n);
void insert_node(TreeNode*);
void insert_fixup(TreeNode*);
void delete_node(TreeNode*);
void delete_fixup(TreeNode*, TreeNode*);
void preOrder(TreeNode*) const;
void inOrder(TreeNode*) const;
TreeNode* getRoot()const { return _root; }
};
RBT::RBT()
:_root(nullptr)
{
cout << "RBT()" << endl;
}
RBT::~RBT()
{
cout << "~RBT()" << endl;
}
void RBT::preOrder(TreeNode* root) const
{
if (root)
{
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
}
void RBT::inOrder(TreeNode* root) const
{
if (root)
{
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
}
void RBT::left_rotate(TreeNode* x)
{
TreeNode* y = x->right;
x->right = y->left;
if (y->left)
y->left->parent = x;
y->parent = x->parent;
if (_root == x)
_root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
void RBT::right_rotate(TreeNode* x)
{
TreeNode* y = x->left;
x->left = y->right;
if (y->right)
y->right->parent = x;
y->parent = x->parent;
if (_root == x)
_root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->right = x;
x->parent = y;
}
void RBT::insert_node(TreeNode* node)
{
TreeNode* curr = _root, *pre = nullptr;
while (curr)
{
pre = curr;
if (node->val < curr->val)
curr = curr->left;
else if (node->val > curr->val)
curr = curr->right;
else //You already have this value, so you don't need to add it
return;
}
node->parent = pre;
if (!pre)
_root = node;
else{
if (node->val < pre->val)
pre->left = node;
else
pre->right = node;
}
insert_fixup(node);
}
/*
Through the nature of red black tree, we know that the tree has strict requirements for black nodes, so we choose to insert red nodes when inserting.
Several situations of insertion:
1.After inserting a node, the parent node is empty, which means that the tree is originally an empty tree. You only need to dye the node color black;
2.After inserting a node, the parent node is black, which will not destroy the nature of the red black tree, so you don't have to do anything;
3.After inserting a node, if the parent node is red and the tertiary node exists and is also red, flip the colors of the grandfather node, parent node and tertiary node, and check whether the grandfather node is the root node;
4.After inserting a node, the parent node is red and the tertiary node does not exist. This situation is more complicated:
1)If the inserted node is on the left of the parent node, rotate the grandfather node to the right and flip the colors of the parent node and the grandfather node;
2)If the inserted node is on the right side of the parent node, rotate to the left of the parent node first, and then perform 1) operation.
Wikipedia and many blogs have also discussed the fifth case: the parent node is red and the tertiary node is black, but I personally don't think it is necessary, because the red black tree itself under this premise has violated its nature (Article 5).
*/
void RBT::insert_fixup(TreeNode* node)
{
TreeNode* parent, *gparent, *uncle;
//Only case 3 and case 4 need to be adjusted
while ((parent=node->parent)!=nullptr && parent->color==RED)
{
gparent = parent->parent;
if (parent == gparent->left){//The parent node is on the left and symmetrical. The other case below is the same
//Situation 3
if ((uncle=gparent->right)!=nullptr && uncle->color==RED){
parent->color = BLACK;
uncle->color = BLACK;
gparent->color = RED;
node = gparent;
continue; //Adjust the grandfather as a newly inserted node
}
//Situation 4
if (parent->right == node){//It may be case 2) in case 4, then make a rotation first
left_rotate(parent);
TreeNode* t = parent;
parent = node;
node = t;
}
//Case 1 of case 4
parent->color = BLACK;
gparent->color = RED;
right_rotate(gparent);
}else //Symmetrical operation
{
//Situation 3
if ((uncle=gparent->left)!=nullptr && uncle->color==RED){
parent->color = BLACK;
uncle->color = BLACK;
gparent->color = RED;
node = gparent;
continue; //Adjust the grandfather as a newly inserted node
}
//Situation 4
if (parent->left == node){//It may be case 2) in case 4, then make a rotation first
right_rotate(parent);
TreeNode* t = parent;
parent = node;
node = t;
}
//Case 1 of case 4
parent->color = BLACK;
gparent->color = RED;
left_rotate(gparent);
}
}
_root->color = BLACK;
}
/*
Delete node:
I Deleting a node has two child nodes, which can be transformed into deleting a single child node or leaf node;
II If the deleted node has a single child node, the node to be deleted must be black and the child node must be red. Top the child node and dye it black;
III Delete a leaf node. If the leaf node is red, you can delete it directly;
IV Delete a leaf node. The leaf node is black. The leaf node must have siblings. This situation is complex and needs to be discussed by situation: (at this time, only the leaf node on the left is discussed, and the right is symmetrical)
1. If the sibling node is red, dye the sibling node black, dye the left son of the sibling node red, and then turn left.
2. If the sibling node is black and is a leaf node, dye the sibling node red. Because the number of black nodes is uneven at this time, it is necessary to adjust the parent node again;
3. If the sibling node is black and not a leaf node, the child of the sibling node must be red. There are three cases:
1)The sibling node has a red right child, which is transformed as follows:
Assign the color of the parent node to the brother node, then dye the right paper color of the parent node and brother node into black, and finally turn left
2)The sibling node has a red left child, which is transformed as follows:
Dye the brother node red, the left child of the brother node black, and finally turn right to the brother node, which returns to the situation of 1)
3)The sibling node has two red children, which are transformed as follows:
This case is essentially the same as case 1). Assign the color of the parent node to the brother node, then dye the right child paper color of the parent node and brother node into black, and finally turn left
*/
void RBT::delete_node(TreeNode* node)
{
//replace represents the node replaced after deletion
//Parent is the parent node of the replace node
TreeNode* replace = nullptr, *parent = nullptr;
//If the deleted node has left and right children, find the largest child in the left subtree or the smallest child in the right subtree for replacement
if (node->left && node->right){
TreeNode* succ = nullptr;
for (succ = node->left; succ->right; succ = succ->right);
node->val = succ->val;
delete_node(succ);
return;
}else{//Delete a node as a leaf node or have only one child
//If you delete the root
if (!node->parent){
_root = (node->left ? node->left : node->right);
replace = _root;
if (_root)
_root->parent = nullptr;
}else{//Deleted is not a root
TreeNode* child = (node->left ? node->left : node->right);
if (node->parent->left == node)
node->parent->left = child;
else
node->parent->right = child;
if (child)
child->parent = node->parent;
replace = child;
parent = node->parent;
}
}
//If the deleted node is red, it ends directly
if (node->color == BLACK)
delete_fixup(replace, parent);
}
void RBT::delete_fixup(TreeNode* replace, TreeNode* parent)
{
TreeNode* brother = nullptr;
// If the replacement node is black and not the root node.
//After the above deleteNode method, the parent must not be null
while ((replace == nullptr || replace->color == BLACK) && replace != this->_root){
//Everything about the left child's position,
if (parent->left == replace) {
brother = parent->right;
// case1 brother is black, parent is red, and parent is left-handed. The brother of replace has changed into the situation of brother black
if (brother->color == RED) {
brother->color = BLACK;
parent->color = RED;
left_rotate(parent);
brother = parent->right;
}
// Through the top, whether entering or not, the brothers became black
// Case 2 brother black, and both of his children are black
if ((brother->left == nullptr || brother->left->color == BLACK) && (brother->right == nullptr || brother->right->color == BLACK)) {
// If the parent is red at this time, transfer the brother's black to the parent
if (parent->color == RED) {
parent->color = BLACK;
brother->color = RED;
break;
} else {// If the parent is black at this time, that is, it is all black at this time, paint the brother red, resulting in one less black in the brother branch and one less black in the whole branch. It is necessary to adjust the parent again
brother->color = RED;
replace = parent;
parent = replace->parent;
}
} else {
// case3 brother black, the brother's left child is red
if (brother->left != nullptr && brother->left->color == RED) {
brother->left->color = parent->color;
parent->color = BLACK;
right_rotate(brother);
left_rotate(parent);
// case4 brother black, the brother's right child is red
} else if (brother->right != nullptr && brother->right->color == RED) {
brother->color = parent->color;
parent->color = BLACK;
brother->right->color = BLACK;
left_rotate(parent);
}
break;
}
} else {//In the case of symmetrical position, reverse the direction of rotation
brother = parent->left;
// case1 brother is black, parent is red, and parent is left-handed. The brother of replace has changed into the situation of brother black
if (brother->color == RED) {
brother->color = BLACK;
parent->color = RED;
right_rotate(parent);
brother = parent->left;
}
// Through the top, whether entering or not, the brothers became black
// Case 2 brother black, and both of his children are black
if ((brother->left == nullptr || brother->left->color == BLACK)
&& (brother->right == nullptr || brother->right->color == BLACK)) {
// If the parent is red at this time, transfer the brother's black to the parent
if (parent->color == RED) {
parent->color = BLACK;
brother->color = RED;
break;
} else {// If the parent is black at this time, that is, it is all black at this time, paint the brother red, resulting in one less black in the brother branch and one less black in the whole branch. It is necessary to adjust the parent again
brother->color = RED;
replace = parent;
parent = replace->parent;
}
} else {
// case3 brother black, the left child of the brother is red, and the right child is free
if (brother->right != nullptr && brother->right->color == RED) {
brother->right->color = parent->color;
parent->color = BLACK;
left_rotate(brother);
right_rotate(parent);
// case4 brother black, the right child of the brother is red, and the left child is optional
} else if (brother->left != nullptr && brother->left->color == RED) {
brother->color = parent->color;
parent->color = BLACK;
brother->left->color = BLACK;
right_rotate(parent);
}
break;
}
}
}
//Here we can deal with the case where the deleted node has only one child node. If it is a root, it will also be blackened.
if (replace != nullptr)
replace->color = BLACK;
}
/*******************************Test function********************************************/
void test1()
{
RBT tree;
tree.insert_node(new TreeNode(7));
tree.insert_node(new TreeNode(2));
tree.insert_node(new TreeNode(3));
tree.insert_node(new TreeNode(1));
tree.insert_node(new TreeNode(5));
tree.insert_node(new TreeNode(6));
tree.insert_node(new TreeNode(4));
tree.insert_node(new TreeNode(8));
cout << "Preorder traversal:" << endl;
tree.preOrder(tree.getRoot());
cout << "Middle order traversal:" << endl;
tree.inOrder(tree.getRoot());
}
void test2()
{
RBT tree;
tree.insert_node(new TreeNode(7));
tree.insert_node(new TreeNode(2));
tree.insert_node(new TreeNode(3));
tree.insert_node(new TreeNode(1));
tree.insert_node(new TreeNode(5));
tree.insert_node(new TreeNode(6));
tree.insert_node(new TreeNode(4));
tree.insert_node(new TreeNode(8));
tree.delete_node(tree.getRoot());
cout << "Preorder traversal:" << endl;
tree.preOrder(tree.getRoot());
cout << "Middle order traversal:" << endl;
tree.inOrder(tree.getRoot());
}
int main()
{
test2();
return 0;
}
test
The red black tree generated according to test1 is as follows:
The red black tree after deleting the root node according to test2 is as follows:
reference resources
Wikipedia - red black tree
CSDN: red black tree
CSDN: red black tree (II)
Red black tree online generator