current position：Home>Properties and simple realization of red black tree
Properties and simple realization of red black tree
2022-06-24 09:53:32【HHYX.】
The property and simple realization of red black tree
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 ：
- Each node is either red or black
- The root node is black
- If a node is red , Then its two child nodes are black
- For each node , A simple path from this node to all its descendant leaf nodes , All contain the same number of black nodes
- 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 ：
- 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
- 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
copyright notice
author[HHYX.],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/175/202206240836485399.html
The sidebar is recommended
- The birth of atomic quantum circuit marks a major breakthrough in quantum computer technology
- How to locate lock waiting in Dameng database
- Easily play with IOS 16 lock screen interface
- How to open an account online for new bonds? Please bless me
- React usestate storage function
- What else can the project implementation engineer do without the project?
- Precautions when applying to upgrade springcloud Version (Dalston to Edgware)
- A docker implemented by shell script
- Android studio simulator modify system language / enable Developer mode / customize resolution and size
- Android uses itemtouchhelper to realize item dragging position exchange and side sliding deletion of recyclerview
guess what you like
Why does the menu bar created with QT in vs report errors
Oauth2 released methods cannot be accessed
About pyopengl: why is the obj model (dinosaur) read and displayed like this? How can it display the same material effect as the teapot
CSS problem, card jitter
Jpprofiler monitors the problem of excessive memory deployed under Tomcat
A HashMap talked with the interviewer for half an hour
Java interview experience in a small company
I have made an application to visually generate echarts code, so I don't have to look at complex documents anymore (attached with project source code)
Can you do it as soon as possible? There is not much time
For non front and rear end separation projects, how can the front and rear ends be separated and packaged separately?
Random recommended
- () is a linear table that restricts the internal structure of data elements to only one character. A. Stack B. queue C. string D. array
- TS cannot find global variable for NPM package
- Java, what should I do if there is an edit configuration in the idea when it runs
- C++ code. Freshmen have just come into contact with this language
- Tnsnames Ora file configuration
- Handling method of Oracle data file header SCN inconsistency
- Oracle database listening file configuration
- Oracle database expdp only exports tables
- Windows method for checking network port occupation and kill process
- Oracle viewing data file header SCN information
- Ora-28000 error after upgrading Oracle 12C to 19C
- [talk about serviceregistryendpoint of springcloud]
- [springcloud service registration and anti registration AOP interception]
- [springboot source code analysis - @endpoint annotation validation principle analysis]
- [elegant offline and grayscale release of spring cloud]
- PostgreSQL
- Reactnative 0.69 release
- The new design can be called a new generation. The gradient borderless grille has a high appearance value. The application drawing of Changan Ruicheng plus
- Linux general command summary
- Render external link address URL video page via iframe - Vue
- Detailed explanation of Linux system tuning (VII) -- network status viewing command nethogs
- Vue failed to parse source for import analysis because the content contains invalid JS syntax
- Differences between front-end set and map
- Difference between front-end foreach and map
- Front end array flattening
- How the front end judges the data type
- Front end CSS style expand and collapse
- Front end array de duplication
- Front end throttling and anti shake
- Analysis of 43 cases of MATLAB neural network: Chapter 33 prediction algorithm of fuzzy neural network -- water quality evaluation of Jialing River
- Java & c++ problem solving and expansion -- leetcode30 Concatenate substrings of all words [new knowledge of Mo]
- Eclipse customizes and calls the header file [c/c++]
- Detailed explanation of Vue Foundation
- Unity determines whether all toggles are selected or not
- Program reverse output and print results
- Ubuntu modify time zone
- Linux Installation maven
- Okhttp source code analysis of Android network framework
- Android adds system service interfaces and test cases
- Ubuntu deployment according to Vue version