Data structure red-black tree (RBTree)

Article directory

Data structure red-black tree (RBTree)
1. The concept of red-black trees
2. Properties of red-black trees
3. Definition of red-black tree nodes
4. Red-black tree structure
5. Insertion operation of red-black tree
- 1. Insert new nodes according to the tree rules of binary search
- 2. Check whether the properties of the red-black tree cause damage after the new node is inserted.
- - Situation one
  - Situation 2
- 3. Insert code
6. Verification of red-black trees
7. Overall code (including tests)

1. The concept of red-black tree

A red-black tree is a binary search tree, but adds a storage bit to each node to represent the color of the node, which can be Red or Black, by coloring each node on any path from the root to the leaves. Due to the constraints of the method, the red-black tree ensures that no path will be twice as long as other paths, so it is close to balance.

2. Properties of red-black trees

Each node is either red or black
The root node is black
If a node is red, then its two children are black
For each node, the simple paths from the node to all its descendant leaf nodes contain the same number of black nodes.
Each leaf node is black (the leaf node here refers to the empty node)

Thinking: Why can a red-black tree guarantee that if the above properties are met, the number of nodes in its longest path will not exceed twice the number of nodes in the shortest path?

3. Definition of red-black tree nodes

enum Color
{<!-- -->
Red,
Black
};

template <class K,class V>
struct TreeNode
{<!-- -->
TreeNode(const pair<K, V> & amp; kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(Red)
{<!-- -->}

TreeNode* _left;
TreeNode* _right;
TreeNode* _parent;
pair<K, V> _kv;
Color_col;
};

Thinking: In the definition of nodes, why should the default color of nodes be set to red?

4. Red-black tree structure

In order to simplify the subsequent implementation of associative containers, a head node is added to the implementation of the red-black tree, because the following node must be black. In order to distinguish it from the root node, the head node is colored black, and the pParent field of the head node is Points to the root node of the red-black tree, the pLeft field points to the smallest node in the red-black tree, and the _pRight field points to the largest node in the red-black tree, as follows:

5. Insertion operation of red-black tree

The red-black tree is based on the binary search tree with its balance constraints, so the insertion of the red-black tree can be divided into two steps:

1. Insert new nodes according to the tree rules of binary search

First find the location of the inserted node according to the rules of searching the binary tree

bool Insert(const pair<K, V> & amp; kv)
{<!-- -->
if (_root == nullptr)
{<!-- -->
_root = new Node(kv);
_root->_col = Black;
return true;
}

Node* cur = _root;
Node* parent = nullptr;

while (cur)
{<!-- -->
if (cur->_kv.first > kv.first)
{<!-- -->
parent = cur;
cur = cur->_left;
}
else if(cur->_kv.first < kv.first)
{<!-- -->
parent = cur;
cur = cur->_right;
}
else
{<!-- -->
return false;
}
}

if (parent->_kv.first > kv.first)
{<!-- -->
cur = new Node(kv);
parent->_left = cur;
cur->_parent = parent;
}
else
{<!-- -->
cur = new Node(kv);
parent->_right = cur;
cur->_parent = parent;
}


*************************************************** *****************
}

2. Check whether the properties of the red-black tree cause damage after the new node is inserted

New: Insert red node
1. The parent of the inserted node is black, then it is over. No rules were broken.
2. If the parent of the inserted node is red, then there are consecutive red nodes, which violates rule 3 and needs to be processed.
The key is to look at uncle uncle and several other nodes c p g three colors fixed
Convention: cur is the current node, p is the parent node, g is the grandparent node, and u is the uncle node

Because the default color of a new node is red, therefore: if the color of its parent node is black, it does not violate any properties of the red-black tree, and no adjustment is required; but when the color of the parent node of the newly inserted node is red, it violates the properties Three cannot have red nodes connected together. At this time, we need to discuss the situation of red and black trees:

There are two major categories here (logical classification):

uncle exists and is red (no need to judge the positional relationship)
uncle exists and is black or uncle does not exist (need to determine the positional relationship and continue classification)

But when actually converting it into code, you need to look at the positional relationship between cur, p, g and u to classify, because different positions are adjusted in different ways.

p is on the left of g, u is on the right of g or p is on the right of g, u is on the left of g
If p is on the left, cur is also on the left. Or if p is on the right, cur is also on the right.
If p is on the left, cur is on the right or if p is on the right, cur is on the left

In the case of these three positional relationships, classification is carried out in combination with logical classification.

The following is a classification logic diagram

Situation 1

In this case uncle exists and is red

Scenario 2

Divided into two small situations

curly on the outside of this tree
curly on the inside of this tree

3. Insert code

