【C++深度探索】红黑树的底层实现机制

1.红黑树结构

红黑树的性质：

• 每个结点不是红色就是黑色
• 根节点是黑色的
• 如果一个节点是红色的，则它的两个孩子结点是黑色的
• 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

所以红黑树的节点必须包含一个值类存储该节点的颜色，我们可以利用枚举来实现：

代码语言：javascript复制

//枚举颜色
enum Colour
{
	RED,
	BLACK
};

//节点类
template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;	//存放数据
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;	//保存颜色

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_col(RED)
	{}
};

//红黑树类
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	bool Insert(const pair<K, V>& data);
		
	// 检测红黑树是否为有效的红黑树
	bool IsValidRBTRee();

	//中序遍历
	void InOrder()
	{
		_InOrder(_pHead);
	}

private:
	void _InOrder(Node* root);
	
	bool Check(Node* root, int blackNum, const int refNum);
	
	// 左单旋
	void RotateL(Node* parent);
	// 右单旋
	void RotateR(Node* parent);
	
private:
	Node* _pHead = nullptr;
};

2.红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏，如果破坏进行相应的修改操作

在插入新节点时，我们先确定一下新节点的颜色，如果是黑色，那么在插入后该条子路径上就会多一个黑色节点，根据红黑树的性质需要在其他路径上都增加一个新节点才可以，比较麻烦，所以我们将新节点的颜色设为红色，这样如果其父亲是黑色就刚刚好插入成功，如果父亲是红色我们就再来修改；所以我们将新节点的颜色设置为红色：

代码语言：javascript复制

//节点类
template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;	//存放数据
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;	//保存颜色

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_col(RED)		//直接在构造时设置即可
	{}
};

先正常插入节点：

代码语言：javascript复制

//1.先找到插入位置
//如果是空树
if (_pHead == nullptr)
{
	Node* newnode = new Node(data);
	newnode->_col = BLACK;
	_pHead = newnode;
	return true;
}
//如果不是空树
Node* cur = _pHead;
Node* parent = nullptr;
while (cur)
{
	if (cur->_kv.first > data.first)
	{
		parent = cur;
		cur = cur->_left;
	}
	else if (cur->_kv.first < data.first)
	{
		parent = cur;
		cur = cur->_right;
	}
	else
		return false;//没找到返回false
}

//2.找到，插入节点
Node* newnode = new Node(data);
//判断插入父节点左侧还是右侧
if (parent->_kv.first > data.first)
	parent->_left = newnode;
else
	parent->_right = newnode;

//更新newnode父节点
newnode->_parent = parent;

1. 如果父节点是黑色，那么直接插入节点即可：

代码语言：javascript复制

if (parent->_col == BLACK)
{
	//父节点是黑色,插入成功
	return true;
}

1. 如果父节点是红色，那么我们需要调整：

因为不可能有两个红色连在一起，所以我们需要进行调整；而且父节点是红色的话那么父节点肯定不是根节点且其父节点的颜色也只能是黑色，如下图所示：

这时，我们就需要根据叔叔节点来进行调整节点：

• 如果uncle节点是红色：

我们就可以将unlcle和parent节点都变为黑色，grandparent节点变为红色：

这样这两条路径的黑色节点依然是一个，没有变，但是grandparent节点变为红色，如果它的父节点是黑色那么调整成功，但是如果其父节点是红色，红黑树的性质就不满足，所以我们需要继续向上调整。

• 如果uncle节点是黑色：

这时我们发现uncle节点的路径上多了一个黑色节点，说明cur节点不可能是新增节点，这种情况是由上面uncle节点是红色情况调整之后还需要继续向上调整得来的(cur是上面情况的grandparent，grandparent的父节点也是红色)，单纯的变色已经不能维持红黑树的性质，我们需要进行旋转：

✨情况一：如果parent为grandparent的左孩子，cur为parent的左孩子，则进行右单旋转：

  再将grandparent的颜色改为红色，parent改为黑色。

✨情况二：如果parent为grandparent的右孩子，cur为parent的右孩子，则进行左单旋转：

  再将grandparent的颜色改为红色，parent改为黑色。

