浮世尘弦头像
【C++】红与黑的边界：红黑树从插入到自检封面图

【C++】红与黑的边界：红黑树从插入到自检

                                                   

                                                   🏆浮世尘弦：

                            ⭐个人专栏：《C语言》、《数据结构与算法》、《C++》

                                      💎：非淡薄无以明志，非宁静无以致远

前言

红黑树看起来规则很多，真正写起来却可以拆成几个清晰步骤：先理解节点和颜色，再找到合适的插入位置，之后通过变色与旋转恢复平衡，最后用查找和性质检查确认实现是否正确。

这篇文章会从基础概念出发，带你用 C++ 完成一棵红黑树。我打算把红黑树沿着“发现问题、补齐结构、验证结果”的顺序，从基本概念出发，依次完成节点设计、查找插入位置、处理颜色冲突以及查找操作。最后，我们还会写一个检查程序，回看生成的红黑树是否真正满足所有性质。希望读完之后，你不仅知道红黑树“应该长什么样”，也能亲手让它在一行行 C++ 代码中稳定地生长起来。

让我们开始今天的学习吧！

目录

前言

一，红黑树的概念

二，红黑树的模拟实现

1，红黑树节点

2，红黑树的插入

1，寻找插入位置并插入

2，调整颜色

3，红黑树的查找 

4，判断是否为红黑树

     结尾

一，红黑树的概念

红黑树是一颗自平衡二叉搜索树，每个节点增加一个变量用来存储该节点的颜色。通过对根到叶子节点路径上的节点的颜色进行约束，确保没有一条路径比其他路径长两倍。

红黑树的核心规则：

1，每个节点不是黑色就是红色的

2，根节点只能是黑色的。

3，如果一个节点的颜色是红色的，那么他的儿子的颜色只能是黑色的。即一条路径中不能出现连续的红色节点。

4，从任意节点位置开始到NULL节点的路径上，黑色节点的个数一定相等。

5，所有的叶子节点（空指针NIL）都是黑色的。

红黑树的效率：

假设N是红黑树当中的节点个数，h为最短路径的长度，2^h-1<=  N < 2^(2h)-1，故h大约为logN，红黑树增删查最坏走最长路径2*logN，时间复杂度依旧为O(logN)。

二，红黑树的模拟实现

1，红黑树节点

红黑树节点由五部分构成：1，关键字key，也可以为pair  2，指向左子树的指针：left

3,指向右子树的指针：right 4，指向父亲节点的指针 5，节点的颜色color，可以设计为枚举值

enum color
{
	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;
	color col;
	RBTreeNode(const pair<K, V>& p)
		:kv(p)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
	{}
};

2，红黑树的插入

插入步骤：

1，寻找插入位置并插入

寻找位置和插入的规则和平衡二叉树插入值的过程一样。

从根节点位置开始，比较节点值的大小。走向左子树或者右子树。知道找到插入位置。

注意:要提前设计一个父亲节点，提前记录位置，方便插入。

代码展示：

