★ C++进阶篇 ★ 红黑树实现-贰  红黑树的实现

时间：2024-10-23 16:37:37

2.1 红黑树的结构

//枚举值表⽰颜⾊
enum Colour
{
	RED,
	BLACK
};

// 这⾥我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
	// 这里更新控制平衡也要加入parent指针
	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)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	//...
private:
	Node* _root = nullptr;
};

2.2 红黑树的插入

2.2.1 红黑树树插入⼀个值的大概过程

  • 插⼊⼀个值按二叉搜索树规则进行插入，插⼊后我们只需要观察是否符合红黑树的4条规则~
  • 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为⾮空树插入，新增黑色结点就破坏了规则4，规则4是很难维护的 ~
  • 非空树插入，新增结点必须红色结点，如果父亲结点是黑色的，插入结束 ~
  • 非空树插入，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。进⼀步分析，c是红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。

新增结点标识为c，c的父亲标识为p，p的父亲标识为g，p的兄弟标识为u。

2.2.2 情况1：变色

c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。在把g当做新的c，继续往上更新。 分析：因为p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加⼀个黑色结点，g再变红，相当于保持g所在⼦树的黑色结点的数量不变，同时解决了c和p连续红色结点的问题，需要继续往上更新 是因为，g是红色，如果g的父亲还是红色，那么就还需要继续处理；如果g的父亲是黑色，则处理结束了；如果g就是整棵树的根，再把g变回黑色。

情况1只变色，不旋转。所以伍论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。

// 父亲是红色，出现连续的红色节点，需要处理
while (parent->_col == RED)
{
	Node* grandfather = parent->_parent;

	if (parent == grandfather->_left)
	{
		//   g
		// p   u
		Node* uncle = grandfather->_right;
		// 叔叔存在且为红，变色即可
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandfather->_col = RED;
			// 继续往上处理
			cur = grandfather;
			parent = cur->_parent;
		}
		// 叔叔不存在，或者存在且为黑
		else
		{
            // 情况二：叔叔不存在或者存在且为黑
			// 旋转+变色
			//...
		}
	}
	else
	{
		//   g
		// u   p
		Node* uncle = grandfather->_left;
		// 叔叔存在且为红，变色即可
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandfather->_col = RED;

			// 继续往上处理
			cur = grandfather;
			parent = cur->_parent;
		}
		else // 叔叔不存在，或者存在且为黑
		{
			// 情况二：叔叔不存在或者存在且为黑
			// 旋转+变色
            //...
			break;
		}
	}
}

2.2.3 情况2：单旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c⼀定是新增结点，u存在且为黑，则c⼀定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。

分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这⾥单纯的变⾊无法解决问题，需要旋转+变色。

如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。

如果p是g的右，c是p的右，那么以g为旋转点进⾏左单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。

 

2.2.4 情况3：双旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c⼀定是新增结点，u存在且为黑，则c⼀定不是新增，c之前是黑色的，是在c的⼦树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。

分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这⾥单纯的变色无法解决问题，需要旋转+变色。

如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变黑，g变红即可。c变成课这颗树新的根，这样⼦树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。

如果p是g的右，c是p的左，那么先以p为旋转点进行右单旋，再以g为旋转点行左单旋，再把c变黑，g变红即可。c变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的⽗亲是黑色还是红色或者空都不违反规则。

2.3 红黑树的插入代码实现

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 (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	// 插入红色新结点
	cur->_col = RED;
	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)
		{
			//   g
			// p   u
			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)
				{
					//     g
					//   p    u
					// c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//      g
					//   p    u
					//     c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		else
		{
			//   g
			// u   p
			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
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	return true;
}

2.4 红黑树的查找

按二叉搜索树逻辑实现即可，搜索效率为 O(logN)

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)
		{
			cur = cur->_right;
		}
		else if (cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

2.5 红黑树的验证

只要检查红黑树的四点规则，满足这4点规则，⼀定能保证最⻓路径不超过最短路径的2倍。

  • 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
  • 规则2直接检查根即可
  • 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不⼀定存在，反过来检查父亲的颜色就方便多了。
  • 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum（黑色结点数量)，前序遍历遇到黑色结点就++blackNum，⾛到空就计算出了⼀条路径的黑色结点数量。再任意⼀条路径黑色结点数量作为参考值，依次比较即可。

bool IsBalance()
{
	if (_root == nullptr)
		return true;

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

~ 完 ~

相关文章