 bool Insert(const pair<K, V> & amp; kv)
{<!-- -->
if (_root == nullptr)
{<!-- -->
_root = new Node(kv);
_root->_col = Black;
return true;
}

Node* cur = _root;
Node* parent = nullptr;

while (cur)
{<!-- -->
if (cur->_kv.first > kv.first)
{<!-- -->
parent = cur;
cur = cur->_left;
}
else if(cur->_kv.first < kv.first)
{<!-- -->
parent = cur;
cur = cur->_right;
}
else
{<!-- -->
return false;
}
}

if (parent->_kv.first > kv.first)
{<!-- -->
cur = new Node(kv);
parent->_left = cur;
cur->_parent = parent;
}
else
{<!-- -->
cur = new Node(kv);
parent->_right = cur;
cur->_parent = parent;
}

\t\t
while (parent & amp; & amp; parent->_col == Red)
{<!-- -->
if (parent->_col == Black)
{<!-- -->
break;
}

//parent is red, you need to find the grandfather first, and then the uncle
Node* grandparent = parent->_parent;
Node* uncle = nullptr;



//parent is on the left and uncle is on the right
if (grandparent->_left == parent)
{<!-- -->
uncle = grandparent->_right;

\t\t\t\t
//uncle exists and is red
if (uncle & amp; & amp; uncle->_col == Red)
{<!-- -->
parent->_col = Black;
uncle->_col = Black;
grandparent->_col = Red;

//Continue to update upwards
cur = grandparent;
parent = cur->_parent;
}
//uncle exists and is black or uncle does not exist
else
{<!-- -->
//cur is on the left and rotates on the right
if (cur == parent->_left)
{<!-- -->
RotateR(grandparent);

parent->_col = Black;
grandparent->_col = Red;

break;
}
//cur is on the right, double rotation
else
{<!-- -->
RotateL(parent);
RotateR(grandparent);

cur->_col = Black;
grandparent->_col = Red;

break;
}
}
\t\t\t\t

}
//parent is on the right and uncle is on the left
else
{<!-- -->
uncle = grandparent->_left;

//uncle exists and is red
if (uncle & amp; & amp; uncle->_col == Red)
{<!-- -->
parent->_col = uncle->_col = Black;
grandparent->_col = Red;

cur = grandparent;
parent = cur->_parent;
}
//uncle exists and is black or uncle does not exist
else
{<!-- -->
//cur is on the right and rotates left
if (cur == parent->_right)
{<!-- -->
RotateL(grandparent);

parent->_col = Black;
grandparent->_col = Red;

break;
}
//cur is on the left, double rotation
else
{<!-- -->
RotateR(parent);
RotateL(grandparent);

cur->_col = Black;
grandparent->_col = Red;

break;
}

}

}

\t\t\t
}

_root->_col = Black;
return true;
}

6. Verification of red-black tree

According to the rules of the red-black tree, we can traverse the tree in in-order and print values to check whether it complies with the rules, but this alone cannot fully detect it. We need to design a function to detect this tree according to the rules of the red-black tree.

Each node is either red or black
The root node is black
If a node is red, then its two children are black
For each node, the simple paths from the node to all its descendant leaf nodes contain the same number of black nodes.
Each leaf node is black (the leaf node here refers to the empty node)

Rules 1 and 2 only need to check one side at the beginning
Rule 3 will be difficult to judge if there is a difference between them, but we can change our thinking. If the node is red, then its parent node must be black. If it is red, it violates the rule.
Rule 4 needs to be compared with the reference value when each path reaches empty. If it is not equal, it violates the rule. The reference value is to calculate the number of black nodes on a certain path before calling it.

