【数据结构】红黑树（C++ 模拟）

Er07

1473人浏览 · 2025-09-02 15:54:41

Er07 · 2025-09-02 15:54:41 发布

文章目录

前言
1. 数据结构
- 1.1 红黑树节点的设计
2. 红黑树插入过程（C++）
- 2.1 P为红色的场景
- 2.2 红黑树插入的实现
3. 红黑树性能分析和总结
红黑树插入模拟及测试源码（C++）

前言

除了AVL树之外，还有一个被广泛应用的平衡二叉搜索树：红黑树。

本章节，小编会和大家介绍红黑树的数据结构和性质、分析红黑树的插入过程并完成代码的实现……

1. 数据结构

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

它有如下的性质：

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

如图的一颗红黑树：
其中NIL：在代码层面可以理解为nullptr。
关于路径：在红黑树中的路径是指从根节点到叶子节点的路径。所以上图中一共有11条路径，叶子节点的个数。

在同一棵红黑树中：
- 关于最短路径：红黑树的最短路径是全黑的路径。
- 关于最长路径：红黑树的最长路径是一黑一红的路径。
所以我们可以从理论上说明：红黑树中最长路径不会超过最短路径的两倍（性质4决定了，每条路径上的黑色节点是固定的。配合性质3，最长的路径就是一黑一红）。
关于性质4：我们还可以证明“在红黑树中的任何一个子树局部上都满足性质4”

1.1 红黑树节点的设计

namespace LL
{
	enum Color
	{
		Red = 0,
		Black
	};

	template<class K, class V>
	struct RBTreeNode
	{
		typedef RBTreeNode<K, V> TreeNode;
		TreeNode* _parent;
		TreeNode* _left;
		TreeNode* _right;
		std::pair<K, V> _kv;
		Color _col;

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

关于红黑树的节点：
- _col：描述红黑树的节点的颜色。
- _parent：指向该节点的父节点。
- _kv：保存的依旧是key/value的键值对。

2. 红黑树插入过程（C++）

红黑树和AVL树一样，需要对树中的节点进行旋转。关于旋转的过程，都是一致的。关于旋转小编在数据结构之AVL树中已经做出了详细的介绍，大家有兴趣可以去看，这里小编就不再带大家详细实现了。最后会在源码处会给出的……

根据性质4：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。我们所以每次插入的节点必须是红色的。这样才能保证我们不破坏性质4。

简单描述一下插入过程：

为了方便描述：我们将插入节点称为C，父节点成为P，父亲的兄弟节点称为U，祖父节点成为G，曾祖父节点成为GG。
注：以下的所有探讨都是P在G的左子树上。右子树同理！！！
1. 寻找插入节点。
2. 寻找成功，创建节点插入到P节点左/右。建立连接关系。
3. 判断P节点的颜色
  - 若P是黑色，则插入结束。
  - 若P是红色，则进一步判断：如果U节点是红色，则变色迭代，直到更新到根节点/遇到P是黑色(迭代之后的P)/遇到U（迭代之后的）是黑色完成旋转变色；如果U节点是黑色，则旋转+变色，完成后插入结束。
注：迭代可以理解为一种另类的插入！
大致过程如下图：
下图是P节点为红色的插入情况。包含了变色迭代、旋转变色。

2.1 P为红色的场景

接下来细致探讨P为红色的情况：

情形一：U是红色。下面给出抽象模型：
- 当我们插入之后发现U是红色：
1. 更改P和U的颜色，将红色改变为黑色；改变G的颜色，将黑色(一定是黑色，不然结构本省不插入就不满足了)改为红色。
2. 迭代：将C指针改为G，将P指针改为GG……继续判断。
- P、U、G变色之后的三种情况A、B、C：
情形二：U是黑色(NIF也是黑色)。下面给出抽象模型：

这里给出两点说明：
1. 如果U不存在。则C一定是新插入的节点。因为如果C不是新插入的节点，那么C和P一定有一个节点为黑色，就不满足性质3和性质4。
2. 如果U节点存在，且是黑色的。那么C节点原来的颜色一定是黑色的，现在的C是红色是因为在原来的插入过程迭代的过程中发生了变色由黑色改为了红色。
- A、单旋转：
  
  根据上图的所示，在该情况下，我们将以G为中心采用右单旋且变色。使用右单旋+变色后，不仅可以使得这颗子树完全满足红黑树的性质4且该子树路径上的黑色节点个数和之前相比没有发生变化。这样的原因，使得旋转完成之后，我们的插入就结束了……
  - 变色策略：P黑；C、G红。
- B、双旋转：
  