✨情况三：如果parent为grandparent的左孩子，cur为parent的右孩子，则先进行左单旋转换成情况一，再进行右单旋：

  再像情况一进行右单旋：

  再将grandparent的颜色改为红色，cur改为黑色。

✨情况四：如果parent为grandparent的右孩子，cur为parent的左孩子，则先进行右单旋转换成情况二，再进行左单旋：

  再像情况二进行左单旋：

  再将grandparent的颜色改为红色，cur改为黑色。

✨进行旋转后，红黑树就满足了性质，插入成功。

• 如果uncle不存在：

这种情况和uncle存在且为黑是一样的，所以可以并入上面一起考虑。

完整代码如下：

代码语言：javascript复制

bool Insert(const pair<K, V>& data)
{
	//1.先找到插入位置
	//如果是空树
	if (_pHead == nullptr)
	{
		Node* newnode = new Node(data);
		newnode->_col = BLACK;
		_pHead = newnode;
		return true;
	}
	//如果不是空树
	Node* cur = _pHead;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first > data.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < data.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
			return false;//没找到返回false
	}
	
	//2.找到，插入节点
	Node* newnode = new Node(data);
	//判断插入父节点左侧还是右侧
	if (parent->_kv.first > data.first)
		parent->_left = newnode;
	else
		parent->_right = newnode;

	//更新newnode父节点和颜色
	newnode->_parent = parent;
	if (parent->_col == BLACK)
	{
		//父节点是黑色,插入成功
		return true;
	}
	if (parent->_col == RED)
	{
		//父节点是红色
		cur = newnode;
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;//parent是红色，肯定不是根节点，所以grandparent不是空节点，而且是黑色
			
			//找叔叔节点
			Node* uncle = grandparent->_left;
			if (parent == grandparent->_left)
				uncle = grandparent->_right;
			
			if (uncle&&uncle->_col == RED)
			{
				//如果uncle是红色
				//将unlcle和parent节点都变为黑色，grandparent节点变为红色
				parent->_col = uncle->_col = BLACK;//即可保证所有路径上黑色一样多
				grandparent->_col = RED;
			
				//继续往上更新
				cur = grandparent;
				parent = cur->_parent;
			}
			else if (uncle==nullptr||uncle->_col == BLACK)
			{
				//如果uncle不存在或者存在且为黑色
				if (grandparent->_left == parent && parent->_left == cur)
				{
					//右单旋,再将grandparent改为红色，parent改为黑色
					RotateR(grandparent);
					grandparent->_col = RED;
					parent->_col = BLACK;
				}
				else if (grandparent->_right == parent && parent->_right == cur)
				{
					//左单旋,再将grandparent改为红色，parent改为黑色
					RotateL(grandparent);
					grandparent->_col = RED;
					parent->_col = BLACK;
				}
				else if (grandparent->_right == parent && parent->_left == cur)
				{
					RotateR(parent);//先右单旋
					RotateL(grandparent);//再左单旋
					//再将grandparent的颜色改为红色，cur改为黑色
					grandparent->_col = RED;
					cur->_col = BLACK;
				}
				else if (grandparent->_left == parent && parent->_right == cur)
				{
					RotateL(parent);//先左单旋
					RotateR(grandparent);//后右单旋
					//再将grandparent的颜色改为红色，parent改为黑色
					grandparent->_col = RED;
					cur->_col = BLACK;
				}
				else
					assert(false);
				
				//插入成功，跳出循环
				break;
			}
		}

	}
	_pHead->_col = BLACK;//最后不管怎样，根节点都是黑色
	return true;
}

因为涉及到多种情况，所以根节点的颜色可能会顾及不上，所以最后我们可以加一句_pHead->_col = BLACK;，这样不管怎么样，根节点都是黑色了。

✨左、右单旋函数与AVL树的左、右单旋一样：

代码语言：javascript复制

