The hand of data structure is red black tree

catalogue

1. Introduction of red black tree

 2. Basic properties of red black tree and definition of node

3. Rotation of red and black trees

4. Insertion of red black tree

Insertion case I

Insertion case II

Insertion case III

Insertion case IV

Red black tree insertion summary:

5. Deletion of red black tree

6. Red black tree summary

7. Summary of red black tree and AVL tree

1. Introduction of red black tree

Red Black Tree is a self balancing binary search tree computer One used in science data structure , the typical use is to realize Associative array.  

The red black tree was created by Rudolf Bayer It was called balanced binary B-trees at that time. Later, it was modified by Leo J. Guibas and Robert Sedgewick to today's "red black tree" in 1978.  

Red black tree is a specialized AVL tree( balanced binary tree ), both maintain the balance of binary search tree through specific operations during insertion and deletion, so as to obtain high search performance.  

Although it is complex, its worst-case running time is also very good, and it is efficient in practice: it can find, insert and delete in O(log n) time. Here n is the number of elements in the tree - from Baidu Encyclopedia

 2. Basic properties of red black tree and definition of node

Red black tree is a binary search tree with red black nodes and self balancing. It must meet the following properties:

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

From property 5, we can infer that if a node has a sunspot node, then the node must have two children

Let's explain the problem in the picture:

From property 3, we can conclude that there are no continuous red nodes in the red black tree. According to property 4, we can conclude that the number of black nodes in all paths is the same.

We assume that the number from the root node to the leaf node is N, then the shortest path is all composed of black nodes, that is, the length is N

The longest path is composed of red and black alternately. In this path, the number of red nodes and black tree nodes is the same. According to property 4, we can get that the length of the longest path is 2N, so the longest path in the black tree will not exceed twice the shortest path, so an approximate balance is achieved.

Let's judge whether a tree is a red black tree:

Obviously, this tree is not a red black tree. There are two paths from root node 55 to 38, one is to empty and the other is to 25. Obviously, the number of black nodes in the two paths is different, one is 3 and the other is 2 So this tree is not a red black tree

 2.2

If we want to insert a node, do we want it to be a red node or a black tree node? Obviously, it is a red node. If a black node is inserted, it will destroy the same number of black nodes in any path in the red black tree. In response to this situation, it becomes very troublesome for us to adjust the red black tree. Therefore, we want the inserted node to be a red node.

Corresponding node code:

enum Colour
{
	RED,
	BLACK,
};
template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K,V>&kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
	RBTreeNode<K, V>* _left;//Left pointer
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;//Father pointer
	pair<K, V>_kv;
	Colour _col;//Each node must have a color
};

3. Rotation of red and black trees

1. Left hand rotation:

Firstly, disconnect the relationship between node PL and right child node g, and point the reference of its right child node to node C2; Then, disconnect the relationship between node g and left child node C2, and point the application of the left child node of G to node pl.

2. Right hand rotation

Firstly, disconnect the relationship between node g and left child node PL, and point the reference of its left child node to node C2; Then, disconnect the relationship between node PL and right child node C2, and point the application of the right child node of PL to node G.

Corresponding

void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curR = cur->_right;//Right subtree of cur
		Node* pparent = parent->_parent;//Save parent's parent node

		//Link the cur right subtree to the left of the parent
		parent->_left = curR;
		if (curR)
			curR->_parent = parent;

		//Connect the parent to the right side of cur
		cur->_right = parent;
		parent->_parent = cur;

		//Link cur to pparent
		if (pparent == nullptr)//cur becomes a new root
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else//pparent is not root
		{
			cur->_parent = pparent;
			if (parent == pparent->_left)//Parent is on the left side of the parent node
			{
				pparent->_left = cur;
			}
			else
			{
				pparent->_right = cur;
			}
		}


	}
	//Sinistral
	void RotateL(Node* parent)//Sinistral
	{
		Node* cur = parent->_right;//The right becomes higher and cannot be empty
		Node* curL = cur->_left;
		Node* pprent = parent->_parent;

		//curL is connected to the parent
		parent->_right = curL;
		if (curL)
			curL->_parent = parent;

		//Connect parent to cur
		cur->_left = parent;
		parent->_parent = cur;

		//cur link to pprent
		if (pprent == nullptr)//root
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else//Not root
		{
			cur->_parent = pprent;
			//Determine which side the link is on
			if (pprent->_left == parent)
			{
				pprent->_left = cur;
			}
			else
			{
				pprent->_right = cur;
			}
		}
	}

