文章目录


在这里插入图片描述

1 红黑树的概念

红黑树是一棵二叉搜索树，每个节点额外存储颜色标识，颜色分为红色、黑色两种。

红黑树通过约束根到叶子路径上的节点颜色，保证任意一条路径的长度不会超过其他路径的2倍，属于近似平衡二叉树。

1.1 红黑树五大规则

  1. 每个节点的颜色只能是红色或黑色。
  2. 根节点必须为黑色。
  3. 若一个节点为红色，则其两个子节点都必须是黑色（路径中不存在连续红色节点）。
  4. 对于任意节点，从该节点出发到所有空（NIL）节点的每条路径，包含的黑色节点数量相同。
  5. 所有空节点（NIL/外部节点）均为黑色。

补充说明：此处的叶子特指空NIL节点（外部节点），并非传统意义上的实际叶子节点；部分代码实现中会省略对NIL节点的显性处理，了解概念即可。

这里给几个红黑树图例帮助理解：
在这里插入图片描述

1.2 最长路径不超过最短路径 2 倍

红黑树依靠自身五大约束保证最长路径≤最短路径的2倍：

  1. 所有根到空节点的路径黑节点数量一致（黑高bh），全黑路径即为最短路径，长度等于bh。
  2. 规则禁止连续红节点，路径中红节点必须与黑节点相间排列。极限情况下每条黑节点后搭配一个红节点，最长路径长度为2bh。
  3. 综上，任意路径长度介于bh与2bh之间，因此最长路径不会超过最短路径的2倍。

2. 红黑树的底层实现

2.1 初始框架

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

// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
    // 这里更新控制平衡也要加入parent指针
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _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 红黑树的插入

红黑树的插入分三种情况，我们需要在每次插入式考虑红黑树的4条规则。
大概有以下内容：
1.空树插入：新增结点为黑色结点。
2.非空树插入：新增结点必须为红色结点；若插入黑色结点，会直接破坏红黑树规则 4（每条路径黑结点数量相同），该规则极难维护，因此非空插入默认染红。
3.非空树插入后：
新增结点为红色，若父结点是黑色，未违反任何红黑树规则，插入直接结束。
4.非空树插入后：
新增结点为红色，若父结点是红色，违反红黑树规则 3（红色结点不能有红色子结点，即无连续红结点）；
此时可确定固定颜色：当前结点（红）、父结点（红）、祖父结点（黑）；
最终调整方案，完全由叔叔结点（u） 的颜色决定，需分情况处理。

2.2.1 情况一：仅变色

只要叔叔节点 u 是红色，就只变色、不旋转！
这其实很好理解。
为什么这种情况 只变色、不旋转？
因为：
叔叔 u 是红色 → 变色就能直接修复连续红，还能保持黑高不变。

完整逻辑链：

  1. c红、p红、g黑、u红
    出现了 连续红（c-p），违反规则。

  2. p 和 u 都是红色、且都是 g 的孩子
    把 p、u 同时变黑
    → 两条子树的黑高 各 +1

  3. 为了保持整棵树黑高不变
    把 g 变红
    → g 所在路径黑高 -1
    → 整体黑高恢复平衡

  4. 连续红消失了，黑高也没变
    → 完全不需要旋转！
    这里给出图例：
    在这里插入图片描述
    代码实现：

if (uncle && uncle->_col == RED)  // 修改8：= RED -> == RED
{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
}

2.2.2 情况二：单旋+变色

情况：叔叔 u 为黑 / 不存在；

前提条件

  • 当前节点c：红色
  • 父节点p：红色
  • 祖父节点g：黑色
  • 叔叔节点u：不存在 或 存在且为黑色

关键推论

  1. u不存在 → c一定是新增节点
  2. u存在且为黑 → c一定不是新增节点，是之前变色后向上更新上来的

核心分析

  • 存在连续红色节点（c-p）违规
  • 单纯变色无法修复黑高平衡
  • 必须采用：旋转 + 变色 组合处理

