【c++】红黑树

用户11029103

发布于 2024-05-24 14:07:26

670

发布于 2024-05-24 14:07:26

文章被收录于专栏：技术学习技术学习

1.红黑树的介绍与性质
2.节点定义
3.红黑树的插入：
- 情况一：父节点与叔节点均为红
- 情况二：父节点为红，叔节点为黑或者不存在
- 情况三：父节点为红，叔节点为黑或者不存在（双旋）
- 代码实现
4.红黑树的验证

1.红黑树的介绍与性质

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

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

这些规则确保了从根到叶子节点的最长路径不会超过最短路径的两倍。最糟糕的情况下，就是红黑树中最长的路径交替着红色和黑色节点，而最短的路径则全由黑色节点构成。因为红色节点不能相邻，所以最长路径上红色节点的数量最多等于黑色节点（忽略根节点）。由于最短路径全由黑色节点构成，因此最长路径的长度最多为最短路径长度的两倍

2.节点定义

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

红黑树要求所有路径从任何节点到叶子节点所包含的黑色节点数量是相同的，这是黑色完美平衡的性质。如果新插入的节点是黑色的，那么会立即破坏这一性质，因为会有一条路径多出一个额外的黑色节点。插入红色节点不会立即违反这个性质，因为它不影响通过它的路径的黑色节点数量

所以在节点的定义中，将节点的默认颜色给成红色的

3.红黑树的插入：

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
       {
	     _root = new Node(kv);
	     _root->_col = BLACK;
	     return true;
       }

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		
	    ----------------

		return true;
	}
	
private:
	Node* _root = nullptr;
};

前面部分相同，从颜色判断开始修改

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

情况一：父节点与叔节点均为红

cur为红，p为红，g为黑，u存在且为红

cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

子树黑节点个数为0，cur为新增

子树黑节点个数为1，cde各有mnpq四种情况，cur两个子节点一定为红色，新插入的节点有四种可能，所以这里将子树抽象为一个整体来处理

情况二：父节点为红，叔节点为黑或者不存在

u的情况有两种：

如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。

如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。，同样是性质4：黑色节点个数相同

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转 p、g变色–p变黑，g变红

de要么为空要么为红，c有四种情况，cur原来为空，子树为两个红，新增有四个位置插入

情况三：父节点为红，叔节点为黑或者不存在（双旋）

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

转换为情况二

代码实现

while (parent && parent->_col == RED)
{
	Node* grandfather = parent->_parent;
	if (parent == grandfather->_left)
	{
		Node* uncle = grandfather->_right;
		if (uncle && uncle->_col == RED)
		{
			parent->_col =uncle->_col= BLACK;
			grandfather->_col = RED;
			cur = grandfather;
			parent = cur->_parent;
		}
		else
		{
		 -------
		}
	}
	---------------
}
_root=BLACK;

这里大条件是父节点存在且为红色，如果为黑色就不用调整颜色

循环内部，根据父节点位置来构建叔节点，如果叔节点存在且为红色，则修改颜色即可

如果不存在或者不为红色，则需要进行旋转，旋转又分为单旋和双旋：

while (parent && parent->_col == RED)
{
	Node* grandfather = parent->_parent;
	if (parent == grandfather->_left)
	{
		Node* uncle = grandfather->_right;
		if (uncle && uncle->_col == RED)
		{
			parent->_col =uncle->_col= BLACK;
			grandfather->_col = RED;
			cur = grandfather;
			parent = cur->_parent;
		}
		else
		{
			if (cur = parent->_left)
			{
				RotateR(grandfather);
				parent->_col = BLACK;
				grandfather->_col = RED;
			}
			else
			{
				RotateL(parent);
				RotateR(grandfather);
				cur->_col = BLACK;
				grandfather->_col = RED;
			}

			break;
		}
	}
}

return true;

如果p在左，cur也在左，进行右单旋，修改颜色，p在左，cur在右，进行先左旋再右旋操作，最后修改节点颜色即可，此时可以直接跳出循环

上面是第一种情况，parent在左边，同理parent在右边也是相类似的实现，代码如下：

	else
	{
		Node* uncle = grandfather->_left;
		// 叔叔存在且为红，-》变色即可
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandfather->_col = RED;

			// 继续往上处理
			cur = grandfather;
			parent = cur->_parent;
		}
		else // 叔叔不存在，或者存在且为黑
		{
			// 情况二：叔叔不存在或者存在且为黑
			// 旋转+变色
			//      g
			//   u     p
			//            c
			if (cur == parent->_right)
			{
				RotateL(grandfather);
				parent->_col = BLACK;
				grandfather->_col = RED;
			}
			else
			{
				//		g
				//   u     p
				//      c
				RotateR(parent);
				RotateL(grandfather);
				cur->_col = BLACK;
				grandfather->_col = RED;
			}

			break;
		}
	}

4.红黑树的验证

检测其是否满足二叉搜索树(中序遍历是否为有序序列)

int main()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16};
	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert({ e,e });
	}
	t1.InOrder();

	return 0;
}

2. 检测其是否满足红黑树的性质

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

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

		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}

			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}

IsBalance函数，用于提供一个公共接口来开始检查红黑树的平衡性。它先检查根节点是否是黑色的，然后计算从根节点到最左侧叶子节点路径中的黑色节点数量作为参考（refNum）。这个数量将用作遍历时所有路径中黑色节点数量的标准。最后，IsBalance调用一个私有递归函数Check来遍历和验证树的每个节点

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函数，它是一个私有的递归函数，用于检查每条从根到叶子节点的路径。对于每一个递归调用：

如果走到了NULL节点（视为达到了叶节点），它会检查当前路径中的黑色节点数量blackNum是否与参考数量refNum相等。如果不等，说明红黑树的黑色完美平衡性质被破坏，返回false。
如果当前节点是红色，并且它的父节点也是红色，这违反了红色节点不能连续的性质，同样返回false。
如果当前节点是黑色，增加当前路径的黑色节点计数（blackNum++）。
之后递归地调用Check函数去检查当前节点的左子树和右子树，传递更新的黑色节点计数。如果左子树或右子树有一个不满足红黑树性质，则整个函数返回false

最终，IsBalance将返回一个布尔值，表示树是否满足红黑树的性质。如果最终返回true，则说明树是平衡的，否则树不平衡

完整代码如下：

#pragma once
#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:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col =uncle->_col= BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红，-》变色即可
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 叔叔不存在，或者存在且为黑
				{
					// 情况二：叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//		g
						//   u     p
						//      c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}
	_root->_col = BLACK;
		return true;
	}	
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}

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

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode;
		}
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	bool IsBalance()
	{
		if (_root->_col == RED)
		{
			return false;
		}

		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}

			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}
private:
	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);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	Node* _root = nullptr;
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-23，如有侵权请联系 cloudcommunity@tencent.com 删除

c++