4. Insertion of red black tree

Let's take a look at a picture and learn some nouns

The idea of inserting red black tree is basically the same as that of searching binary tree, but there are more adjustment operations than searching binary tree.

1. Find the insertion position according to the size

2. Create the corresponding node and link with the parent

3. Adjust the red black tree

Insertion case I

The inserted is an empty tree, and the node is built directly and returned.

Insertion case II

The parent node of the inserted node is a black node: insert 66 this node

We found that his father was a black node. At this time, it did not violate the basic properties of black mangrove, and the insertion ended.

Insertion case III

After insertion, you need to change color without rotation, that is, the father of the inserted node is red and the uncle node is red.

Insert 51 this node

We find that his father node is red and his uncle node is red. At this time, we only need to turn the father node and uncle node black, turn the grandfather node red, and check whether it violates the rules of the red black tree from the grandfather node.

After the end, the whole tree is like this:

Insertion case IV

The inserted node is red or its parent is not black.

At this time, the insertion can be divided into four cases:

Case 1: the insertion node is the father's left child and the father is the grandfather's left child

1. Insert 65 nodes

At this time, the parent node and the insertion node form two continuous red nodes, and at the same time, on the left (LL type), it is necessary to rotate the parent node to the right and change color. Color change: change the parent node to black and the grandfather node to red

Case 2: the insertion node is the right child of the father and the father is the left child of the grandfather.

Insert node 67:

At this time, the parent node and the insertion node form two continuous red nodes, and one on the left and one on the right is a broken line (LR), which needs double rotation and color change processing. First perform a left single rotation on the parent node and a right single rotation on the grandfather node. Set the color of the parent node to black and the grandfather node to red.

Case 3:

The parent node is the right child of the grandfather node and the insertion node is the right child of the parent node

Insert node 70:

At this time, the insertion node and the parent node form two red nodes, which are RR type on the right at the same time. We just need to carry out a left single rotation and color change treatment on them. Change the color of the father to black and the color of the grandfather node to red.

Case 4:

Father's Day is the right child of the grandfather node and the insertion node is the father's left child.

Insert 68 this node:

The parent node and the insertion node form two continuous red nodes, which belong to RL type. At this time, we only need to make a right single rotation for our father and a left single selection for our grandfather.

Color change: change the parent node to black and the grandfather node to red.

Red black tree insertion summary:

No adjustment requiredJust change colorRotation + discoloration
The parent node of the inserted node is blackThe father of the inserted node is red and the uncle node is redThe parent node is red and the uncle node is black. Insert the left child node (left rotation)
nothingnothingThe parent node is red, the left node, and the uncle node is black. Insert the right child node (left and right double rotation)
nothingnothingThe parent node is red and the uncle node is black. Insert the right child node (left rotation)
nothingnothingThe parent node is a red right node, and the uncle node is a black one. Insert the left child node (right left double spin)

Corresponding insertion code:

