【数据结构】红黑树

发布于：2025-05-22 ⋅ 阅读:(17) ⋅ 点赞:(0)

文章目录

1. 红黑树的概念

红黑树是一种自平衡的二叉搜索树，通过颜色标记节点和旋转维持平衡。红黑树并不会像 AVL树那样保持严格的自平衡，它的平衡严格度比较宽松，只保证了最长路径是2倍最短路径。

1.1 红黑树的特性

红黑树的五大特性：

  1. 颜色属性：每个节点为红色或黑色。
  2. 根属性：根节点必须是黑色。
  3. 叶子属性：所有叶子节点（NIL节点，空指针）视为黑色，NIL节点指的是空节点。
  4. 红色节点规则：红色节点的子节点必须为黑色（即不能有连续红色节点）。
  5. 黑高一致性：从任一节点到其所有后代NIL节点的路径上，黑色节点数量相同（称为该节点的黑高）。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

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

  • 由黑高一致性可以保证每条路径都有相同数量的黑色节点，极端场景下，最短路径全是黑色节点，设此时最短路径高度为 h。
  • 又因为不会存在连续的红色节点，那么极端场景下就是一黑一红的情况，最长路径为 2 * h。
  • 最短路径为 h， 最长路径为 2 * h，那么其他路径长度x就有 h <= x <= 2 * h。

1.3 红黑树的效率

设 N 为树中节点数量， 2h - 1 <= N < 2^2 * h^ - 1，h ≈ logN，最坏情况也就是 2 * logN，时间复杂度为O(logN)。

1.4 与AVL树的对比

特性 红黑树 AVL树
高度约束 H ≤ 2 l o g ( N + 1 ) H≤2log(N+1) H≤2log(N+1) H ≈ 1.44 l o g N H≈1.44logN H≈1.44logN
平衡严格度 宽松（最长路径<=2倍最短路径） 严格（左右子树高度差<=1）
旋转次数 较少 较多
适用场景 频繁插入/删除 频繁查询

2. 红黑树的实现

2.1 红黑树的结构

红黑树节点的结构就是在二叉搜索树节点的基础上增加一个父结点指针、一个颜色属性，颜色属性通常用枚举来表示。

enum Colour
{
	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;
	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 红黑树的插入

2.2.1 红黑树插入一个值的大概过程

  1. 按照二叉搜索树的规则进行插入，插入后对比上面五条规则
  2. 如果是空树插入，必为黑色节点。如果是非空树插入，必为红色节点，因为要维护每条路径的黑色节点数量相同，所以选择插入红色节点会便于维护。
  3. 非空树插入后，如果父节点是黑色的，那么并不会破坏规则，插入结束。
  4. 非空树插入后，如果父节点是红色的，那么就破坏了规则，就需要进行变色、旋转操作了。

下面把新增节点称为 c（cur），c 的父亲节点称为 p（parent），p 的父亲节点称为 g（grandparent），p 的兄弟节点为 u（uncle）。

下面几种情况，c 都是为红色，因为我们新插入的节点都是红色的，并且我们在向上更新时，更新后的爷爷节点如果为黑色的话，它的父亲节点无论为红还是黑都不会影响规则。所以下面的几种情况 c 都是红色。

2.2.2 情况1：p、u为红，g为黑 变色

p为红，g为黑，u存在且为红，此时将 p、u 变黑，g 变红，再把 g 当作新的 c 向上更新。

分析：p、u 从红变黑，g 从黑变红维持了 p、u 两条路径上黑色节点数量不变。但是因为我们不知道 g 的父亲节点是什么颜色的，所以需要将它当成 c 继续向上更新。如果更新到根了（根为 g 的时候会将其变红），所以还要将 g 变回黑色。

在这里插入图片描述

2.2.3 情况2：单旋 + 变色

单旋其实是 p、c 同侧的情况，如 p 是 g 的左，c 是 p 的左；p 是 g 的右，c 是 p 的右。

2.2.3.1 p、c 都在左

p 为红，g 为黑，u 不存在或存在且为黑。这种情况其实就是 g 为黑，p、u 不同时为红（记得吗，u 为 NIL 时为黑），所以我们不能像情况1 那样对 p、u 进行变黑，再对 g 变红。

分析：p 必须变黑，才能解决，连续红色节点的问题，u 不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转 + 变色。

	  g(b)
	 /  \
   p(r)  u(b)
  /
c(r)

如果 p 为 g 的左，c 为 g 的左，那么以 g 为旋转点进行右单旋，再将 p 变黑，g 变红。p 变成这棵树新的根，这样子树黑色节点的数量不变，没有连续的红色节点了，且不需要向上更新，因为 p 的父亲是红是黑都不影响规则。

	  p(b)
	 /  \
   c(r)  g(r)
  		   \
  		    u(b)

根据我画的图可以看到，原先左路径只有一个黑色节点，右路径右两个黑色节点，在旋转 + 变色之后，左路径保持一个黑色节点，右路径保持两个黑色节点。

在这里插入图片描述

2.2.3.2 p、c 都在右

如果 p 是 g 的右，c 是 g 的右，操作刚好是对称的。

	  g(b)
	 /  \
   u(b)  p(r)
 		   \
 		    c(r)

以 g 为旋转点进行左单旋，再将 p 变黑，g 变红。

