C++红黑树（RBTree）原理、性质与完整实现

听雨眠

发布时间：2026-10-15 | 5人浏览过

原创

深入理解C++红黑树的五大性质及其在插入操作中维持平衡的机制。文章详细解析了当新节点破坏“红色节点无连续子节点”规则时的三种修正策略（变色、左旋、右旋），并提供基于模板类的完整实现代码，涵盖三叉链节点结构、BST查找插入逻辑及严格的合法性校验方法。

红黑树的核心概念

红黑树（Red-Black Tree）本质上是一棵二叉搜索树（BST），但其每个节点额外增加了一个存储位来记录颜色（通常为 Red 或 Black）。这种着色限制确保了从根节点到任意叶子节点的最长路径长度不会超过最短路径长度的两倍，从而实现了近似平衡。这意味着虽然它不是严格平衡（如AVL树那样高度差受限），但在大多数实际应用中提供了更优的平均性能和维护成本。

红黑树的五大性质

节点颜色：每个节点非红即黑。
根节点：根节点必须是黑色。
无连续红节点：如果一个节点是红色，则其两个子节点必须是黑色（即不存在连续的红色节点）。
黑高相同：对于同一个节点，从该节点到其所有后代叶子节点的简单路径上，包含相同数目的黑色节点（称为黑高）。
叶子节点：所有的叶子节点（NULL或NIL节点）都是黑色的。空树视为满足此性质。

理解平衡性保证

结合性质3和4可以推断：最短路径可以是全黑路径；而最长路径则是红黑相间的路径。由于每条路径的黑色节点数量必须一致，且红色不能相连，因此最长路径最多是全黑路径长度的两倍。这保证了树的高度始终保持在 O(log N) 量级。

节点结构与默认颜色选择

红黑树通常采用三叉链结构（含父节点指针），便于回溯调整。相比AVL树使用的平衡因子字段，这里使用枚举类型表示颜色。

//结点颜色
template<class K, class V >
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	enum Color { RED, BLACK };
	Color _col;
	//默认构造为红色
	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
	{}
};

为什么默认设为红色？
如果插入黑色节点，会直接违反性质4（不同路径黑节点数不同），需要全局维护。如果插入红色节点，仅可能违反性质3（红父红子），但若其父节点原本为黑色，则无需调整。因此，将新节点默认为红色可以减少调整发生的概率。

插入与自平衡算法

插入流程分为两步：首先按BST规则找到位置并插入一个红色新节点；其次检查是否破坏红黑性质，若被破坏则进行调整。调整的关键在于当前节点(cur)、父节点(parent)、祖父节点(grandfather)和叔叔节点(uncle)之间的相对关系。

注意：在进行任何修复操作前，建议对现有数据结构进行备份或在测试环境中验证，以免逻辑错误导致链表断裂或内存泄漏。

第1步：定位与初步插入

类似于普通二叉搜索树，从根开始遍历寻找插入位置。若key已存在则返回false；否则创建新节点，默认颜色为RED，并通过判断大小关系将其挂载至父节点下。

第2步：自平衡调整（分三种情况）

仅当 `parent` 存在且为红色时触发调整（根为空或parent为黑色时无需调整）。此时需考察叔叔节点(u)的颜色。

情况一：叔叔节点存在且为红色

特征：cur为红, p为红, g为黑, u存在且为红。
策略：变色。
1. 将 parent 和 uncle 变为 BLACK。
2. 将 grandfather (g) 变为 RED。
3. 此时 g 变为新的 cur，继续向上递归检查。若 g 最终变成根，则强制将其染回 BLACK。

情况二：叔叔节点不存在或为黑色，且 cur/p/g 在同一侧

特征：u不存在/u为黑, cur/p/g 同侧（如左左或右右）。
策略：单旋 + 变色。
1. 若 p 是 g 的左孩子，cur 是 p 的左孩子，则对 g 进行右旋。
2. 若 p 是 g 的右孩子，cur 是 p 的右孩子，则对 g 进行左旋。
3. 旋转后，原 parent 变黑，原 grandfather 变红。

情况三：叔叔节点不存在或为黑色，且 cur/p/g 不在同一侧

特征：u不存在/u为黑, gpc 折线型（如左右或右左）。
策略：双旋 + 变色。
1. 先以 cur 为轴进行一次旋转，使其转化为情况二的形态（直线型）。例如：若 p 为左孩子，cur 为右孩子，则先对 p 左旋。
2. 再进行情况二的反向旋转（对 g 右旋）。
3. 最后调整颜色：原 cur 变黑，原 g 变红。

C++ 完整代码实现

以下实现包含了旋转函数、插入逻辑以及用于验证红黑树合法性的检测函数。

#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;

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>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_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;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		
		// 调整平衡
		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			if (parent == grandfater->_left)
			{
				Node* uncle = grandfater->_right;
				//情况一：u存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
					//向上调整
					cur = grandfater;
					parent = cur->_parent;
				}
				else//其他情况，需要旋转
				{
					//情况2：cur与parent同侧
					if (cur == parent->_left)
					{
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					//情况3：cur与parent异侧
					else
					{
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
			else//parent==grandfater->_right
			{
				Node* uncle = grandfater->_left;
				//情况1：u存在且为红色
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfater->_col = RED;
					//向上调整
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					//情况2：cur与parent同侧
					if (cur == parent->_right)
					{
						RotateL(grandfater);
						grandfater->_col = RED;
						parent->_col = BLACK;
					}
					//情况3：cur与parent异侧
					else
					{
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
		}
		//根变黑
		_root->_col = BLACK;
		return true;
	}
	
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (ppNode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}
	
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		subL->_right = parent;
		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}
	
	void InOrder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	
	// 检测红黑树合法性
	bool Check(Node*root,int blackNum,int ref)
	{
		if (root == nullptr)
		{
			if (blackNum != ref)
			{
				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,ref)
			&& Check(root->_right,blackNum,ref);
	}
	
	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}
		if (_root->_col != BLACK)
		{
			return false;
		}
		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				++ref;
			}
			left = left->_left;
		}
		return Check(_root,0,ref);
	}
private:
	Node* _root = nullptr;
};

void TestRBTree1()
{
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestRBTree2()
{
	srand(time(0));
	const size_t N = 100000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; i++)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}
	cout << t.IsBalance() << endl;
}

以上就是C++中红黑树的原理、插入自平衡机制及完整源码实现的详细内容，更多关于C++容器底层原理、STL设计与优化的资料请关注本站其它相关文章！