  双旋转的第一次旋转：是为了将复杂模型转化为简单的单旋转模型。完成第一次旋转之后，就变成了情况A。这里就不再过多描述了……
  - 变色策略：C变黑； P、G红

2.2 红黑树插入的实现

至此P作为G的左边节点的实现已经全部结束。但是P还会作为G的右边节点。这是一个对称的过程，类似的……

bool insert(const std::pair<K, V>& kv)
{
	if (!_root)
	{
		_root = new TreeNode(kv);
		_root->_col = Black; //根节点为黑色
		return true;
	}
	//1、查找插入节点
	TreeNode* cur = _root, * parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
			return false;
	}
	//2、插入连接
	TreeNode* newnode = new TreeNode(kv);
	if (kv.first < parent->_kv.first) //newnode在parent的左边
		parent->_left = newnode;
	else
		parent->_right = newnode;
	newnode->_parent = parent;
	
	//3、判断迭代
	cur = newnode;
	//循环条件直接作为判断条件，如果parent->_col == Black不进入循环，插入结束
	while (parent && parent->_col == Red) //P不为nullptr且P为红色
	{
		//第一次进入循环的parent不可能是根
		TreeNode* gparent = parent->_parent; //拿到G节点
		if (gparent->_left == parent) //P在G的左边
		{
			TreeNode* uncle = gparent->_right;
			if (uncle && uncle->_col == Red) //uncle是红色
			{
				//变色
				parent->_col = uncle->_col = Black;
				gparent->_col = Red;
				//迭代
				cur = gparent;
				parent = cur->_parent;
			}
			else //uncle是NIF || 黑色
			{
				//旋转变色
				if (parent->_left == cur) //单旋转
				{
					//右单旋
					Rotate_Right(gparent);
					//变色
					cur->_col = gparent->_col = Red;
					parent->_col = Black;
				}
				else //左右双旋
				{
					Rotate_LR(gparent);
					//变色
					parent->_col = gparent->_col = Red;
					cur->_col = Black;
				}
				break; //插入结束
			}
		}
		else //P在G的右边
		{
			TreeNode* uncle = gparent->_left;
			if (uncle && uncle->_col == Red) //uncle是红色
			{
				//变色
				parent->_col = uncle->_col = Black;
				gparent->_col = Red;
				//迭代
				cur = gparent;
				parent = cur->_parent;
			}
			else //uncle是NIF || 黑色
			{
				//旋转变色
				if (parent->_right == cur) //单旋转
				{
					//左单旋
					Rotate_Left(gparent);
					//变色
					cur->_col = gparent->_col = Red;
					parent->_col = Black;
				}
				else //右左双旋
				{
					Rotate_RL(gparent);
					//变色
					parent->_col = gparent->_col = Red;
					cur->_col = Black;
				}
				break; //插入结束
			}
		}
	}
	_root->_col = Black; //保证根是黑色
	return true;
}

3. 红黑树性能分析和总结

我们不妨推导一下红黑树的最深深度：

假设：红黑树的高度为h；最短路径为h_s；总节点个数为N。

所以，红黑树至少拥有的节点个数 N₀ = 2^h_s - 1。红黑树的最短路径就相当于其最小深度。

同时：N >= N₀成立。且h <= 2 * h_s成立。

进行代换，不等式传递：h <= 2 * $log_2(N+1)$ 。

即：红黑树最差情况下，深度为： $2log_2(N)$ 级别……
关于红黑树的性能分析，我们不妨与AVL树进行对比。

	AVL树	红黑树
特点	左右子树高度差不会超过1	最长路径的长度不会超过最短路径的2倍
高度	平均 $log_2(N)$	最坏情况下2 $log_2(N)$

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( $log_2 N$ )，但是红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数。虽然在查找上红黑树的效率不如AVL树，但是是同一个量级的。更何况红黑树减少了AVL树在旋转上的开销。

旋转和高度对比

对待同样的10w+数据，红黑树旋转次数明显少于AVL树。

因此在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
适用场景
- AVL 树：适合查询操作远多于插入 / 删除的场景（如静态数据查询）。例如：数据库中不常更新的索引、需要高频次查询的字典表。
- 红黑树：适合插入 / 删除操作频繁的场景。例如：Java 的TreeMap、TreeSet，C++ 的map、set，Linux内核的进程调度、内存管理等（频繁更新时，红黑树的低调整成本更具优势）。
总结：
1. 查询优先选 AVL：严格平衡带来更低的树高，查询效率略高。
2. 更新优先选红黑树：弱平衡策略减少旋转次数，插入 / 删除成本更低，且空间开销更小。

红黑树插入模拟及测试源码（C++）

#pragma once

#include <iostream>
#include <cassert>


namespace LL
{

