红黑树简单模拟实现

发布于：2025-05-25 ⋅ 阅读:(18) ⋅ 点赞:(0)


我们前面实现了 二叉搜索树和 AVL树。
其中AVL树是二叉搜索树的改进，但是有些人觉得二叉树搜索的插入调整太频繁了，或者说平衡条件过于苛刻。
于是人们放松了左右子树高度差的限制，只需要确保没有一条路径会比其他路劲长出两倍，这就是所谓的红黑树。

定义

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

红黑树满足的性质：

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

满足这上面五个条件就确保了最长路径不会超过最短路径两倍。接下来我解释一下这是为什么。

首先看到34两点。满足了这两点之后，我们的理论最短路径就是全黑结点。
那最长路径呢？
因为要满足第四条，所以只能在全黑结点路径上插入红色结点来增长路径，又因为红色结点不能连续，因此最多插入等量的红色结点。这就确保了最长路径不会超过最短路径的两倍。

那为什么根节点要是黑色结点呢？
假如根节点是红色结点，那么他只能插入黑色结点，这就导致了左右子树的黑色结点数量不同。因此根节点只能是黑色的。

成员变量

enum Color
{
	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;
	Color _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:

private:
	Node* _root = nullptr;
};

旋转

在前文AVL树中我们实现了左单旋和右单旋，那么这两种旋转能不能合并成一个函数呢？
注意到左单旋：
在这里插入图片描述
右单旋：
在这里插入图片描述
左单旋是将parent右子subR的左子树subRL接到parent的右边。
右单旋是将parent左子subL的右子树subLR接到parent的左边。

如此对称的行为理应可以合并：

void Rotate(Node* child)
{
	Node* parent = child->_parent;
	Node** childson[] = {  &(child->_right),&(child->_left) };
	Node** parentson[] = { &(parent->_left),&(parent->_right) };
	bool IsRight = (child == parent->_right);

	*(parentson[IsRight]) = *(childson[IsRight]);
	if (*(childson[IsRight]))
		(*(childson[IsRight]))->_parent = parent;

	*(childson[IsRight]) = parent;
	child->_parent = parent->_parent;
	parent->_parent = child;

	if (parent == _root)
	{
		_root = child;
		child->_parent = nullptr;
	}
	else 
	{
		//Node* grandparent = parent->_parent; 千错万错
		Node* grandparent = child->_parent;
		if (parent == grandparent->_left) grandparent->_left = child;
		else grandparent->_right = child;
	}

}

这时候如果要左单旋，就传入旋转点的右孩子，如果要右单旋就传入旋转点的左孩子。

insert

对于插入一个结点，那么是默认他为红色还是黑色呢？
如果默认是黑色就会违反所有路径黑色结点数相同这一个规定，如果默认是红色就有可能违反红色结点不连续这一规定。
显然插入红色结点的冲突比较好处理，因此我们默认插入的结点为红色结点。那么就分三种情况：

  1. 插入的结点是根节点，那只需要让根节点变黑即可
  2. 插入的结点的父结点是黑色结点，那么不违反规则，不做处理
  3. 插入的结点的父结点是红色结点，需要处理。

对于第三种情况，又要分两种情况进行讨论：

  1. 叔叔结点存在且为红色：

在这里插入图片描述

如上，10结点为插入结点。
首先是很容易想到的，为了维持到10结点这一路径的黑色结点个数不变，我们需要将20结点变黑同时将30结点变红，如果仅仅是将20结点变黑，那么到10结点这一路径的黑色结点数就会+1，违反规定4.
那么在30结点变红之后，到40结点这一路径的黑色节点数是不是就少了一个？所以我们要将40结点变黑。如下处理：
在这里插入图片描述
那么30结点有没有可能和他的父结点冲突呢？答案是有可能的，所以我们还需要将30结点看作插入结点继续循环处理。

  1. 那么再看到另一种情况，也就是叔叔结点不存在或者为黑色

实际上这种情况又详细分为四种，我们先看第一种插入结点为左子结点，叔叔结点为右子结点或者不存在：
在这里插入图片描述
由图可知，先将父亲变黑，爷爷变红然后进行右单旋调整

