# Properties and simple realization of red black tree

2022-06-24 09:53:32HHYX.

# The nature of the mangrove

The previous blog introduced AVL The nature and basic realization of tree , Red black tree as another tree structure , What is his nature ？
Red black tree is a binary search tree , And AVL Trees use height differences to control balance , He adds a storage bit to each node to represent the color of the node , It can be Red or Black. By restricting the coloring method of each node in any path from root to leaf , The red and black trees make sure that no path is twice as long as the others , So it's close to equilibrium .
therefore , In order to control the height balance , It has the following properties ：

1. Each node is either red or black
2. The root node is black
3. If a node is red , Then its two child nodes are black
4. For each node , A simple path from this node to all its descendant leaf nodes , All contain the same number of black nodes
5. Every leaf node is black ( The leaf node here refers to the empty node )

If a red black tree has the above properties, it means that its node control has the following properties ：

1. Suppose the number of black nodes in any path of the red black tree is X, Then the height of the red black tree h Then for 2X>=h>=X
2. Suppose the number of black nodes in any path of the red black tree is X, Then the number of nodes of the red black tree is 2^X-1<=N<=2^2X-1
Therefore, it is in strict balance with AVL Compared with the time complexity of tree search ,AVL The time complexity of tree search is log2N, The time complexity of red black tree searching a tree is 2*log2N, however AVL Tree control balance requires frequent rotation to control balance , The rotation performance loss of the red black tree control balance will be higher than AVL Tree low .

# Simple implementation of red black tree

## The basic composition of red and black trees

As the name suggests, there is a variable in each node of the red black tree to represent the color of the node ( Red or black ), Control the balance of red and black trees by color and the principle of red and black trees , Therefore, the red black tree node can be constructed as follows ：
Enumeration is used here to identify the color of each node of the red black tree , By default, each node of the red black tree stores a pair Variable of type , The red black tree is also realized through a trigeminal chain .

``````enum Colour
{

RED,
BLACK
};

template<class K,class V>
struct RBtreeNode
{

RBtreeNode<K, V>* _left;
RBtreeNode<K, V>* _right;
RBtreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
RBtreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{

}

};
``````

After defining the red black tree node , The basic framework of red black tree can be simply constructed , Then, the functions such as inserting can be realized in turn .

``````template<class K,class V>
class RBTree
{

typedef RBtreeNode<K, V> Node;
public:
RBTree()
:_root(nullptr)
{

}
bool Insert(const pair<K, V>& kv);
void _InOrder(Node* root);
bool IsBalance();
private:
Node* _root;
};
``````

## The insertion of red and black trees

Red black tree inserts and AVL Trees are like , First find the insertion position to insert , Then adjust the balance , The main difference between the two is the way to adjust the balance . Let's take a look at the code implementation of the red black tree insertion process