 bool Isbalance()
{<!-- -->
if (_root == nullptr)
{<!-- -->
return true;
}

if (_root->_col == Red)
{<!-- -->
return false;
}

size_t reference = 0;
\t\t
Node* cur = _root;
\t\t
while (cur)
{<!-- -->
if (cur->_col == Black)
{<!-- -->
reference + + ;
}
cur = cur->_left;
}

return _Isbalance(_root, reference, 0);
}


bool _Isbalance(Node* root, size_t reference, size_t bnum)
{<!-- -->
if (root == nullptr)
{<!-- -->
if (bnum != reference)
{<!-- -->
cout << "The number of black nodes in each path is different" << endl;
return false;
}
return true;
}

if (root->_col == Red)
{<!-- -->
if (root->_parent->_col != Black)
{<!-- -->
cout << "Continuous red nodes appear" << endl;
return false;
}
}
else
{<!-- -->
bnum + + ;
}

return _Isbalance(root->_left, reference, bnum) & amp; & amp; _Isbalance(root->_right, reference, bnum);
}

7. Overall code (including tests)

RBTree.h

#include 
using namespace std;

enum Color
{<!-- -->
Red,
Black
};

template <class K,class V>
struct TreeNode
{<!-- -->
TreeNode(const pair<K, V> & amp; kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(Red)
{<!-- -->}

TreeNode* _left;
TreeNode* _right;
TreeNode* _parent;
pair<K, V> _kv;
Color_col;
};

template 
classRBTree
{
typedef TreeNode Node;

public:
bool Insert(const pair & amp; kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = Black;
return true;
}

Node* cur = _root;
Node* parent = nullptr;

while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if(cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}

if (parent->_kv.first > kv.first)
{
cur = new Node(kv);
parent->_left = cur;
cur->_parent = parent;
}
else
{
cur = new Node(kv);
parent->_right = cur;
cur->_parent = parent;
}

\t\t
while (parent & amp; & amp; parent->_col == Red)
{
if (parent->_col == Black)
{
break;
}

//parent is red, you need to find the grandfather first, and then the uncle
Node* grandparent = parent->_parent;
Node* uncle = nullptr;



//parent is on the left and uncle is on the right
if (grandparent->_left == parent)
{
uncle = grandparent->_right;

\t\t\t\t
//uncle exists and is red
if (uncle & amp; & amp; uncle->_col == Red)
{
parent->_col = Black;
uncle->_col = Black;
grandparent->_col = Red;

//Continue to update upwards
cur = grandparent;
parent = cur->_parent;
}
//uncle exists and is black or uncle does not exist
else
{
//cur is on the left and rotates on the right
if (cur == parent->_left)
{
RotateR(grandparent);

parent->_col = Black;
grandparent->_col = Red;

break;
}
//cur is on the right, double rotation
else
{
RotateL(parent);
RotateR(grandparent);

cur->_col = Black;
grandparent->_col = Red;

break;
}
}
\t\t\t\t

}
//parent is on the right and uncle is on the left
else
{
uncle = grandparent->_left;

//uncle exists and is red
if (uncle & amp; & amp; uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandparent->_col = Red;

cur = grandparent;
parent = cur->_parent;
}
//uncle exists and is black or uncle does not exist
else
{
//cur is on the right and rotates left
if (cur == parent->_right)
{
RotateL(grandparent);

parent->_col = Black;
grandparent->_col = Red;

break;
}
//cur is on the left, double rotation
else
{
RotateR(parent);
RotateL(grandparent);

cur->_col = Black;
grandparent->_col = Red;

break;
}

}

}

\t\t\t
}

_root->_col = Black;
return true;
}

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

parent->_right = subRL;
subR->_left = parent;

Node* parentparent = parent->_parent;

if(subRL)
subRL->_parent = parent;

parent->_parent = subR;

if (parent == _root)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
subR->_parent = parentparent;

if (parentparent->_left == parent)
{
parentparent->_left = subR;
}
else
{
parentparent->_right = subR;
}
}
}

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

parent->_left = subLR;
subL->_right = parent;

Node* parentparent = parent->_parent;

if(subLR)
{
subLR->_parent = parent;
}
parent->_parent = subL;

if (parent == _root)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
subL->_parent = parentparent;

if (parentparent->_left == parent)
{
parentparent->_left = subL;
}
else
{
parentparent->_right = subL;
}
}
}


voidInOrder()
{
_InOrder(_root);
cout << endl;
}

boolIsbalance()
{
if (_root == nullptr)
{
return true;
}

if (_root->_col == Red)
{
return false;
}

size_t reference = 0;
\t\t
Node* cur = _root;
\t\t
while (cur)
{
if (cur->_col == Black)
{
reference + + ;
}
cur = cur->_left;
}

return _Isbalance(_root, reference, 0);
}



private:

void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}

bool _Isbalance(Node* root, size_t reference, size_t bnum)
{
if (root == nullptr)
{
if (bnum != reference)
{
cout << "The number of black nodes in each path is different" << endl;
return false;
}
return true;
}

if (root->_col == Red)
{
if (root->_parent->_col != Black)
{
cout << "Continuous red nodes appear" << endl;
return false;
}
}
else
{
bnum + + ;
}

return _Isbalance(root->_left, reference, bnum) & amp; & amp; _Isbalance(root->_right, reference, bnum);
}


Node* _root = nullptr;
};

RBTree.c

#include "RBTree.h"
#define N 1000

int main()
{<!-- -->
srand((unsigned int)time(NULL));

RBTree<int, int> t;
for (int i = 0; i < N; i + + )
{<!-- -->
int sum = rand();

cout << "Insert data as" << sum;

t.Insert(make_pair(sum, sum));
if (t.Isbalance())
{<!-- -->
cout << "Conforms to rules after insertion" << endl;
}
else
{<!-- -->
cout << "It does not comply with the rules after insertion" << endl;
}
}

return 0;
}