current position:Home>Properties and simple realization of red black tree

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 :
 Insert picture description here

		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 .
 Insert picture description here

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 .
 Insert picture description here
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 .
 Insert picture description here

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;
}

 Insert picture description here

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;
}

 Insert picture description here
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

Random recommended