目录

1.红黑树的概念

2.红黑树的性质

3.红黑树节点的定义

4.红黑树的插入操作

（1）. 按照二叉搜索的树规则插入新节点

（2）检测新节点插入后，红黑树的性质是否造到破坏

情况一：u存在且为红

情况二.u节点不存在或存在且为黑

5.红黑树与AVL树的比较

6.红黑树的代码实现：

1.红黑树的概念

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

2.红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的 

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？

  一个节点到其叶子节点的所有路径中黑色节点的个数，称为“黑色高度”；通过性质4可以知道，根节点的所有路径中，黑色高度都是一样的，假设为x；另外，还可以推出：黑色节点可以连续，红色节点不能连续；

  对于最短路径：最短情况即：路径上全是黑色节点，没有红色节点，长度为x；

  对于最长路径：最长情况即，在x个黑色节点中，每两个黑色节点之间就有一个红色节点，长度为2*x；

因此，最长路径不会超过最短路径的两倍；

红黑树的平衡标准就是：任何一条路径都不会比其他路径长出俩倍——最长路径不会超过最短路径的两倍；

想要做到这一点，就必须维护好上述性质，主要是性质3和性质4！

3.红黑树节点的定义

enum Color
{
	Red = 0,
	Black
};
template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _data;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>*_right;
	RBTreeNode<K, V>* _parent;
	Color _color;

	RBTreeNode(const pair<K,V> &data)
		:_data(data),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_color(Red)
	{}
};

   可以看出，我们采用的是KV模式，红黑树的每节点还要维护父节点，以及节点颜色（用枚举表示）。

   在创建节点的时候，我们默认给的是红色，而不是黑色，原因如下：

  红黑树的性质4要求从一个节点出发的每条路径的“黑色高度”必须相同，如果将节点设为黑色，那么在插入节点后，一定会破坏黑色高度的一致性，违反了性质4，必须通过旋转和重新着色修复，操作复杂。而红色节点只需检查是否违反性质3（无连续红色），调整（不一定用旋转）更简单。因此默认采用红色节点可以减少旋转次数，提高效率；

4.红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

（1）. 按照二叉搜索的树规则插入新节点

if (_root == nullptr)
{
	_root = new Node(data);
	_root->_color = Black;
	return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
	if (cur->_data.first < data.first)
	{
		parent = cur;
		cur = cur->_right;
	}
	else if (cur->_data.first > data.first)
	{
		parent = cur;
		cur = cur->_left;
	}
	else
	{
		return false;
	}
}
cur = new Node(data);
if (parent->_data.first < data.first)
{
	parent->_right = cur;
}
else
{
	parent->_left = cur;
}
cur->_parent = parent;

  与普通二叉搜索树的插入相似，不同的是还要维护新节点的父节点指针，且如果是给空树插入，我们直接给根节点赋值的是红色节点，一定要改成黑色。

（2）检测新节点插入后，红黑树的性质是否造到破坏

  因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连 在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点，如果要调整，其中cur和p一定是红色的，g一定是黑色的。

情况一：u存在且为红

又能分出两种情况：

a.u位于g的右侧

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

注意：

  1.虽然p和cur违反了性质3，但是不能直接将p改为黑色，因为这样会导致黑色高度不平衡！

  2.图中情形，可能是一颗完整的树，也可能是一颗子树，如果是完整的树，g为根节点，最后要变成黑色才行；如果是子树，调整完后g是红色，所以需要继续看看g的上层节点是不是红色，因此还要继续向上调整！

  3.cur可以在p的左侧或右侧，但p节点不可能连接一个黑节点，因为会导致黑色高度不平衡。

  4.这里的cur一定是新插入的节点，如果是cur是黑色变换成红色的，说明原先的黑色高度就不平衡了，显然不成立。

b.u位于g的左侧

  解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二.u节点不存在或存在且为黑

同样以u的位置，分为两种：

a.u位于g的右侧

