数据结构：红黑树的插入实现(C++)

---

一、红黑树

红黑树的概念：
红黑树是一颗二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，该节点颜色不是红色就是黑色。通过对每一条从根节点到叶子结点路径上各个节点颜色的控制，确保没有一条路径会比其它路径长出两倍，因此红黑树是接近平衡。

那红黑树是通过哪些规则来对节点颜色进行控制？

1. 每个节点不是红色就是黑色

2. 根节点是黑色

3. 如果一个节点是红色，则其两个子节点是黑色(不能有连续的红色节点)

4. 对于每个节点，从该节点到其所以叶子结点的路径上，其黑色节点的数目相同

5. 每个叶子结点都是黑色的(此处的叶子结点是空节点(NIL)，方便我们计算路径的个数)
   注意：上述中的路径是从某一节点到NIL节点。如上图8节点到叶子结点就有5条路径，每条路径都有一个黑色节点。

那为什么遵循这5条规则，红黑树就能保证其最长路径中节点的个数不会超过最短路径节点个数的两倍？
我们假设从根节点到叶子结点的黑色节点数为n，那么最短路径不就是连续的黑色节点，最短路径的节点数为n，那么最长路径不就是红黑相间，最长路径的节点数为2n。所以红黑树保证其最长路径中节点的个数不会超过最短路径节点个数的两倍。

---

下面是红黑树节点的定义。

enum
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode(T data = T())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)
	{}

	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _data;
	int _col;
};

该定义中，我们默认将新节点颜色定义为红色，这样我们插入节点时需要维护规则的成本就少。如我们新插入一个红色节点，那么有可能会违背规则3(当其父节点是红色时，有连续红色节点)，这时我们可能需要一些变色和旋转，来维持规则，但如果我们插入节点是黑色，那么我们一定违背4(每条路径上黑色节点数相同)，这时我们可能需要对整个数进行操作。

二、红黑树的插入

红黑树也是一个二叉搜索树，插入新节点与二叉搜索树的操作一样，如果新插入节点比该节点大，新插入节点就去该节点的右子树，反之去该节点的左子树。

if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur != nullptr)
		{
			parent = cur;
			if (cur->_data > data)
			{
				cur = cur->_left;
			}
			else if(cur->_data < data)
			{
				cur = cur->_right;
			}
			else // cur->_data == data
			{
				return false;
			}
		}
		
		cur = new Node(data);
		cur->_parent = parent;
		if (cur->_data > parent->_data)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

---

这里我们主要分析新插入节点后，红黑树的情况和处理。对于旋转，这里并不会详细解析。对于旋转的详细解析在我的AVL树一文中。数据结构：AVLTree的插入和删除的实现

在分析情况前，我们先了解几个节点的含义，方便后续的理解。

接下来的所有情况都与这四个节点有关。

因为我们新插入的节点是红色，如果新插入节点的父节点是黑色，那么红黑树的规则未被破坏。如果新插入节点的父节点是红色，那么就有连续的红色节点。这是我们就要分情况讨论。

while (parent != nullptr && parent->_col != BLACK)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle != nullptr && uncle->_col == RED) // uncle存在且为红色
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK) // uncle不存在 或 umcle存在且为黑
				{
					if (cur == parent->_left) // 同方向
					{
						RotateR(grandfather);

						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // cur == parent->_right 不同方向
					{
						RotateL(parent);
						RotateR(grandfather);
						
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				if (uncle != nullptr && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)
				{
					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; //特殊处理，保证根节点是黑色

则此，红黑树的插入就完成了。

三、代码实现

RBTree.h 文件是红黑树插入的实现
test.cpp 文件是测试用例

// RBTree.h 文件
#pragma once

enum
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode(T data = T())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)
	{}

	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _data;
	int _col;
};

template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	RBTree()
		:_root(nullptr)
	{}

	bool insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur != nullptr)
		{
			parent = cur;
			if (cur->_data > data)
			{
				cur = cur->_left;
			}
			else if(cur->_data < data)
			{
				cur = cur->_right;
			}
			else // cur->_data == data
			{
				return false;
			}
		}
		
		cur = new Node(data);
		cur->_parent = parent;
		if (cur->_data > parent->_data)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		while (parent != nullptr && parent->_col != BLACK)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle != nullptr && uncle->_col == RED) // uncle存在且为红色
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK) // uncle不存在 或 umcle存在且为黑
				{
					if (cur == parent->_left) // 同方向
					{
						RotateR(grandfather);

						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // cur == parent->_right 不同方向
					{
						RotateL(parent);
						RotateR(grandfather);
						
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				if (uncle != nullptr && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)
				{
					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 true;
	}

	// 读取红黑树最左侧节点
	Node* leftMost()
	{
		if (_root == nullptr)
		{
			return nullptr;
		}
		Node* cur = _root;
		while (cur->_left != nullptr)
		{
			cur = cur->_left;
		}
		return cur;
	}

	// 读取红黑树最右侧节点
	Node* rightMost()
	{
		if (_root == nullptr)
		{
			return nullptr;
		}
		Node* cur = _root;
		while (cur->_right != nullptr)
		{
			cur = cur->_right;
		}
		return cur;
	}

	bool isValidRBTree()
	{
		if (_root->_col == RED)
		{
			return false;
		}

		// 找最左边的黑色节点数作为标准比较
		int pathBlack = 0;
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_col == BLACK)
			{
				pathBlack++;
			}

			cur = cur->_left;
		}

		return _isValidRBTree(_root, 0, pathBlack);
	}

	bool _isValidRBTree(Node* root, int blackCount, int pathBlack)
	{
		if (root == nullptr)
		{
			if (blackCount == pathBlack)
				return true;
			else
				return false;
		}

		if (root->_col == RED
			&& root->_parent != nullptr
			&& root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			blackCount++;
		}
		return _isValidRBTree(root->_left, blackCount, pathBlack)
			&& _isValidRBTree(root->_right, blackCount, pathBlack);
	}


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

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

		parent->_parent = subL;
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}
		if (pparent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
			subL->_parent = pparent;
		}
	}

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

		parent->_right = subRL;
		subR->_left = parent;
		
		parent->_parent = subR;
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		if (pparent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
			subR->_parent = pparent;
		}
	}

private:
	Node* _root;
};

---

//test.cpp 文件
#include <iostream>
#include <vector>

using namespace std;
#include "RBTree.h"

#define N 10000000

void test1()
{
	vector<int> nums(N);
	srand((unsigned int)time(0));

	for (int i = 0; i < N; i++)
	{
		nums[i] = rand() + i;
		//cout << nums[i] << endl;
	}

	RBTree<int> tree;
	for (auto val : nums)
	{
		if (val == 11478)
		{
			int i = 0;
			i++;
		}
		tree.insert(val);
		//cout << val << "->" << tree.isValidRBTree() << endl;
	}
	cout << tree.isValidRBTree() << endl;
}

int main()
{
	test1();

	return 0;
}

---

总结

以上就是我对于红黑树插入实现的总结。感谢支持！！！