具体处理规则
1.左左情况（p是g的左孩子，c是p的左孩子）

  • 操作：以g为支点执行右单旋
  • 变色：p变黑，g变红
  • 结果：p成为子树根节点，黑高不变，无连续红节点，无需向上更新
  1. 右右情况（p是g的右孩子，c是p的右孩子）
  • 操作：以g为支点执行左单旋
  • 变色：p变黑，g变红
  • 结果：p成为子树根节点，黑高不变，无连续红节点，无需向上更新
    给个示例：
    在这里插入图片描述
    代码分享：
//在左边
if (cur == parent->_left)
{
				//     g
				//   p    u
				// c
				RotateR(grandfather);//将g右旋，p为父，p变黑，g变红（这里P肯定是红的,循环条件）
				parent->_col = BLACK;
				grandfather->_col = RED;
}

左右旋代码后面给出。

2.2.3 双旋+变色

父子节点呈折线、叔叔节点为空或黑色时，执行双旋。

前提条件

  • 当前节点c：红色
  • 父节点p：红色
  • 祖父节点g：黑色
  • 叔叔节点u：不存在 或 存在且为黑色

关键推论

  1. u不存在 → c 一定是新增节点
  2. u存在且为黑 → c 一定不是新增节点，是子树插入后经变色向上更新而来

核心分析

  • 存在c-p连续红色节点违规
  • 单纯变色无法修复黑高，必须旋转+变色

1. 左右情况（p是g的左孩子，c是p的右孩子）

  1. 以p为支点执行左单旋
  2. 以g为支点执行右单旋
  3. 变色：c变黑，g变红
  4. 结果：c成为子树根，黑高不变，无连续红节点，无需向上更新

2. 右左情况（p是g的右孩子，c是p的左孩子）

  1. 以p为支点执行右单旋
  2. 以g为支点执行左单旋
  3. 变色：c变黑，g变红
  4. 结果：c成为子树根，黑高不变，无连续红节点，无需向上更新

核心：叔叔红只变色，叔叔黑/无则旋转加变色。
示例：
在这里插入图片描述
代码分享：

else//在右边
{
				//      g
				//   p    u
				//     c
				RotateL(parent);//先左旋，再右旋，将parent右边节点与parent左旋，再一g右旋
				//     g
				//   c    u
				// p
				RotateR(grandfather);
				//      c
				//   p    g
				//            u
				cur->_col = BLACK;
				grandfather->_col = RED;
}

2.3 左右旋代码分享

//右旋
void RotateR(Node* parent)
{	//subl是子节点，subl右节点放parent左边，parent的父节点换为subl,subl的右节点换为parent
	//如果parent为root，则subl的父节点为null,不为root就换为parent之前的父节点
	Node* subl = parent->_left;
	Node* sublR = subl->_right;
	parent->_left = sublR;

	if (sublR) {
		sublR->_parent = parent;

	}
	Node* pParent = parent->_parent;  // 修改11：保存祖父节点

	subl->_right = parent;
	parent->_parent = subl;

	if (parent == _root)
	{
		_root = subl;
		subl->_parent = nullptr;

	}
	else
	{
		if (pParent->_left == parent)
		{
			pParent->_left = subl;  // 修改12：subL -> subl
		}
		else
		{
			pParent->_right = subl;  // 修改13：subL -> subl
		}

		subl->_parent = pParent;  // 修改14：subL -> subl
	}
}

//左转，和右转差不多
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;
	}
}

3. 整体代码

#pragma once
#include <iostream>
using namespace std;

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


// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
	// 这里更新控制平衡也要加入parent指针
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _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:
	bool Insert(const pair<K, V>& kv)
	{
		//先来个根节点
		if (_root == nullptr) {  // 修改1：null -> nullptr
			_root = new Node(kv);//这里是指针
			_root->_col = BLACK;

			return true;
		}
		Node* parent = nullptr;  // 修改2：NULL -> 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还是空，这里实例化
		cur = new Node(kv);
		cur->_col = RED;
		//因为之前cur是空指针，所以需要重新关联父节点
		if (parent->_kv.first < kv.first) {  // 修改3：parent->kv.first -> parent->_kv.first
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;  // 修改4：插入后设置父节点指针
		//这里已经插入节点，但还需要通过旋转来维护红黑树规则
		while (parent && parent->_col == RED)
		{
			//定义个爷，便于找
			Node* grandfather = parent->_parent;  // 修改5：parent->_right -> parent->_parent
			//parent在g左边
			if (parent == grandfather->_left)  // 修改6：grandfather->_right -> grandfather->_left
			{
				Node* uncle = grandfather->_right;  // 修改7：grandfather->_right -> grandfather->_right（保持，但上面条件改了）
				//叔节点在且为红，与parent节点一样
				if (uncle && uncle->_col == RED)  // 修改8：= RED -> == RED
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//uncle为空或为黑，这个时候为了维护规则
				//需要以g右旋，g,u,p均变色
				else
				{
					//在左边
					if (cur == parent->_left)
					{
						//     g
						//   p    u
						// c
						RotateR(grandfather);//将g右旋，p为父，p变黑，g变红（这里P肯定是红的,循环条件）
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//在右边
					{
						//      g
						//   p    u
						//     c
						RotateL(parent);//先左旋，再右旋，将parent右边节点与parent左旋，再一g右旋
						//     g
						//   c    u
						// p
						RotateR(grandfather);
						//      c
						//   p    g
						//            u
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}

			else//差不多，反着来
			{
				//   g
				// u   p
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红，-》变色即可
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 叔叔不存在，或者存在且为黑
				{
					// 情况二：叔叔不存在或者存在且为黑
					// 旋转+变色
					//   g
					// u   p
					//       c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}
		_root->_col = BLACK;  // 修改9：确保根节点为黑色
		return true;  // 修改10：添加返回值
	}
	//右旋
	void RotateR(Node* parent)
	{	//subl是子节点，subl右节点放parent左边，parent的父节点换为subl,subl的右节点换为parent
		//如果parent为root，则subl的父节点为null,不为root就换为parent之前的父节点
		Node* subl = parent->_left;
		Node* sublR = subl->_right;
		parent->_left = sublR;

		if (sublR) {
			sublR->_parent = parent;

		}
		Node* pParent = parent->_parent;  // 修改11：保存祖父节点

		subl->_right = parent;
		parent->_parent = subl;

		if (parent == _root)
		{
			_root = subl;
			subl->_parent = nullptr;

		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subl;  // 修改12：subL -> subl
			}
			else
			{
				pParent->_right = subl;  // 修改13：subL -> subl
			}

			subl->_parent = pParent;  // 修改14：subL -> subl
		}
	}

	//左转，和右转差不多
	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;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}


		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}


	// 前序递归遍历
	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 前序遍历走到空时，意味着一条路径走完了
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色结点的数量不相等的路径" << endl;
				return false;
			}
			return true;
		}


		// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色结点" << endl;
			return false;
		}


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


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


	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 Check(_root, 0, refNum);
	}

	Node* getroot() {
		return _root;
	}
private:
	Node* _root = nullptr;
};
# c++ # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

2026年，讯飞星火海外访问中转方案究竟有何独特之处？

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

Java分布式架构设计方法

服务拆分后，服务间的通信成为关键。事件驱动架构是另一种有效解耦和数据同步的方式，服务通过发布/订阅领域事件进行通信，借助Apache Kafka或RabbitMQ等消息中间件，可以实现事件的可靠传递与异步处理，提升系统整体响应能力。从业务拆分出发，选择恰当的通信与治理模式，妥善处理数据一致性，并构建完善的运维支撑体系。随着云原生理念的深入，Serverless、Service Mesh等新技术也在

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

分布式事务尝试取消确认模式的具体实现步骤

首先需要事务协调器（Transaction Coordinator），负责协调整个分布式事务的流程，记录事务状态，并在必要时触发补偿操作。尝试取消确认模式（Try-Cancel-Confirm，简称TCC）作为一种补偿型分布式事务解决方案，通过业务逻辑层面的拆解，提供了更灵活的一致性实现方式。未来，随着事务中间件的成熟和云原生技术的发展，TCC模式的实施成本将进一步降低，应用场景也将更加广泛。Co

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