如果cur位于p的左侧，情景如下：

图中的虚线表示可有可无，cur节点要么是新插入的，要么是经过情况一变换的；

如果u不存在，说明cur一定是新插入的节点，否则，cur一定原先是是黑色的，这样黑色高度就不平衡了。这种情况p不可能连接黑色节点。

如果u存在且为黑，说明cur原来一定是黑色的，现在看到cur是红色的是因为经过情况一翻转颜色了。如果cur是新插入的，那么原先的黑色高度就不平衡了。这种情况的p是可以连接一个黑色节点的；

注意：cur的黑色被翻转，并不是少了一个黑色节点，而是这个黑色节点被转移到该路径的下方了，cur的节点下方还有节点，参考情况一图解；因此我们在进行调整的时候，应该保证每条路径的黑色节点个数相等即可，路径条数可以变化；

解决方式：将g节点右旋，然后g变为红，p变为黑色，无需继续向上调整；

如果cur位于p的右侧，情景如下：

（u不存在）

解决方式：先将p节点左旋，再对g节点右旋（中间和后面的图解应该将cur和p对换），然后将g改为红，p改为黑即可，无需继续向上调整；

（u存在且为黑）

b.u位于g的左侧

思路和a类似，当cur位于p的右侧，则将g左旋，再将g改为红色，cur改为黑色，无需继续调整；

当cur位于p的左侧，则先将p右旋，再将g左旋，再将g改为红色，cur改为黑色即可，无需继续调整。

最后附上插入的整体接口实现：

bool insert(const pair<K, V>& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_color = Black;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_data.first < data.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_data.first > data.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(data);
	if (parent->_data.first < data.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	//进行颜色调整
	while (parent && parent->_color == Red)
	{
		Node* grand = parent->_parent;
		Node* uncle = nullptr;
		if (parent == grand->_left)
		{
			uncle = grand->_right;
			if (uncle && uncle->_color == Red)
			{
				parent->_color = uncle->_color = Black;
				grand->_color = Red;
				cur = grand;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_left)
				{
					RotateR(grand);
					grand->_color = Red;
					parent->_color = Black;
					break;
				}
				else
				{
					RotateL(parent);
					RotateR(grand);
					cur->_color = Black;
					grand->_color = Red;
					break;
				}
			}
		}
		else
		{
			uncle = grand->_left;
			if (uncle && uncle->_color == Red)
			{
				parent->_color = uncle->_color = Black;
				grand->_color = Red;
				cur = grand;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_right)
				{
					RotateL(grand);
					grand->_color = Red;
					parent->_color = Black;
					break;
				}
				else
				{
					RotateR(parent);
					RotateL(grand);
					cur->_color = Black;
					grand->_color = Red;
					break;
				}
			}
		}
	}
	_root->_color = Black;
	return true;
}

5.红黑树与AVL树的比较

  红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追 求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红 黑树更多。

6.红黑树的代码实现：

#include <iostream>

using namespace std;
enum Color
{
	Red = 0,
	Black
};
template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _data;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>*_right;
	RBTreeNode<K, V>* _parent;
	Color _color;

	RBTreeNode(const pair<K,V> &data)
		:_data(data),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_color(Red)
	{}
};
template<class K, class V>
class RBTree
{
public:
	using Node = RBTreeNode<K, V>;
	RBTree() = default;
	RBTree(const RBTree<K,V>& t)
	{
		_root = Copy(t._root);

	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* newroot = new Node(root->_data);
		newroot->_parent = root->_parent;
		newroot->_color = root->_color;
		newroot->_left = Copy(root->_left);
		newroot->_right = Copy(root->_right);
		return newroot;


	}
	RBTree<K,V>& operator=(RBTree t)
	{
		swap(_root, t._root);
		return *this;
	}
	void inorder()
	{
		Inorder(_root);

	}
	void Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		Inorder(root->_left);
		cout << root->_data.first << ' ' << root->_data.second << endl;