// 左单旋
void RotateL(Node* parent)
{

	Node* cur = parent->_right;

	//将cur的左边给parent的右边，cur的左边再指向parent
	parent->_right = cur->_left;
	cur->_left = parent;

	//链接cur与parent的父节点
	if (parent->_parent == nullptr)
	{
		//如果parent是根节点
		cur->_parent = nullptr;
		_pHead = cur;
	}
	else if (parent->_parent->_left == parent)
		parent->_parent->_left = cur;
	else
		parent->_parent->_right = cur;


	//更新父节点
	cur->_parent = parent->_parent;
	parent->_parent = cur;
	if (parent->_right)//判断parent的右边是否存在
		parent->_right->_parent = parent;

	
}
// 右单旋
void RotateR(Node* parent)
{
	Node* cur = parent->_left;

	//将cur的右边给parent的左边，cur的右边再指向parent
	parent->_left = cur->_right;
	cur->_right = parent;

	//链接cur与parent的父节点
	if (parent->_parent == nullptr)
	{
		//如果parent是根节点
		cur->_parent = nullptr;
		_pHead = cur;
	}
	else if (parent->_parent->_left == parent)
		parent->_parent->_left = cur;
	else
		parent->_parent->_right = cur;


	//更新父节点
	cur->_parent = parent->_parent;
	parent->_parent = cur;
	if (parent->_left)
		parent->_left->_parent = parent;
}

红黑树的左、右单旋与AVL树的区别在于不需要跟新平衡因子。

测试函数：

代码语言：javascript复制

void RBTreeTest()
{
	RBTree<int, int> t;
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
	}
}

3.红黑树的验证

 红黑树的验证和AVL树一样，分为两个步骤：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质

对于第二点：

代码语言：javascript复制

// 检测红黑树是否为有效的红黑树
bool IsValidRBTRee()
{
	if (_pHead == nullptr)
		return true;

	if (_pHead->_col == RED)
	{
		return false;
	}

	// 先求一条路径上黑色节点数量作为参考值
	int refNum = 0;
	Node* cur = _pHead;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			  refNum;
		}

		cur = cur->_left;
	}

	return Check(_pHead, 0, refNum);
}

首先如果一棵树是空树满足红黑树的性质，返回true；其次如果根节点为红色则不满足红黑树的性质，返回false；然后再根据每条路径上是否有相同的黑色节点已及是否存在连续的红色节点来进一步判断即Check()函数，但是我们需要先确定一条路上应该有多少个黑色节点作为参考。

Check()函数如下：

代码语言：javascript复制

bool Check(Node* root, int blackNum, const int refNum)
{
	if (root == nullptr)
	{
		//cout << blackNum << endl;
		if (refNum != blackNum)
		{
			cout << "存在黑色节点的数量不相等的路径" << endl;
			return false;
		}
		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << root->_kv.first << "存在连续的红色节点" << endl;
		return false;
	}

	if (root->_col == BLACK)
	{
		blackNum  ;
	}

	return Check(root->_left, blackNum, refNum)
		&& Check(root->_right, blackNum, refNum);
}

因为Check()函数使用的是递归来计算每条路径上黑色节点的数量，所以当root为空时我们就可以将计算该条路径上的黑色节点数量blackNum与参考值refNum进行比较，如果相等返回true，不相等就返回fals；此外如果在计算黑色节点过程中存在连续的红色节点也直接返回false即可。

测试函数：

代码语言：javascript复制

void RBTreeTest()
{
	RBTree<int, int> t;
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
	}
	
	cout << t.IsValidRBTRee() << endl;
}

4.中序遍历

 与二叉搜索树一样，可以使用递归进行中序遍历，并且遍历结果是有序的，代码如下：

代码语言：javascript复制

//中序遍历
void InOrder()
{
	_InOrder(_pHead);
}

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

结果如下：

5.结语

  因为红黑树也是二叉搜索树，其他的类似查找节点，析构函数和构造函数都与二叉搜索树类似，对于删除节点，可按照二叉搜索树的方式将节点删除，然后再进行调整，大家有兴趣可以自己查找了解一下

parent 遍历 函数 搜索 c++

0 人点赞