	  p(b)
	 /  \
   g(r)  c(r)
  /
u(b)

2.2.4 情况3：双旋 + 变色

双旋是 == p、c 异侧==的情况，如 p 是 g 的左，c 是 p 的右；p 是 g 的右，c 是 p 的左。

2.2.4.1 p 在左，c 在右

p 为红，g 为黑，u 不存在或 u 存在且为黑。

如果 p 是 g 的左，c 是 p 的右，先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红即可。

	  g(b)
	 /  \
   p(r)  u(b)
  	\
  	 c(r)

通过上面的步骤不难看出，其实双旋是建立在单旋的基础之上的，先通过单旋将p、c 异侧转换为 p、c 同侧

以 p 为旋转点进行右单旋之后
	  g(b)
	 /  \
   c(r)  u(b)
  /
 p(r)

再通过单旋完成需求

	  c(b)
	 /  \
   p(r)  g(r)
   		   \
   		    u(b)

操作前后，所有路径的黑色节点数量不变，且最上面那个节点为黑色，不会向上更新。

在这里插入图片描述

2.2.4.2 p 在右、c 在左

如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，再把 c 变黑，g 变红即可。

	  g(b)
	 /  \
   u(b)  p(r)
  		/
  	   c(r)

同样的，这也是先通过单旋将 p、c 异侧转换成 p、c同侧

以 p 为旋转点进行右单旋
	  g(b)
	 /  \
   u(b)  c(r)
  		   \
  	   		p(r)

再通过单旋完成需求

	  c(b)
	 /  \
   g(b)  p(r)
  		   \
  	   		u(r)

2.2.5 插入总结

  • 直接变色因为是将 g 变成红色，所以需要向上更新
  • 单旋和双旋的初始颜色、旋转完成后要变的颜色都是一样的
  • 单旋和双旋只是初始位置不同，单旋是p、c同侧，双旋是p、c异侧
  • 双旋是基于单旋的，它是通过先将p、c异侧转换成p、c同侧之后再对顶部进行一次单旋得到结果
  • 单旋和双旋因为是把更新后新的 g 变黑，所以无需继续向上更新
  1. 直接变色的：
    • p 为红，g 为黑，u 存在且为红：将 p、u 变黑，g 变红，再将 g 作为新的 c 继续向上更新
  2. 单旋 + 变色：
    p 为红，g 为黑，u 不存在或存在且为黑，p、c 同侧：
    • p 为 g 的左，c 为 p 的左：以 g 为旋转点进行右单旋，再将 p 变黑，g 变红
    • p 为 g 的右，c 为 p 的右：以 g 为旋转点进行左单旋，再将 p 变黑，g 变红
  3. 双旋 + 变色
    p 为红，g 为黑，u 不存在或存在且为黑，p、c 同侧：
    • p 为 g 的左，c 为 p 的右：先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红
    • p 为 g 的右，c 为 p 的左：先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，再把 c 变黑，g 变红

对称性对比：
单旋：

特性 右旋 左旋
失衡类型 LL型 RR型
提升节点方向 左子节点上升为父节点 右子节点上升为父节点
操作做方向 顺时针方向旋转 逆时针方向旋转
颜色调整 提升的节点变黑，原父节点变红 提升的节点变黑，原父节点变红

双旋：

失衡类型 旋转顺序 颜色调整
LR型 先左旋 p，再右旋 g c 变黑，g 变红
RL型 先右旋 p，再左旋 g c 变黑，g 变红

2.3 红黑树插入代码实现

旋转部分代码除了不需要调整平衡因子之外，指针的修改和 AVL 树是完全一样的。

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			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;
		}
		else
		{
			parent->_left = cur;
		}

		// 链接父亲
		cur->_parent = parent;

		// 父亲是红色节点，出现连续红色节点，开始处理
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				//   g
				// p   u
				Node* uncle = grandfather->_right;
				// 如果叔叔节点也是红色，直接变色并继续向上调整就可以了，不需要旋转
				if (uncle && uncle->_col == RED)
				{
					// 变色
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					// 将 g 作为新的 c 继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					// 到这就该考虑 p、c 同侧还是异侧的情况了
					// p、c同侧单旋，异侧双旋

					if (cur == parent->_left)
					{
						// 同侧单旋

						//		g
						//	  p   u
						//  c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						// 异侧双旋

						//		g
						//	  p   u
						//     c
						RotateL(parent);
						RotateR(grandfather);
						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
				{
					// 还是考虑同侧异侧的问题，代码和上面刚好对称

					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;

		return true;
	}

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

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* pParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

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

			subL->_parent = pParent;
		}
	}

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

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

旋转代码不理解的去看我上一篇链接: AVL树的实现。

2.4 红黑树的查找

就是二叉搜索树的查找逻辑

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

2.5 红黑树的验证

通过以下4点一定能保证最长路径不超过最短路径两倍

  1. 枚举颜色类型，保证不是黑色就是红色
  2. 检查根节点是否为黑色
  3. 前序遍历检查孩子节点颜色不方便，因为有两个孩子节点，所以通过孩子节点检查父亲节点颜色会更方便
  4. 通过回溯算法检查每条路径上的黑色节点是否相同

在这里插入图片描述

public:
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

	bool IsBalance()
	{
		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);
	}

private:
	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->_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);
	}

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

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

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _Size(root->_left) + _Size(root->_right) + 1;
	}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布