		Inorder(root->_right);
	}
	bool find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_data.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}
	bool insert(const pair<K, V>& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_color = Black;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_data.first < data.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_data.first > data.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (parent->_data.first < data.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//进行颜色调整
		while (parent && parent->_color == Red)
		{
			Node* grand = parent->_parent;
			Node* uncle = nullptr;
			if (parent == grand->_left)
			{
				uncle = grand->_right;
				if (uncle && uncle->_color == Red)
				{
					parent->_color = uncle->_color = Black;
					grand->_color = Red;
					cur = grand;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grand);
						grand->_color = Red;
						parent->_color = Black;
						break;
					}
					else
					{
						RotateL(parent);
						RotateR(grand);
						cur->_color = Black;
						grand->_color = Red;
						break;
					}
				}
			}
			else
			{
				uncle = grand->_left;
				if (uncle && uncle->_color == Red)
				{
					parent->_color = uncle->_color = Black;
					grand->_color = Red;
					cur = grand;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grand);
						grand->_color = Red;
						parent->_color = Black;
						break;
					}
					else
					{
						RotateR(parent);
						RotateL(grand);
						cur->_color = Black;
						grand->_color = Red;
						break;
					}
				}
			}
		}
		_root->_color = Black;
		return true;
	}
	private:
		void RotateR(Node* parent)
		{
			Node* cur = parent->_left;
			Node* cr = cur->_right;

			parent->_left = cr;
			if (cr)
			{
				cr->_parent = parent;
			}
			Node* pparent = parent->_parent;
			cur->_right = parent;
			parent->_parent = cur;

			if (pparent == nullptr)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
				{
					pparent->_left = cur;
				}
				else
				{
					pparent->_right = cur;
				}
				cur->_parent = pparent;
			}
		}
		void RotateL(Node* parent)
		{
			Node* cur = parent->_right;
			Node* cr = cur->_left;

			parent->_right = cr;
			if (cr)
			{
				cr->_parent = parent;
			}
			Node* pparent = parent->_parent;
			cur->_left = parent;
			parent->_parent = cur;

			if (pparent == nullptr)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
				{
					pparent->_left = cur;
				}
				else
				{
					pparent->_right = cur;
				}
				cur->_parent = pparent;
			}
		}
private:
	Node* _root = nullptr;
};

# 算法 # 开发语言 # c++ # 数据结构 # 面试 # c语言
Logo
乐奇 Rokid 开放社区

更多推荐

cover

使用Rokid AIUI做了一个童年推箱子游戏

avatar 乐奇 Rokid 开放社区

基于 AIUI 框架的眼镜端坐姿监测智能体：WorkerMonitor 设计与实现

基于AIUI框架，设计并实现眼镜端坐姿监测智能体WorkerMonitor。通过加速度传感器实时采集头部姿态数据，结合校准偏移量进行三态分类（正常/警示/异常），每秒采样一次，累计时长并低打扰提醒。每2小时调用LLM生成个性化健康建议，支持自动工作/休息切换与隐藏模式，兼顾隐私与体验。项目采用Ink单文件页面结构，实现极简交互与可持续反馈，为长期伏案者提供无感式颈椎健康管理方案。

avatar 乐奇 Rokid 开放社区

FPC与机器人的双向赋能，解锁智能装备进化新势能

如果说AI算法、算力芯片是智能眼镜的“智慧大脑”，光学模组是智能眼镜的“视觉窗口”，那么FPC就是贯穿整机、连接所有功能模块的“柔性神经脉络”。方寸之间的柔性突破，破解了智能眼镜“轻薄形态”与“全能功能”的核心矛盾，是穿戴智能设备实现形态革新、体验升级的底层核心。未来，随着AR沉浸式技术、AI大模型、穿戴硬件技术的持续进化，智能眼镜将朝着更轻薄、更智能、更多场景、更高稳定性的方向持续迭代，对高端精

avatar 乐奇 Rokid 开放社区