``````	bool Insert(const pair<K, V>& kv)
{

if (_root == nullptr)// When the inserted node is the root node
{

_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{

if (cur->_kv.first < kv.first)// When the inserted value is larger than the current node , Go to the right
{

parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)// When the inserted value is smaller than the current node , Go to the left
{

parent = cur;
cur = cur->_left;
}
else// When duplicate values occur
{

return false;
}
}
cur = new Node(kv);
cur->_col = RED;// Set the value of the inserted node to red   It's the lowest cost
if (parent->_kv.first < kv.first)// When parent The value ratio in the node kv When I was young ,cur Is the right node of this node
{

parent->_right = cur;
cur->_parent = parent;
}
else// When parent The value ratio in the node kv When it's high ,cur Is the left node of this node
{

parent->_left = cur;
cur->_parent = parent;
}
}
``````

Through the above code, you can insert new nodes in the red black tree , However, the insertion may lead to the imbalance of the red black tree or violate the basic principles of the red black tree , Therefore, it is necessary to adjust the balance of red and black trees after insertion . Here, the balance adjustment can be roughly divided into the following 4 In this case ：

### situation 1

As shown in the figure below , When parent The node is red ,parent The sibling node of is also red ,grandparent When the node is black , Insert a red left node , Two consecutive red nodes appear , So it needs to be adjusted , The adjustment method here is to parent Nodes and uncle Nodes are changed to black , And will grandparent The node changes to red , If grandparent If the node is the root node, it will be changed to black , Otherwise, continue to adjust upward , The code implementation is as follows ： ``````		while (parent && parent->_col == RED)// When parent If it exists and is red, it needs to be adjusted
{

Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{

// The color change continues to adjust upwards
Node* uncle = grandparent->_right;
//uncle It exists and is red
if (uncle && uncle->_col == RED)
{

parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
}

}
}
_root->_col=BLACK;
``````

### situation 2

When cur For the red node ,parent It is also a red node ,grandparent Black nodes , here uncle It may not exist or it may be a black node , If at this time uncle Node does not exist , be cur It must be a newly inserted node , because parent It's a red node , If cur If the node is not newly inserted, the principle that the number of black nodes in each path is the same will not be satisfied . If uncle When the node exists and is black , that cur The nodes must have been black , What you see now is red because cur The subtree of becomes red in the process of upward adjustment . If the inserted node is the left node , Then carry out the above right rotation , If the inserted node is the right node , Then, it is necessary to convert the left rotation to the former one, and then carry out the right rotation . The adjustment implementation code is as follows ：

``````//uncle Not present or existing and black
if (cur == parent->_left)//cur yes parent The left node
{

RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
parent = cur->_parent;
}
else// If the current node is parent The right of the node
{

RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
``````

### situation 3

When parent by grandparent The right node of , Similar to the above two cases , Just do the same
The code is as follows ：

``````				Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{

// Color change upward treatment
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle It doesn't exist or it's black
{

if (cur == parent->_right)
{

RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{

RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}

``````

### rotate

The rotation and AVL The rotation in a tree is similar to , The code is as follows ：

``````	void RotateR(Node* parent)// Right single spin
{

Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{

subLR->_parent = parent;
}
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{

_root = subL;
_root->_parent = nullptr;
}
else
{

if (parentParent->_left == parent)
{

parentParent->_left = subL;
}
else
{

parentParent->_right = subL;
}
subL->_parent = parentParent;

}
}

void RotateL(Node* parent)// Left spin
{

Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{

subRL->_parent = parent;
}
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{

_root = subR;
_root->_parent = nullptr;
}
else
{

if (parentParent->_left == parent)
{

parentParent->_left = subR;
}
else
{

parentParent->_right = subR;
}
subR->_parent = parentParent;
}

}
``````

### summary

The overall insertion code of the red black tree is as follows ：

``````	bool Insert(const pair<K, V>& kv)
{

if (_root == nullptr)// When the inserted node is the root node
{

_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{

if (cur->_kv.first < kv.first)// When the inserted value is larger than the current node , Go to the right
{

parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)// When the inserted value is smaller than the current node , Go to the left
{

parent = cur;
cur = cur->_left;
}
else// When duplicate values occur
{

return false;
}
}
cur = new Node(kv);
cur->_col = RED;// Set the value of the inserted node to red   It's the lowest cost
if (parent->_kv.first < kv.first)// When parent The value ratio in the node kv When I was young ,cur Is the right node of this node
{

parent->_right = cur;
cur->_parent = parent;
}
else// When parent The value ratio in the node kv When it's high ,cur Is the left node of this node
{

parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)// When parent If it exists and is red, it needs to be adjusted
{

Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{

Node* uncle = grandparent->_right;
//uncle It exists and is red
if (uncle && uncle->_col == RED)
{

// The color change continues to adjust upwards
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
//uncle Not present or existing and black
else
{

if (cur == parent->_left)//cur yes parent The left node
{

RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;

}
else// If the current node is parent The right of the node
{

RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}

}
else//parent==grandparent->_right
{

Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{

// Color change upward treatment
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle It doesn't exist or it's black
{

if (cur == parent->_right)
{

RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{

RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}

}
}
_root->_col = BLACK;
return false;

}
``````

## Search for red and black trees

The search function of red black tree is similar to that of other search binary trees , Use the middle order traversal , The code implementation is as follows ：

``````
void InOrder()
{

return _InOrder(_root);
}

void _InOrder(Node* root)
{

if (root == nullptr)
{

return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
``````

## Red black tree balance judgment

The balance judgment of red black tree mainly starts from the principle of red black tree ： The first is that the number of black nodes in each path is the same , The second is that there will be no continuous red nodes , The third is that the root node must be black , The function to judge the balance is realized according to the above principles ：

``````	bool IsBalance()// Judge whether the binary tree is balanced
{

if (_root && _root->_col == RED)
{

cout << " The root node is not black " << endl;
return false;
}
int banchmark = 0;// Count the number of black nodes in a path
Node* left = _root;// Here, select the leftmost node path
while (left)
{

if (left->_col == BLACK)
{

++banchmark;
}
left = left->_left;
}
int blacknum = 0;
return _IsBalance(_root, banchmark, blacknum);

}
bool _IsBalance(Node* root, int banchmark, int blacknum)
{

if (root == nullptr)
{

if (banchmark != blacknum)
{

cout << " There are path black nodes that are not equal " << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{

cout << " Continuous red nodes appear " << endl;
return false;
}
if (root->_col == BLACK)
{

blacknum++;
}
return _IsBalance(root->_left, banchmark, blacknum) && _IsBalance(root->_right, banchmark, blacknum);
}
``````

## Height calculation of red and black trees

Here, the height calculation of the red black tree is the same as that of the normal binary tree , Find the longest path

``````	int Height()
{

return _Height(_root);
}

int _Height(Node* root)
{

if (root == nullptr)
{

return 0;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
``````

# The test of red black tree

``````#include<iostream>
using namespace std;

enum Colour
{

RED,
BLACK
};

template<class K,class V>
struct RBtreeNode
{

RBtreeNode<K, V>* _left;
RBtreeNode<K, V>* _right;
RBtreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
RBtreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{

}

};

template<class K,class V>
class RBTree
{

typedef RBtreeNode<K, V> Node;
public:
RBTree()
:_root(nullptr)
{

}
bool Insert(const pair<K, V>& kv)
{

if (_root == nullptr)// When the inserted node is the root node
{

_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{

if (cur->_kv.first < kv.first)// When the inserted value is larger than the current node , Go to the right
{

parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)// When the inserted value is smaller than the current node , Go to the left
{

parent = cur;
cur = cur->_left;
}
else// When duplicate values occur
{

return false;
}
}
cur = new Node(kv);
cur->_col = RED;// Set the value of the inserted node to red   It's the lowest cost
if (parent->_kv.first < kv.first)// When parent The value ratio in the node kv When I was young ,cur Is the right node of this node
{

parent->_right = cur;
cur->_parent = parent;
}
else// When parent The value ratio in the node kv When it's high ,cur Is the left node of this node
{

parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)// When parent If it exists and is red, it needs to be adjusted
{

Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{

Node* uncle = grandparent->_right;
//uncle It exists and is red
if (uncle && uncle->_col == RED)
{

// The color change continues to adjust upwards
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;

}
//uncle Not present or existing and black
else
{

if (cur == parent->_left)//cur yes parent The left node
{

RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else// If the current node is parent The right of the node
{

RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}

}
else//parent==grandparent->_right
{

Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{

// Color change upward treatment
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle It doesn't exist or it's black
{

if (cur == parent->_right)
{

RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{

RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}

}
}
_root->_col = BLACK;
return false;

}

void InOrder()
{

return _InOrder(_root);
}

bool IsBalance()// Judge whether the binary tree is balanced
{

if (_root && _root->_col == RED)
{

cout << " The root node is not black " << endl;
return false;
}
int banchmark = 0;// Count the number of black nodes in a path
Node* left = _root;// Here, select the leftmost node path
while (left)
{

if (left->_col == BLACK)
{

++banchmark;
}
left = left->_left;
}
int blacknum = 0;
return _IsBalance(_root, banchmark, blacknum);

}

int Height()
{

return _Height(_root);
}

private:
void _InOrder(Node* root)
{

if (root == nullptr)
{

return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}

bool _IsBalance(Node* root, int banchmark, int blacknum)
{

if (root == nullptr)
{

if (banchmark != blacknum)
{

cout << " There are path black nodes that are not equal " << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{

cout << " Continuous red nodes appear " << endl;
return false;
}
if (root->_col == BLACK)
{

blacknum++;
}
return _IsBalance(root->_left, banchmark, blacknum) && _IsBalance(root->_right, banchmark, blacknum);
}

int _Height(Node* root)
{

if (root == nullptr)
{

return 0;
}
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

}

void RotateR(Node* parent)// Right single spin
{

Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{

subLR->_parent = parent;
}
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{

_root = subL;
_root->_parent = nullptr;
}
else
{

if (parentParent->_left == parent)
{

parentParent->_left = subL;
}
else
{

parentParent->_right = subL;
}
subL->_parent = parentParent;

}
}

void RotateL(Node* parent)
{

Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{

subRL->_parent = parent;
}
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{

_root = subR;
_root->_parent = nullptr;
}
else
{

if (parentParent->_left == parent)
{

parentParent->_left = subR;
}
else
{

parentParent->_right = subR;
}
subR->_parent = parentParent;
}

}

private:
Node* _root;
};

``````

The above is the complete code for the simple implementation of the red black tree , Next, a random array is inserted to verify the construction of the red black tree , The test code is as follows ：

``````void TestRBTree()
{

int arr[] = {
2,15,12,74,64,13,15,10,11,13,12,18 };
RBTree<int, int> Node;
for (auto e : arr)
{

Node.Insert(make_pair(e, e));
}
Node.InOrder();
cout << Node.IsBalance() << endl;
cout << Node.Height() << endl;
}
`````` ``````void TestRBTree()
{

vector<int> v;
//int arr[] = { 2,15,12,74,64,13,15,10,11,13,12,18 };
srand(time(0));
int N = 1000000;
for (int i = 0; i < N; i++)
{

v.push_back(rand());
}
RBTree<int, int> Node;
for (auto e : v)
{

Node.Insert(make_pair(e, e));
}
//Node.InOrder();
cout << Node.IsBalance() << endl;
cout << Node.Height() << endl;
}
`````` Test here 1000000 Insert random numbers , Generate binary tree , You can see that he has only 19 Around the floor