【C++进阶】红黑树：平衡规则原理、三大调整场景与完整代码实现

Z2382430464

379人浏览 · 2026-05-25 06:00:00

Z2382430464 · 2026-05-25 06:00:00 发布

1.红黑树的概念

红黑树是一棵二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或黑色。
通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的

1.1 红黑树的规则

每个结点不是红色就是黑色
根节点是黑色的
如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点
对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点
说明：《算法导论》等书籍上补充了一条每个叶子结点（NIL）都是黑色的规则。这里的叶子节点指的不是传统意义上的叶子结点，而是空节点，有些书籍上也把NIL结点叫做外部结点。NIL结点是为了方便准确的标识出所有路径。

1.2 红黑树如何保证最长路径不超过最短路径2倍？

右规则4可知，从根到 NULL 结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就是全为黑色结点的路径，假设最短路径的长度为 bh(black height)
由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长路径就是一黑一红间隔组成，那么最长路径的长度为 2 * bh
综合红黑树的四条规则，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到 NULL 结点路径的长度为 h，那么 bh <= h <= 2 * bh

1.3 红黑树的效率

假设 N 是红黑树中结点的数量，h 为最短路径的长度，那么 2^h - 1 <= N <= 2^(2h) - 1，由此推出 h ≈ logN，也就是意味着红黑树增删查改最坏情况下也就是走最长路径 2logN，那么时间复杂度还是 O(logN)
红黑树的表达相对 AVL 树要抽象一些，AVL树通过高度差直观的控制了平衡，红黑树通过四条规则的颜色约束间接实现了近似平衡，他们的效率是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数更少，因为它对平衡的控制没有AVL树严格

2.红黑树的实现

2.1 红黑树的结构

// 枚举值表示颜色
enum Color
{
	RED,
	BLACK
};

// key/value结构
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>& 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(cur)，c 的父亲结点为 p(parent)，p 的父亲结点为 g(grandfather)，p 的兄弟结点为 u(uncle)

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 的左孩子还是右孩子，都是一样的变色处理方式。

2.2.3 情况2：单旋+变色

c 为红，p 为红，g 为黑，u 不存在或u存在且为黑。
若u不存在，则c一定是新增结点；u存在且为黑，则c一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况1，变色将 c 从黑色变成红色，更新上来的。
分析：p 必须变黑才能解决连续红色结点的问题。u 不存在或 u 存在且为黑色时，单纯变色无法解决问题，需要旋转 + 变色。

      g
   p     u
c

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

      g
   u     p
            c

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

例如：当 bh == 1 时
bh==1单旋+变色

2.2.4 情况3：双旋+变色

      g
   p     u
     c

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

      g
   u     p
       c

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

双旋+变色

例如：当 bh == 1 时
bh==1双旋+变色

2.3 红黑树的插入代码实现

红黑树插入时的旋转逻辑和AVL树是一样的，只是不需要更新平衡因子
右旋和左旋

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// subLR 连接 parent
	// subLR 非空时才能更改其 _parent
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;

	// 记录 parent 的原 parent
	Node* parentParent = parent->_parent;
	
	// subL 连接 parent
	subL->_right = parent;
	parent->_parent = subL;

	// parent 可能是整棵树的根，也可能是局部的子树
	// 如果是整棵树的根，要修改 _root
	// 如果是局部的指针要与上一层连接
	if (parentParent == nullptr)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subL;
		}
		else
		{
			parentParent->_right = subL;
		}

		subL->_parent = parentParent;
	}
}

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

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

	Node* parentParent = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR;

	if (parentParent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subR;
		}
		else
		{
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}
}

插入时双旋可以通过调用两次单旋完成

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 < cur->_kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	// 父亲节点存在并且为红色：出现了连续的红色结点，需要处理
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;

		//   g
		// p   u
		// uncle存在且为右孩子
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;

			// uncle存在且为红色
			// 直接修改 parent 和 uncle为黑色，grandfather为红色
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续向上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// u存在且为黑或不存在
				//     g
				//   p   u
				// c
				// LL 右旋+变色
				if (cur == parent->_left)
				{
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//   g
					// p   u
					//  c	
					// LR 左右双旋
					RotateL(parent);
					RotateR(grandfather);

					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
		else {
			//   g
			// u   p
			// uncle存在且为左孩子
			Node* uncle = grandfather->_left;

			// uncle存在且为红色
			// 直接修改 parent 和 uncle为黑色，grandfather为红色
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续向上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// u存在且为黑或不存在
				//   g
				// u   p
				//       c
				// RR 左旋+变色
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//   g
					// u   p
					//    c	
					// RL 左右双旋
					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 (key > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else if (key < cur->_kv.first)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}

	return nullptr;
}

2.5 红黑树的验证

规则1：枚举颜色类型保证红黑树中只有RED和BLACK两种颜色，无需检查
规则2：直接检查根即可
规则3：遍历二叉树，检查每个红色结点的父亲节点是否为红色
规则4：前序遍历，遍历过程中用形参记录根到当前结点的blackNum（黑色结点数量），前序遍历遇到黑色结点就blackNum++，走到空就计算出当前路径的黑色结点数量，将黑色结点数量与基准值（任意一条路径的黑色结点数量）比较即可

bool IsBalanceTree()
{
	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 _IsBalanceTree(_root, 0, refNum);
}

bool _IsBalanceTree(Node* root, int blackNum, const int refNum)
{
	if (root == nullptr)
	{
		if (refNum != blackNum)
		{
			cout << "存在黑色结点数量不相等的路径" << endl;
			return false;
		}
		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "存在连续红色结点" << endl;
		return false;
	}

	if (root->_col == BLACK)
	{
		blackNum++;
	}

	return _IsBalanceTree(root->_left, blackNum, refNum) 
		&& _IsBalanceTree(root->_right, blackNum, refNum);
}

亚马逊云科技技术品牌专区

更多推荐

从0到1构建AIGC产品：全栈视角下的LLM技术方案选型与落地实践

亚马逊云科技技术品牌专区

第一篇博客｜零基础女生备战 408 碎碎念日记

我是炫炫，人工智能专业的普通女生一枚。说实话我属于纯零基础选手😭，代码底子特别薄弱，现在啃 C 语言天天抓头发，随便敲几行代码全是报错，调不通程序的时候真的会偷偷 emo 好久。🥰开这个小窝就是用来记录我一点点补c语言基础、冲刺 408的全过程，专门留给和我一样起步困难的女孩子抱团取暖。也欢迎各位业界大佬路过，多多指点我的不足，🙈有学习建议都可以留在评论区，我会认真看、虚心吸收！讲真心话，C