	enum Color
	{
		Red = 0,
		Black
	};

	template <class K, class V>
	struct RBTreeNode
	{
		typedef RBTreeNode<K, V> TreeNode;
		TreeNode* _parent;
		TreeNode* _left;
		TreeNode* _right;
		std::pair<K, V> _kv;
		Color _col;

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

	template <class K, class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> TreeNode;
	public:
		RBTree()
			:_root(nullptr)
		{ }
	private:
		void _inorder(TreeNode* root)
		{
			if (!root) return;

			_inorder(root->_left);
			std::cout << root->_kv.second << " ";
			_inorder(root->_right);
		}
	public:
		void inorder()
		{
			_inorder(_root);
		}
		bool insert(const std::pair<K, V>& kv)
		{
			if (!_root)
			{
				_root = new TreeNode(kv);
				_root->_col = Black; //根节点为黑色
				return true;
			}
			//1、查找插入节点
			TreeNode* cur = _root, * parent = nullptr;
			while (cur)
			{
				if (kv.first < cur->_kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (kv.first > cur->_kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return false;
			}
			//2、插入连接
			TreeNode* newnode = new TreeNode(kv);
			if (kv.first < parent->_kv.first) //newnode在parent的左边
				parent->_left = newnode;
			else
				parent->_right = newnode;
			newnode->_parent = parent;
			
			//3、判断迭代
			cur = newnode;
			//循环条件直接作为判断条件，如果parent->_col == Black不进入循环，插入结束
			while (parent && parent->_col == Red) //P不为nullptr且P为红色
			{
				//第一次进入循环的parent不可能是根
				TreeNode* gparent = parent->_parent; //拿到G节点
				if (gparent->_left == parent) //P在G的左边
				{
					TreeNode* uncle = gparent->_right;
					if (uncle && uncle->_col == Red) //uncle是红色
					{
						//变色
						parent->_col = uncle->_col = Black;
						gparent->_col = Red;
						//迭代
						cur = gparent;
						parent = cur->_parent;
					}
					else //uncle是NIF || 黑色
					{
						//旋转变色
						if (parent->_left == cur) //单旋转
						{
							//右单旋
							Rotate_Right(gparent);
							//变色
							cur->_col = gparent->_col = Red;
							parent->_col = Black;
						}
						else //左右双旋
						{
							Rotate_LR(gparent);
							//变色
							parent->_col = gparent->_col = Red;
							cur->_col = Black;
						}
						break; //插入结束
					}
				}
				else //P在G的右边
				{
					TreeNode* uncle = gparent->_left;
					if (uncle && uncle->_col == Red) //uncle是红色
					{
						//变色
						parent->_col = uncle->_col = Black;
						gparent->_col = Red;
						//迭代
						cur = gparent;
						parent = cur->_parent;
					}
					else //uncle是NIF || 黑色
					{
						//旋转变色
						if (parent->_right == cur) //单旋转
						{
							//左单旋
							Rotate_Left(gparent);
							//变色
							cur->_col = gparent->_col = Red;
							parent->_col = Black;
						}
						else //右左双旋
						{
							Rotate_RL(gparent);
							//变色
							parent->_col = gparent->_col = Red;
							cur->_col = Black;
						}
						break; //插入结束
					}
				}
			}
			_root->_col = Black; //保证根是黑色
			return true;
		}
		size_t GetRotateCount()
		{
			return _rotatecount;
		}
	private:
		//1、左单旋
		void Rotate_Left(TreeNode* parent) //传入需要旋转的节点
		{
			//1、多用变量保存节点
			TreeNode* pparent = parent->_parent; //祖父节点
			TreeNode* cur = parent->_right;
			TreeNode* curleft = cur->_left;

			//2、更改链接关系
			//parent的
			parent->_right = curleft;
			parent->_parent = cur;
			//cur的
			cur->_left = parent;
			cur->_parent = pparent;
			// cueleft的
			if (nullptr != curleft) //简单模型的特殊判断
				curleft->_parent = parent;
			//pparent的
			if (!pparent) //如果parent是根节点
			{
				_root = cur; //更新根节点
			}
			else //parent不是根节点
			{
				if (pparent->_left == parent) //如果原来parent在pparent的左边
					pparent->_left = cur;
				else //在右边
					pparent->_right = cur;
			}
			++_rotatecount;
		}
		//2、右单旋
		void Rotate_Right(TreeNode* parent)
		{
			//1、多用变量保存节点
			TreeNode* pparent = parent->_parent; //祖父节点
			TreeNode* cur = parent->_left;
			TreeNode* curright = cur->_right;

			//2、更改链接关系
			//parent的
			parent->_left = curright;
			parent->_parent = cur;
			//cur的
			cur->_right = parent;
			cur->_parent = pparent;
			//curright的
			if (nullptr != curright)
				curright->_parent = parent;
			//pparent的
			if (!pparent) //如果parent是根节点
			{
				_root = cur; //更新根节点
			}
			else //parent不是根节点
			{
				if (pparent->_left == parent) //如果原来parent在pparent的左边
					pparent->_left = cur;
				else //在右边
					pparent->_right = cur;
			}
			++_rotatecount;
		}
		//3、左右双旋
		void Rotate_LR(TreeNode* parent)
		{
			TreeNode* cur = parent->_left;
			TreeNode* curright = cur->_right;
			//复用两次单旋
			Rotate_Left(cur); //以cur为中心
			Rotate_Right(parent);
			//更新平衡因子
		}
		//4、右左双旋
		void Rotate_RL(TreeNode* parent)
		{
			TreeNode* cur = parent->_right;
			TreeNode* curleft = cur->_left;
			//复用两次单旋
			Rotate_Right(cur); //以cur为中心
			Rotate_Left(parent);
		}
	public: //得到二叉数的高度
		int GetHeight()
		{
			return _GetHeight(_root);
		}
	private:
		int _GetHeight(TreeNode* root)
		{
			if (root == nullptr)
				return 0;

			int left = _GetHeight(root->_left);
			int right = _GetHeight(root->_right);

			return left > right ? left + 1 : right + 1;
		}
	public:
		bool IsValidRBTree()
		{
			TreeNode* root = _root;
			// 空树也是红黑树
			if (nullptr == root)
				return true;
			// 检测根节点是否满足情况
			if (Black != root->_col)
			{
				std::cout << "违反红黑树性质二：根节点必须为黑色" << std::endl;
				return false;
			}
			// 获取任意一条路径中黑色节点的个数
			size_t blackCount = 0;
			TreeNode* cur = root;
			while (cur)
			{
				if (Black == cur->_col)
					blackCount++;
				cur = cur->_left;
			}
			// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
			size_t k = 0;
			return _IsValidRBTree(root, k, blackCount);
		}
	private:
		bool _IsValidRBTree(TreeNode* root, size_t k, const size_t blackCount)
		{
			//走到null之后，判断k和black是否相等
			if (nullptr == root)
			{
				if (k != blackCount)
				{
					std::cout << "违反性质四：每条路径中黑色节点的个数必须相同" << std::endl;
					return false;
				}
				return true;
			}
			// 统计黑色节点的个数
			if (Black == root->_col)
				k++;
			// 检测当前节点与其双亲是否都为红色
			TreeNode* parent = root->_parent;
			if (parent && Red == parent->_col && Red == root->_col)
			{
				std::cout << "违反性质三：不能有连在一起的红色节点" << std::endl;
				return false;
			}
			return _IsValidRBTree(root->_left, k, blackCount) &&
				_IsValidRBTree(root->_right, k, blackCount);
		}


	private:
		TreeNode* _root;
		size_t _rotatecount; //统计旋转次数
	};
}

//-----------------------------------------------------------------
#include "RBTree.hpp"
#include <ctime>
#include <random>

int main()
{
	LL::RBTree<int, int> r;
	//r.insert({ 16, 16 });
	//r.insert({ 3, 3 });
	//r.insert({ 7, 7 });
	//r.insert({ 11, 11 });
	//r.insert({ 9, 9 });
	//std::cout << r.IsValidRBTree() << std::endl;
	//r.insert({ 26, 26 });
	//std::cout << r.IsValidRBTree() << std::endl;
	//r.insert({ 18, 18 });
	//std::cout << r.IsValidRBTree() << std::endl;
	//r.insert({ 14, 14 });
	//r.insert({ 15, 15 });

	//r.inorder();

	//std::cout << std::endl;
	//std::cout << r.IsValidRBTree() << std::endl;

	srand((unsigned int)time(nullptr));

	for (int i = 0; i < 100000; ++i)
	{
		int tmp = rand();
		r.insert({ tmp, tmp });
	}
	std::cout << r.GetRotateCount() << std::endl;
	std::cout << "高度为：" << r.GetHeight() << std::endl;
	return 0;
}

完。

希望这篇文章能够帮助你！！

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能