pair<Node* ,bool>Insert(const pair<K, V>& kv) {
		if (!_root) {//Case 1 empty tree
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}
		Node* parent = nullptr;
		Node* cur = _root;//Find the corresponding position by the size of the value
		while (cur) {
			if (cur->_kv.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				return make_pair(cur, false);
			}
		}
	     Node*newnode = new Node(kv);
		 newnode->_col = RED;
		if (parent->_kv.first < kv.first) {//Link with parent node
			parent->_right= newnode;
			newnode->_parent = parent;
		}
		else {
			parent->_left = newnode;
			newnode->_parent = parent;
		}
		cur = newnode;

		while (parent&&parent->_col==RED)//The father exists and the father is red and needs to be handled
		{
			//The key is to see your uncle
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left) {//
				Node* uncle = grandfather->_right;
				//uncle exists and is red,
				//Turn my grandfather red and my grandfather's two children black
				if (uncle && uncle->_col == RED) {//Situation III
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else {//Uncle doesn't exist, or uncle doesn't exist
					if (cur == parent->_left) {//Case 1 in case 4
						RotateR(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else {//Case 2 in case 4
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}

			else {//It's grandpa's right
				Node* uncle = grandfather->_left;//Situation III
				if (uncle && uncle->_col == RED) {
					uncle->_col = BLACK;
					parent->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else {
					if (cur == parent->_right) {//Case 3 of case 4;
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else {//Minor case 4 in case 4
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
						
					}
					break;
				}
			}
		}
		_root->_col = BLACK;//In any case, the root node is black
		return make_pair(newnode,true);
	}

 5. Deletion of red black tree

The deletion of red black tree is much more complex than the insertion

The general steps are as follows:

1. Find the node according to the nature of binary search tree

2. Find a node to replace it

3. Adjust the red black tree to make it balanced

Let's first review the deletion of binary search tree:

Case 1: if the deleted node has no child nodes, it can be deleted directly

Case 2: if the deleted node has only one child node, replace the deleted node with a child node

Case 3: if the deleted node has two child nodes, replace the deleted node with a successor node (greater than the smallest node of the deleted node)

Case 3 can be converted to case 1 for processing.

Let's look at the deletion of red black tree

Case 1:

The node to be deleted is a red leaf node: delete 69 this red leaf node

You can delete it directly

Situation 2

Delete the black leaf node, the parent node is red, the brother node is black, and there is no red child node

We want to delete the node 64, but we can change it to delete the leaf node 63. At this time, we only need to change the color to change the parent node to black and the brother node to red.  

Case 3: the deleted node is a black leaf node, and the sibling node is black and has a red child node

We want to delete 88 this black leaf node. After deletion, it is unbalanced. We found that his brother node is black and has a red child node, so we borrowed it from the brother node. How to borrow it? We found that the brother node and his red leaf node are in a straight line, so we just need to carry out a right single rotation and color change on 80.

Discoloration: the rotated central node inherits the color of the original parent node, and the rotated left and right nodes are dyed into a black tree

There is another small case in case 3: the brother node and the red child node are not in a straight line: that is, on the right of the brother node

Similarly, delete 88 node. The difference between this situation and the above situation is that the red child node of the brother node is not on a certain straight line. At this time, we need to carry out double rotation processing, i.e. left and right double rotation + color change processing, that is, first carry out a left single rotation on the brother node and a right single rotation on the father node, To change color, you only need to inherit the color of the original parent node from the central node, and the left and right nodes turn black after rotation.

There are three cases. The left child whose deleted node is the Father also does the same, but the rotation mode is different. The old fellow can draw pictures on their own, if necessary, leave a message in the comments area.

Situation 4

Delete the black leaf node. The brother node is a black tree with two red nodes.

This situation can be divided into two cases: the deleted node is the father's left child and the deleted node is the father's right child. Here is only one example:

Here, we want to delete 88 node. At this time, its brother node has only {2 black tree nodes. At this time, we can perform double rotation or single rotation. Here, I rotate single rotation, that is, right single rotation.

Right single rotation is performed on the parent node. The rotated central node inherits the color of the parent node, and the left and right nodes turn black after rotation.

 

Case 5:

The deleted node is a black tree node and has a red sub node.

This situation is very simple. Replace the deleted node with a red child node and turn the red child node into black.

Delete 80 this node:

 

 

Case 6:

The deleted node is a leaf node, but the sibling node is a red node:

Delete 88 this node:

At this time, his brother node is red. Here, our 88 real black brother node is actually 76. Here, we force 88 and 76 to be brothers. We only need to make a right single spin on the parent node. The code written before calling and applying:

 

In the case of left single selection, the left parent of the deleted node is on the left, which is just the rotation direction is different. The old fellow can draw down their own paintings.

Case 7:

Delete the black leaf node, the parent node is black, the brother node is black, and there is no red child node:

Delete 88 this node

First, turn the sibling node red and call the code above. Note that there may be nodes above node 80 in practice.

Corresponding code:

	//Delete function
	bool Erase(const K& key)
	{
		//Used to traverse a binary tree
		Node* parent = nullptr;
		Node* cur = _root;
		//Used to mark the actual node to be deleted and its parent node
		Node* delParentPos = nullptr;
		Node* delPos = nullptr;
		while (cur)
		{
			if (key < cur->_kv.first) //The given key value is less than the key value of the current node
			{
				//Go to the left subtree of this node
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_kv.first) //The given key value is greater than the key value of the current node
			{
				//Go to the right subtree of the node
				parent = cur;
				cur = cur->_right;
			}
			else //The node to be deleted was found
			{
				if (cur->_left == nullptr) //The left subtree of the node to be deleted is empty
				{
					if (cur == _root) //The node to be deleted is the root node
					{
						_root = _root->_right; //Let the right subtree of the root node be the new root node
						if (_root)
						{
							_root->_parent = nullptr;
							_root->_col = BLACK; //The root node is black
						}
						delete cur; //Delete original root node
						return true;
					}
					else
					{
						delParentPos = parent; //Mark the parent node of the actual deleted node
						delPos = cur; //Mark the node actually deleted
					}
					break; //Adjust the red black tree and actually delete the nodes
				}
				else if (cur->_right == nullptr) //The right subtree of the node to be deleted is empty
				{
					if (cur == _root) //The node to be deleted is the root node
					{
						_root = _root->_left; //Let the left subtree of the root node be the new root node
						if (_root)
						{
							_root->_parent = nullptr;
							_root->_col = BLACK; //The root node is black
						}
						delete cur; //Delete original root node
						return true;
					}
					else
					{
						delParentPos = parent; //Mark the parent node of the actual deleted node
						delPos = cur; //Mark the node actually deleted
					}
					break; //Adjust the red black tree and actually delete the nodes
				}
				else //The left and right subtrees of the node to be deleted are not empty
				{
					//Substitution deletion
					//Find the node with the smallest key value in the right subtree of the node to be deleted as the actual deleted node
					Node* minParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minParent = minRight;
						minRight = minRight->_left;
					}
					cur->_kv.first = minRight->_kv.first; //Change the key of the node to be deleted to the key of minRight
					cur->_kv.second = minRight->_kv.second; //Change the value of the node to be deleted to the value of minRight
					delParentPos = minParent; //Mark the parent node of the actual deleted node
					delPos = minRight; //Mark the node actually deleted
					break; //Adjust the red black tree and actually delete the nodes
				}
			}
		}
		if (delPos == nullptr) //delPos has not been modified, which means that the node to be deleted is not found
		{
			return false;
		}

		//Record the node to be deleted and its parent node (for subsequent actual deletion)
		Node* del = delPos;
		Node* delP = delParentPos;

		//Adjust red black tree
		if (delPos->_col == BLACK) //Black nodes are deleted
		{
			if (delPos->_left) //The node to be deleted has a red left child (cannot be black)
			{
				delPos->_left->_col = BLACK; //Turn the red left child black
			}
			else if (delPos->_right) //The node to be deleted has a red right child (cannot be black)
			{
				delPos->_right->_col = BLACK; //Turn the red right child black
			}
			else //The left and right of the node to be deleted are empty
			{
				while (delPos != _root) //It may be adjusted to the root node
				{
					if (delPos == delParentPos->_left) //The node to be deleted is the left child of its parent node
					{
						Node* brother = delParentPos->_right; //A sibling node is the right child of its parent node
						//: brother is red
						if (brother->_col == RED)
						{
							delParentPos->_col = RED;
							brother->_col = BLACK;
							RotateL(delParentPos);
							//Need to continue processing
							brother = delParentPos->_right; //Update brother (otherwise the code that executes other situations in this loop will make an error)
						}
						//: brother is black, and its left and right children are black or empty
						if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
							&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
						{
							brother->_col = RED;
							if (delParentPos->_col == RED)
							{
								delParentPos->_col = BLACK;
								break;
							}
							//Need to continue processing
							delPos = delParentPos;
							delParentPos = delPos->_parent;
						}
						else
						{
							//: brother is black, and its left child is red node, and its right child is black node or empty
							if ((brother->_right == nullptr) || (brother->_right->_col == BLACK))
							{
							/*	brother->_left->_col = BLACK;
								brother->_col = RED;*/
								RotateR(brother);
								//Need to continue processing
								brother = delParentPos->_right; //Update brother (otherwise an error will occur when executing the code in case 4 below)
							}

							//: brother is black, and its right child is red
							brother->_col = delParentPos->_col;
							delParentPos->_col = BLACK;
							brother->_right->_col = BLACK;
							RotateL(delParentPos);
							break; //Situation four the adjustment will be finished after execution.
						}
					}
					else //delPos == delParentPos->_ Right / / the node to be deleted is the left child of its parent node
					{
						Node* brother = delParentPos->_left; //A sibling node is the left child of its parent node
						//: brother is red
						if (brother->_col == RED) //brother is red
						{
							delParentPos->_col = RED;
							brother->_col = BLACK;
							RotateR(delParentPos);
							//Need to continue processing
							brother = delParentPos->_left; //Update brother (otherwise the code that executes other situations in this loop will make an error)
						}
						//: brother is black, and its left and right children are black or empty
						if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
							&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
						{
							brother->_col = RED;
							if (delParentPos->_col == RED)
							{
								delParentPos->_col = BLACK;
								break;
							}
							//Need to continue processing
							delPos = delParentPos;
							delParentPos = delPos->_parent;
						}
						else
						{
							//: brother is black, and its right child is red node, and its left child is black node or empty
							if ((brother->_left == nullptr) || (brother->_left->_col == BLACK))
							{
								/*brother->_right->_col = BLACK;
								brother->_col = RED;*/
								RotateL(brother);
								//Need to continue processing
								brother = delParentPos->_left; //Update brother (otherwise an error will occur when executing the code in case 4 below)
							}
							//: brother is black and its left child is red
							brother->_col = delParentPos->_col;
							delParentPos->_col = BLACK;
							brother->_left->_col = BLACK;
							RotateR(delParentPos);
							break; //Situation four the adjustment will be finished after execution.
						}
					}
				}
			}
		}
		//Actual deletion
		if (del->_left == nullptr) //The left subtree of the actually deleted node is empty
		{
			if (del == delP->_left) //The actual deleted node is the left child of its parent node
			{
				delP->_left = del->_right;
				if (del->_right)
					del->_right->_parent = delP;
			}
			else //The actual deleted node is the right child of its parent node
			{
				delP->_right = del->_right;
				if (del->_right)
					del->_right->_parent = delP;
			}
		}
		else //The right subtree of the actual deleted node is empty
		{
			if (del == delP->_left) //The actual deleted node is the left child of its parent node
			{
				delP->_left = del->_left;
				if (del->_left)
					del->_left->_parent = delP;
			}
			else //The actual deleted node is the right child of its parent node
			{
				delP->_right = del->_left;
				if (del->_left)
					del->_left->_parent = delP;
			}
		}
		delete del; //Actually delete node
		return true;
	}

 6. Red black tree summary

To sum up, the self balancing treatment after red black tree deletion can be summarized as follows:

  1. Self digestion that you can handle
  2. If you can't handle it by yourself, ask your brother for help
  3. If brothers can't help, they can find distant relatives through their parents.

Haha, is it very similar to reality? When we have difficulties, we should first solve them ourselves. If we are unable to help, we should always find brothers and sisters. If we can't even help our brothers and sisters, we can go to distant relatives. The memory here should be easy to remember ~

7. Summary of red black tree and AVL tree

 

Finally, how can we verify the red black tree?

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

Back to the rule of red black tree, we only need to verify the first four points. The difficulty lies in verifying property 4. We can first count the number of black nodes in a path and see whether the number of black nodes is equal in other paths of the variable red black tree

Corresponding code:

bool CheckBlance() {
		if (!_root) {

			return true;
		}
		if (_root->_col == RED) {
			cout << "The root node is red" << endl;
		}
		int blacknum = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK) {
				blacknum++;
			}
			left = left->_left;
		}
		int Count = 0;
		return _CheckBlance(_root, blacknum, Count);
	}
	bool _CheckBlance(Node* root, int blackNum, int Count) {
		if (!root) {
			if (Count != blackNum) {
				cout << "The number of black nodes is not equal" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED) {//Continuous red nodes
			return false;
		}
		if (root->_col == BLACK) {
			Count++;
		}
		return _CheckBlance(root->_left, blackNum, Count) && _CheckBlance(root->_right, blackNum, Count);
	}

Code summary:

#pragma once
#include<iostream>
using namespace std;
enum Colour
{
	RED,
	BLACK,
};
template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K,V>&kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V>_kv;
	Colour _col;
};
template<class K,class V>
class RBTree {
	typedef RBTreeNode<K, V> Node;
public:
	pair<Node* ,bool>Insert(const pair<K, V>& kv) {
		if (!_root) {
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (cur->_kv.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				return make_pair(cur, false);
			}
		}
	     Node*newnode = new Node(kv);
		 newnode->_col = RED;
		if (parent->_kv.first < kv.first) {
			parent->_right= newnode;
			newnode->_parent = parent;
		}
		else {
			parent->_left = newnode;
			newnode->_parent = parent;
		}
		cur = newnode;

		while (parent&&parent->_col==RED)//The father exists and the father is red and needs to be handled
		{
			//The key is to see your uncle
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left) {
				Node* uncle = grandfather->_right;
				//uncle exists and is red,
				//Turn my grandfather red and my grandfather's two children black
				if (uncle && uncle->_col == RED) {
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else {//Uncle doesn't exist, or uncle doesn't exist
					if (cur == parent->_left) {//Single rotation
						RotateR(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else {
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}

			else {//It's grandpa's right
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED) {
					uncle->_col = BLACK;
					parent->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else {
					if (cur == parent->_right) {
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else {
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
						
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(newnode,true);
	}
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curR = cur->_right;//Right subtree of cur
		Node* pparent = parent->_parent;//Save parent's parent node

		//Link the cur right subtree to the left of the parent
		parent->_left = curR;
		if (curR)
			curR->_parent = parent;

		//Connect the parent to the right side of cur
		cur->_right = parent;
		parent->_parent = cur;

		//Link cur to pparent
		if (pparent == nullptr)//cur becomes a new root
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else//pparent is not root
		{
			cur->_parent = pparent;
			if (parent == pparent->_left)//Parent is on the left side of the parent node
			{
				pparent->_left = cur;
			}
			else
			{
				pparent->_right = cur;
			}
		}


	}
	//Sinistral
	void RotateL(Node* parent)//Sinistral
	{
		Node* cur = parent->_right;//The right becomes higher and cannot be empty
		Node* curL = cur->_left;
		Node* pprent = parent->_parent;

		//curL is connected to the parent
		parent->_right = curL;
		if (curL)
			curL->_parent = parent;

		//Connect parent to cur
		cur->_left = parent;
		parent->_parent = cur;

		//cur link to pprent
		if (pprent == nullptr)//root
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else//Not root
		{
			cur->_parent = pprent;
			//Determine which side the link is on
			if (pprent->_left == parent)
			{
				pprent->_left = cur;
			}
			else
			{
				pprent->_right = cur;
			}
		}
	}
	bool CheckBlance() {
		if (!_root) {

			return true;
		}
		if (_root->_col == RED) {
			cout << "The root node is red" << endl;
		}
		int blacknum = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK) {
				blacknum++;
			}
			left = left->_left;
		}
		int Count = 0;
		return _CheckBlance(_root, blacknum, Count);
	}
	bool _CheckBlance(Node* root, int blackNum, int Count) {
		if (!root) {
			if (Count != blackNum) {
				cout << "The number of black nodes is not equal" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED) {//Continuous red nodes
			return false;
		}
		if (root->_col == BLACK) {
			Count++;
		}
		return _CheckBlance(root->_left, blackNum, Count) && _CheckBlance(root->_right, blackNum, Count);
	}
	//Delete function
	bool Erase(const K& key)
	{
		//Used to traverse a binary tree
		Node* parent = nullptr;
		Node* cur = _root;
		//Used to mark the actual node to be deleted and its parent node
		Node* delParentPos = nullptr;
		Node* delPos = nullptr;
		while (cur)
		{
			if (key < cur->_kv.first) //The given key value is less than the key value of the current node
			{
				//Go to the left subtree of this node
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_kv.first) //The given key value is greater than the key value of the current node
			{
				//Go to the right subtree of the node
				parent = cur;
				cur = cur->_right;
			}
			else //The node to be deleted was found
			{
				if (cur->_left == nullptr) //The left subtree of the node to be deleted is empty
				{
					if (cur == _root) //The node to be deleted is the root node
					{
						_root = _root->_right; //Let the right subtree of the root node be the new root node
						if (_root)
						{
							_root->_parent = nullptr;
							_root->_col = BLACK; //The root node is black
						}
						delete cur; //Delete original root node
						return true;
					}
					else
					{
						delParentPos = parent; //Mark the parent node of the actual deleted node
						delPos = cur; //Mark the node actually deleted
					}
					break; //Adjust the red black tree and actually delete the nodes
				}
				else if (cur->_right == nullptr) //The right subtree of the node to be deleted is empty
				{
					if (cur == _root) //The node to be deleted is the root node
					{
						_root = _root->_left; //Let the left subtree of the root node be the new root node
						if (_root)
						{
							_root->_parent = nullptr;
							_root->_col = BLACK; //The root node is black
						}
						delete cur; //Delete original root node
						return true;
					}
					else
					{
						delParentPos = parent; //Mark the parent node of the actual deleted node
						delPos = cur; //Mark the node actually deleted
					}
					break; //Adjust the red black tree and actually delete the nodes
				}
				else //The left and right subtrees of the node to be deleted are not empty
				{
					//Substitution deletion
					//Find the node with the smallest key value in the right subtree of the node to be deleted as the actual deleted node
					Node* minParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minParent = minRight;
						minRight = minRight->_left;
					}
					cur->_kv.first = minRight->_kv.first; //Change the key of the node to be deleted to the key of minRight
					cur->_kv.second = minRight->_kv.second; //Change the value of the node to be deleted to the value of minRight
					delParentPos = minParent; //Mark the parent node of the actual deleted node
					delPos = minRight; //Mark the node actually deleted
					break; //Adjust the red black tree and actually delete the nodes
				}
			}
		}
		if (delPos == nullptr) //delPos has not been modified, which means that the node to be deleted is not found
		{
			return false;
		}

		//Record the node to be deleted and its parent node (for subsequent actual deletion)
		Node* del = delPos;
		Node* delP = delParentPos;

		//Adjust red black tree
		if (delPos->_col == BLACK) //Black nodes are deleted
		{
			if (delPos->_left) //The node to be deleted has a red left child (cannot be black)
			{
				delPos->_left->_col = BLACK; //Turn the red left child black
			}
			else if (delPos->_right) //The node to be deleted has a red right child (cannot be black)
			{
				delPos->_right->_col = BLACK; //Turn the red right child black
			}
			else //The left and right of the node to be deleted are empty
			{
				while (delPos != _root) //It may be adjusted to the root node
				{
					if (delPos == delParentPos->_left) //The node to be deleted is the left child of its parent node
					{
						Node* brother = delParentPos->_right; //A sibling node is the right child of its parent node
						//: brother is red
						if (brother->_col == RED)
						{
							delParentPos->_col = RED;
							brother->_col = BLACK;
							RotateL(delParentPos);
							//Need to continue processing
							brother = delParentPos->_right; //Update brother (otherwise the code that executes other situations in this loop will make an error)
						}
						//: brother is black, and its left and right children are black or empty
						if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
							&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
						{
							brother->_col = RED;
							if (delParentPos->_col == RED)
							{
								delParentPos->_col = BLACK;
								break;
							}
							//Need to continue processing
							delPos = delParentPos;
							delParentPos = delPos->_parent;
						}
						else
						{
							//: brother is black, and its left child is red node, and its right child is black node or empty
							if ((brother->_right == nullptr) || (brother->_right->_col == BLACK))
							{
							/*	brother->_left->_col = BLACK;
								brother->_col = RED;*/
								RotateR(brother);
								//Need to continue processing
								brother = delParentPos->_right; //Update brother (otherwise an error will occur when executing the code in case 4 below)
							}

							//: brother is black, and its right child is red
							brother->_col = delParentPos->_col;
							delParentPos->_col = BLACK;
							brother->_right->_col = BLACK;
							RotateL(delParentPos);
							break; //Situation four the adjustment will be finished after execution.
						}
					}
					else //delPos == delParentPos->_ Right / / the node to be deleted is the left child of its parent node
					{
						Node* brother = delParentPos->_left; //A sibling node is the left child of its parent node
						//: brother is red
						if (brother->_col == RED) //brother is red
						{
							delParentPos->_col = RED;
							brother->_col = BLACK;
							RotateR(delParentPos);
							//Need to continue processing
							brother = delParentPos->_left; //Update brother (otherwise the code that executes other situations in this loop will make an error)
						}
						//: brother is black, and its left and right children are black or empty
						if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
							&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
						{
							brother->_col = RED;
							if (delParentPos->_col == RED)
							{
								delParentPos->_col = BLACK;
								break;
							}
							//Need to continue processing
							delPos = delParentPos;
							delParentPos = delPos->_parent;
						}
						else
						{
							//: brother is black, and its right child is red node, and its left child is black node or empty
							if ((brother->_left == nullptr) || (brother->_left->_col == BLACK))
							{
								/*brother->_right->_col = BLACK;
								brother->_col = RED;*/
								RotateL(brother);
								//Need to continue processing
								brother = delParentPos->_left; //Update brother (otherwise an error will occur when executing the code in case 4 below)
							}
							//: brother is black and its left child is red
							brother->_col = delParentPos->_col;
							delParentPos->_col = BLACK;
							brother->_left->_col = BLACK;
							RotateR(delParentPos);
							break; //Situation four the adjustment will be finished after execution.
						}
					}
				}
			}
		}
		//Actual deletion
		if (del->_left == nullptr) //The left subtree of the actually deleted node is empty
		{
			if (del == delP->_left) //The actual deleted node is the left child of its parent node
			{
				delP->_left = del->_right;
				if (del->_right)
					del->_right->_parent = delP;
			}
			else //The actual deleted node is the right child of its parent node
			{
				delP->_right = del->_right;
				if (del->_right)
					del->_right->_parent = delP;
			}
		}
		else //The right subtree of the actual deleted node is empty
		{
			if (del == delP->_left) //The actual deleted node is the left child of its parent node
			{
				delP->_left = del->_left;
				if (del->_left)
					del->_left->_parent = delP;
			}
			else //The actual deleted node is the right child of its parent node
			{
				delP->_right = del->_left;
				if (del->_left)
					del->_left->_parent = delP;
			}
		}
		delete del; //Actually delete node
		return true;
	}

private:
	Node* _root=NULL;
};

reference material:

(1269 messages) red black tree (c + + implementation)_ 2021dragon blog - CSDN blog_ Red black tree c++

Keywords: Algorithm data structure

Added by B-truE on Mon, 14 Feb 2022 08:59:06 +0200