第二种插入结点为右子结点，叔叔结点为左子结点或者不存在，根据对称性可知，先将父亲变黑，爷爷变红然后进行左单旋调整

第三种插入结点为右子结点，叔叔结点为右子结点或者不存在
在这里插入图片描述
可以看到对父亲结点进行左单旋就转换成了第一种情况，这时按第一种情况除了

第四种插入结点为左子结点，叔叔结点为左子结点或者不存在

以234树的角度来待插入操作

我们可以将红黑树看作一棵二三四树，其中黑色结点为2结点，黑色结点加红色结点为3结点，黑色结点和两个红色结点为4结点。
例如：
在这里插入图片描述
这时我们插入一个16：
在这里插入图片描述
这就对应了父结点时黑色结点，不用处理

如果插入一个3：
在这里插入图片描述
这时候对应叔叔结点存在且为红。
那么5结点上溢，叔父变黑，爷爷变红，继续向上处理。

如果插入一个17：
在这里插入图片描述
本质上就是父亲做了爷爷，又因为父亲是右子结点，实际上就是进行左单旋。对应插入结点为右子结点，叔叔结点为左子结点或者不存在。

我们再看到如果插入25.5：
在这里插入图片描述
实际上是儿子做了爷爷，首先儿子要当爹，又因为儿子是左子结点，因此右单旋。然后儿子就是爷爷的右子结点了，再左单旋就成了爷爷。最后变色处理。
对应插入结点为左子结点，叔叔结点为左子结点或者不存在。

其余情况也是类似讨论，这里不多做赘述。

具体代码

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)
		{
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续处理
				cur = grandfather;
				//未必有parent
				parent = cur->_parent;
			}
			else//叔叔不存在或者为黑
			{

				if (cur == parent->_left)
				{
					//RotateR(grandfather);
					Rotate(grandfather->_left);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{

					//RotateL(parent);
					//RotateR(grandfather);
					Rotate(parent->_right);
					Rotate(grandfather->_left);
					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
				parent = cur->_parent;
			}
			else//叔叔不存在或为黑
			{
				if (cur == parent->_right)
				{
					//RotateL(grandfather);
					Rotate(grandfather->_right);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}

	}

	//处理边界情况
	_root->_col = BLACK;

	return true;
}

完整代码

完整代码包括InOrder和IsBalance

enum Color
{
	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;
	Color _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 (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)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续处理
					cur = grandfather;
					//未必有parent
					parent = cur->_parent;
				}
				else//叔叔不存在或者为黑
				{

					if (cur == parent->_left)
					{
						//RotateR(grandfather);
						Rotate(grandfather->_left);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{

						//RotateL(parent);
						//RotateR(grandfather);
						Rotate(parent->_right);
						Rotate(grandfather->_left);
						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
					parent = cur->_parent;
				}
				else//叔叔不存在或为黑
				{
					if (cur == parent->_right)
					{
						//RotateL(grandfather);
						Rotate(grandfather->_right);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}

		}

		//处理边界情况
		_root->_col = BLACK;

		return true;
	}

	void Rotate(Node* child)
	{
		Node* parent = child->_parent;
		Node** childson[] = {  &(child->_right),&(child->_left) };
		Node** parentson[] = { &(parent->_left),&(parent->_right) };
		bool IsRight = (child == parent->_right);

		*(parentson[IsRight]) = *(childson[IsRight]);
		if (*(childson[IsRight]))
			(*(childson[IsRight]))->_parent = parent;

		*(childson[IsRight]) = parent;
		child->_parent = parent->_parent;
		parent->_parent = child;

		if (parent == _root)
		{
			_root = child;
			child->_parent = nullptr;
		}
		else 
		{
			//Node* grandparent = parent->_parent; 千错万错
			Node* grandparent = child->_parent;
			if (parent == grandparent->_left) grandparent->_left = child;
			else grandparent->_right = child;
		}

	}

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

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

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	bool Check(Node* root,int blackNum,const int refNum)
	{
		if (root == nullptr)
		{
			if (blackNum != refNum)
			{
				cout << "黑错" << endl;
				return false;
			}
			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "红红" << 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;
	//size_t _size;
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布