//红黑树
template <class K,class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	//插入
	bool Insert(const pair<K, V>& p1)
	{
		//根节点为空
		if (root == nullptr)
		{
			root = new Node(p1);
			root->col = BLACK;
			return true;
		}
		//根节点不为空，找到要插入的位置
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			if (p1.first > cur->kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (p1.first < cur->kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else  //不能存在相同节点
			{
				return false;
			}
		}
		//进行插入
		cur = new Node(p1);
		cur->col = RED;
		if (p1.first > parent->kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		//链接父亲
		cur->_parent = parent;

2，调整颜色

插入的节点主要看是否违反上面的规则，如果违反了怎样处理更合适。和上面规则息息相关的就是节点的颜色。

1，如果是空树，新增节点一定是黑色；但如果非空树新增节点是黑色的，就会违反上面的规则4，此时需要处理其他所有路径，很难维护。所以插入的节点的颜色只能是红色的。

2，新增红色节点的父亲节点也是红色的话，就需要进行调整。

下图：g表示爷爷，p表示父亲，u表示叔叔，c表示新增节点

由上图可知：新增节点的颜色一定是红色，若p的颜色为红色，则g的颜色一定是黑色。

只有u的颜色是不确定的。下面我们调整的关键就是根据u的颜色分情况进行处理。

第一种情况：只变色

如果u存在并且为红色，就把p，u变成黑色，g变成红色。如果g不是根节点就继续向上进行处理，如果g是根节点就要变成黑色 。

无论c在p的左边，还是右边；u在g的左边，还是右边。都只变色处理。

下面使用抽象图，抽象出变色的情况：

a/b表示每条路径上都有m-1个黑色节点且根为红色的子树，d/e/f表示每条路径上都有m个黑色节点且根为黑色的子树。(m>=0)

当m=1时：

第二种情况：单旋+变色

如果u不存在或者u为黑色，如果u不存在，那么c一定是新增节点，如果u为黑色节点，那么c一定是由黑色节点变化过来的。此时单纯的变色是无法解决问题的。需要旋转。

先看一组案例：

叔叔不存在，cur一定是新增的节点，如果不是新增的那cur就是变化过来的原先是黑色，导致路径上的黑色节点数量不同。

如果叔叔存在且为黑色，那么c一定是从黑色节点变化成红色节点，否则之前各个路径上的黑色节点就不同。

将单旋和变色的情况变为抽象图：

第三种情况：双旋+变色

c插入的位置和单旋位置不同，就会出现双旋

案例展示：

变成抽象图：

双旋结论： 8cur作为根节点，父亲作为左子树爷爷作为右子树，他原来的子树分别链接到左边的父亲和右边的爷爷中

调整颜色代码展示：

		//父亲存在且父亲是红色，并且出现连续的红色节点需要向上进行处理
		while (parent && parent->col == RED)
		{
			Node* gparent = parent->_parent;
			//     g
			//  p    u
			//父亲在左边
			if (gparent->_left == parent)
			{
				Node* uncle = gparent->_right;
				//叔叔存在并且叔叔的颜色是红色-变色
				if (uncle && uncle->col == RED)
				{
					gparent->col = RED;;
					parent->col = uncle->col = BLACK;
					//继续向上进行处理
					cur = gparent;
					parent = cur->_parent;
				}
				else //叔叔不存在或者叔叔的颜色是黑色的--旋转+变色
				{
					//    g
					//  p   u
				    //c
					if (cur == parent->_left)//右单旋
					{
						RotateR(gparent);
						parent->col = BLACK;
						gparent->col = RED;
					}
					//   g
					// p   u
					//  c
					else//左右双旋
					{
						RotateL(parent);
						RotateR(gparent);
						cur->col = BLACK;
						gparent->col = RED;
					}
					//旋转+变色处理后，子树的高度一定不变且根节点是黑色
					//一定不会出现连续两个红色节点的情况，可以提前跳出
					break;
				}
			}
			//    g
			//  u   p
			else //父亲在右侧
			{
				Node* uncle = gparent->_left;
				//叔叔存在并且叔叔的颜色是红色-变色
				if (uncle && uncle->col == RED)
				{
					gparent->col = RED;
					parent->col = uncle->col = BLACK;
					//继续向上进行处理
					cur = gparent;
					parent = cur->_parent;
				}
				else //叔叔不存在或者叔叔的颜色是黑色的--旋转+变色
				{
					//    g
					// u     p
					//         c
					if (cur == parent->_right)//左单旋
					{
						RotateL(gparent);
						parent->col = BLACK;
						gparent->col = RED;
					}
					//     g
					//  u     p
					//      c
					else//右左双旋
					{
						RotateR(parent);
						RotateL(gparent);
						cur->col = BLACK;
						gparent->col = RED;
					}
					break;
				}
			}
		}
		root->col = BLACK;
		return true;
	}

3，红黑树的查找 

直接从根节点，按照二叉搜索树的逻辑进行查找，时间复杂度为log(N)

红黑树查找代码：

	//查找
	Node* Find(const K& k)
	{
		Node* cur = root;
		while (cur)
		{
			if (k > cur->kv.first)
			{
				cur = cur->_right;
			}
			else if (k < cur->kv.first)
			{
				cur = cur->_left;
			}
			else //找到了
			{
				return cur;
			}
		}
		return nullptr;
	}

4，判断是否为红黑树

直接判断最长路径是否不超过最短路径的2倍，比较麻烦，而且不能保证颜色正确。

我们可以从上面的五条规则入手进行判断：

对于规则1：直接枚举颜色类型进行判断

对于规则2：直接检查根节点的颜色类型

对于规则3：对于红色节点，直接查找红色节点的父亲节点是否为黑色节点。

对于规则4：先任意走一条路径(例如：最左路径)，记录黑色节点的个数作为参考值。使用前序遍历，用一个参数记录根节点到当前节点路径上黑色节点的个数，直到走到空为止。和参考值进行比较。

代码展示：

	//判断是否为红黑树
	bool IsRBTree()
	{
		//根为空
		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, int refnum)
		{
			//如果走到空节点
			if (root == nullptr)
			{
				if (blacknum != refnum)
				{
					cout << "路径黑色节点的个数不同" << endl;
					return false;
				}
				return true;
			}
			//检查不能出现连续的红色节点
			if (root->col == RED && root->_parent && root->_parent->col == RED)
			{
				cout << "出现了连续的红色节点" << endl;
				return false;
			}
			if (root->col == BLACK)
				blacknum++;
			return Check(root->_left, blacknum, refnum) &&
				Check(root->_right, blacknum, refnum);
		}

运行测试1：

效率测试2：

void test2()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();

	size_t begin22 = clock();
	RBTree<int, int> rbt;
	for (auto e : v)
	{
		rbt.Insert(make_pair(e, e));
	}
	size_t end22 = clock();

	cout << "AVL Insert:" << end2 - begin2 << endl;
	cout << "RB Insert:" << end22 - begin22 << endl;

	cout <<"AVL IsBalance:"<< t.IsAVLTree() << endl;
	cout << "RB IsBalance:" << rbt.IsRBTree() << endl;


	cout << "AVL Height:" << t.Height() << endl;
	cout << "AVL Size:" << t.Size() << endl;

	cout << "RB Height:" << rbt.Height() << endl;
	cout << "RB Size:" << rbt.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}
	// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "AVL Find:" << end1 - begin1 << endl;

	size_t begin11 = clock();
	// 确定在的值
	for (auto e : v)
	{
		rbt.Find(e);
	}
	// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end11 = clock();
	cout << "RB Find:" << end11 - begin11 << endl;
}

测试结果：

     结尾

本篇文章中所涉及到的代码：

gitee链接：红黑树的模拟实现

以上就是本文的全部内容了，如果对你有所帮助的话，请大佬不妨给博主来个“一键三连”，这对我是大大的支持，也能让博主产出更优质的内容。

往期回顾：

【C++】《手撕二叉搜索树：删除才是真正的分水岭》
【C++】一次插入，四场旋转：C++ AVL 树的自平衡之路

总结：本文系统讲解红黑树的原理与模拟实现，涵盖节点结构、插入操作及三种调整情形（变色、单旋+变色、双旋+变色），确保满足五条核心规则。通过自上而下调整，保障增删查时间复杂度稳定在O(logN)。文章还实现查找、判断是否为红黑树等功能，并通过性能测试验证其高效性，适合深入理解自平衡二叉搜索树的实现逻辑。

                                      ⚡把上面的内容吃透就休息一下吧⚡

                                        

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/w37773698/article/details/169067841

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--