技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

红黑树-我与C的不解之缘二十五

 收录于 C
   约 3494 字   预计阅读 7 分钟 
https://bing.ee123.net/img/rand?artid=146286854

【红黑树】—— 我与C++的不解之缘（二十五）

前言

学习了 avl 树，现在来学习 红黑树 。

一、什么是红黑树

红黑树是一颗平衡二叉搜索树，它每一个节点增加了一个存储位表示节点的颜色，可以是红色或者黑色。

相比较于 AVL 树， 红黑树 也是一个自平衡二叉搜索树，但是它与 AVL 树控制平衡的方式不同；

  • AVL 是通过平衡因子来控制整个树的平衡
  • 红黑树 则是通过节点的颜色 红/黑 来控制整个树的平衡

这里红黑树通过对 任何一条从根到叶子的路径上每一个节点的颜色 的约束，从而确保最长路径不会超过最短路径的 2 倍，因此让整个树保证平衡。

红黑树的规则

红黑树遵循以下几条规则：

  • 每一个节点的颜色不是 RED/红色 就是 BLACE/黑色 。
  • 根节点的颜色为 BLACK 。
  • 如果一个节点是红色的，那么它的孩子节点就一定是黑色的；也就是在任意一条路径中不会出现连续的红色节点。
  • 对任何一个节点，从这个节点到其所有的 NULL 的简单路径上，均包含相同数量的黑色节点。

这里在 《算法导论》 和 《STL源码剖析》 书籍中，存在这样的一条定义 每个叶子节点NIL都是黑色 ；

注意：这里说的并不是我们认为的叶子节点，而是 NULL 节点；

https://i-blog.csdnimg.cn/direct/76878c394c27445ba6e4bb8353266033.png#pic_center

有了 NIL 节点我们就可以十分清楚的看出来所有的 路径 。

为什么红黑树能确保最长路径不超过最短路径的 2 倍

  • 根据规则4，从根节点到 NULL 节点每条路径都存在相同数量的黑色节点；所以这里假设一下极端情况：最短路径下全是黑色节点，长度为 bh ，那么黑色节点的个数也是 bh 。
  • 根据规则3，任何一条路径下不会存在连续的红色节点，那极端情况下，最长路径就是由 一黑一红 组成的，那最长路径的长度为 2*bh ，黑色节点个数是 bh 。
  • 然而极端情况并不是在每一个红黑树中都存在的；假设从根节点到 NULL 的一条路径长度为 h ，那就存在 bh <= h <= 2*bh 。

https://i-blog.csdnimg.cn/direct/90fddcd18d134d3aa35e7422ed84d1ae.png#pic_center

红黑树的效率

对于红黑树，确实控制了平衡，但是它的查找效率如何呢？

这里假设红黑树的节点个数为 n ， h 是最短路径的长度；那我们就可以得出红黑树最坏情况是走最长路径，时间复杂度就是O(log N)

虽然说红黑树相对于 AVL 树的效率较差一点，但是它的效率还是 O(log N)

  • AVL 树通过高度来严格控制了整个树的平衡
  • 而 红黑树 就通过了四条规则，控制树中节点的颜色来控制这个树的相对平衡。

二、红黑树的结构

说了这么多，现在来看一下红黑树的结构

红黑树首先是一个 三叉链 结构，还要存放 pair<K,V> ，和颜色 Color

这里颜色使用枚举变量来表示

enum Color
{
	RED,
	BLACK,
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair<K, V> _kv;
	Color _col;

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

三、红黑树的插入

了解了红黑树节点的结果，现在来看红黑树的插入节点

插入一个值，我们需要按照`二叉搜索树的结构来进行插入，插入之后来判断是否满足红黑树的规则

这里 AVL 在找到插入位置并插入节点后做的是更新平衡因子；

而红黑树则是进行循环操作（ 变色 、 旋转 + 变色1 等），直到其父节点不存在（遍历到 _root )或者父节点颜色为 BLACK 。

首先就是插入节点的颜色

  • 如果是空树插入，新增节点为黑色；
  • 那如果是非空树的插入节点，新增节点就必须是红色
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree() {};
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//空树插入
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		//非空树插入
		Node* tail = _root;
		Node* parent = nullptr;
		while (tail)
		{
			if (kv.first > tail->_kv.first)
			{
				parent = tail;
				tail = tail->_right;
			}
			else if (kv.first < tail->_kv.first)
			{
				parent = tail;
				tail = tail->_left;
			}
			else
			{
				return false;
			}
		}
		Node* cur = new Node(kv);
		cur->_col = RED;//新插入节点一定是红色
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else if (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		//进行不满足规则的一系列处理
	}
private:
	Node* _root;
};

这里如果新增节点是黑色，那就一定破坏了规则四（因为插入之前是符合条件的红黑树）。

如果我们插入红色节点，其父节点为黑色就不需要做任何调整；

如果父节点是红色，这时违反了规则三，我们需要进一步分析

  • 此时其父节点 p 为红色，那祖父节点 g 就一定为黑色；而叔节点 uncle 颜色并不确定

    这时 c 插入节点， p 父节点， g 祖父节点颜色都是固定的，这种情况下我们来看 u 叔节点

我们根据 u 节点的颜色可以分为三种情况

1. 情况一： 变色

在上述中，我们已经确定了 c 、 p 、 g 的颜色，现在我们现在唯一不能确定的就是 u 节点；

如果 u 节点存在，且 u 节点的颜色为红色，如下图所示

https://i-blog.csdnimg.cn/direct/1cce0a74d08f471f845a9e563266e86e.png#pic_center

对于这种情况， u 存在且为红色；通过观察我们可以发现：

g 节点的黑色节点影响的路径是其左右子树 p 和 u 的路径，那我们将 p 和 u 变成黑色、 g 变成红色

变化之后可以发现，从 g 节点到 NULL 节点的路径上的黑色几点并没有发生变化。

这里有些问题：

  1. 在上述图中， g 的父节点为黑色，那如果 g 的父节点为红色呢？

这就好说了，将 g 赋值给 c ，继续执行循环即可。

  1. 那现在存在一个问题，如果在向上变色的过程中， g 为根节点怎么办？

这里在执行完循环过后，直接把 _root 的颜色修改为黑即可。

  1. 如果在执行向上变色的过程中遇到 u 不存在或者 u 存在但其颜色为 黑 怎么办？

接着往下看情况二：

2. 情况二：单选 + 变色

如果我们在向上执行变色的过程中，遇到了 u 不存在或者 u 存在但它的颜色为 黑 ；

这时我们就不能只变色来解决问题了。

https://i-blog.csdnimg.cn/direct/15b90921e3f34985bfb6a747ab5e47da.png#pic_center

这种情况下，我们就需要进行一次单旋，再进行变色才能解决问题

https://i-blog.csdnimg.cn/direct/26c01029f12c4c169b880b0d6f705718.png#pic_center

https://i-blog.csdnimg.cn/direct/af04a103d39444c3992d58d60820002d.png#pic_center

根据上图可以看到，右单旋的条件是 c = p->_left && u==g->_right

这里都是右单旋的问题，左单旋是以下情况，就不做分析了。

https://i-blog.csdnimg.cn/direct/97d60f2b079b404fa4644f01472f0b5e.png#pic_center

进行右单旋加变色的条件是 c = p->_right && u==g->_left

3. 情况三： 双旋 + 变色

在上述过程中，只有单旋，那如果单旋解决不了问题呢？

如下图所示：

https://i-blog.csdnimg.cn/direct/64606d7396d544038579c677b1d475bd.png#pic_center

如果我们在 p 的这个位置插入（或者有 g 向上更新变化过来的 c ）

这时就不能就进行单旋了，就像 AVL 中平衡因中一样，如果进行了单旋就会发现把问题变得更加复杂了。

这是要进行左右双旋转

先以 p 节点进行一次左单旋，再以 g 节点进行一下右单旋。

https://i-blog.csdnimg.cn/direct/f11364187bbb412580a4306fa5d40902.png#pic_center

https://i-blog.csdnimg.cn/direct/9f0b85b86e2b49f989f7d0682326151b.png#pic_center

当然，存在左右双旋的情况，也存在右左双旋的情况，如下图所示（这里就不推理了）

https://i-blog.csdnimg.cn/direct/9582ab374d854ba5be4a262661278b30.png#pic_center

插入代码实现：

有了上述情况分析，现在来实现 红黑树 插入的代码：

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree() {};
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//空树插入
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		//非空树插入
		Node* tail = _root;
		Node* parent = nullptr;
		while (tail)
		{
			if (kv.first > tail->_kv.first)
			{
				parent = tail;
				tail = tail->_right;
			}
			else if (kv.first < tail->_kv.first)
			{
				parent = tail;
				tail = tail->_left;
			}
			else
			{
				return false;
			}
		}
		Node* cur = new Node(kv);
		cur->_col = RED;//新插入节点一定是红色
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else if (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		//这里当父节点存在且为红色时就一直循环
		//直到父节点不存在或者父节点的颜色为黑色
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//   g
			// p   u
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//叔节点的颜色为红色
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)
				{
					if (cur == parent->_left)
					{
						//    g
						//  p   u
						//c
						//右单旋+变色
						RevoleR(parent);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (cur == parent->_right)
					{
						//    g
						//  p   u
						//   c
						//先左单旋，再右单旋，再变色
						RevoleL(parent);
						RevoleR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
				}
				else if (uncle == grandfather->_left)
				{
					//   g
					// u  p
					if (uncle && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else if (uncle == nullptr || uncle->_col == BLACK)
					{
						if (cur == parent->_right)
						{
							//   g
							// u   p
							//       c
							//左单旋+变色
							RevoleL(parent);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else if (cur == parent->_left)
						{
							//   g
							// u   p
							//    c
							//先右单旋，再左单旋，再变色
							RevoleR(parent);
							RevoleL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
					}
				}
			}
		}
		_root->_col = BLACK;
	}
private:
	void RevoleR(Node* parent) //右单旋
	{
		Node* subl = parent->_left;
		Node* sublr = parent->_left->_right;

		parent->_left = sublr;
		if (sublr)
			sublr->_parent = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subl;
		subl->_parent = ppNode;
		if (ppNode == nullptr)
		{
			_root = subl;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subl;
			}
			else if (parent->_right)
			{
				ppNode->_right = subl;
			}
		}
	}
	void RevoleL(Node* parent)//左单旋
	{
		Node* subr = parent->_right;
		Node* subrl = parent->_right->_left;
		
		parent->_right = subrl;
		if (subrl)
			subrl->_parent = parent;

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

四、红黑树的查找

红黑树依旧是一个 搜索二叉树 ，它的查找效率仍旧是 log N ；比 AVL 略微差一点。

	bool find(const pair<K, V>& kx)
	{
		Node* tail = _root;
		while (tail)
		{
			if (kv.first > tail->_kv.first)
			{
				tail = tail->_right;
			}
			else if (kv.first < tail->_kv.first)
			{
				tail = tail->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

四、红黑树的查找

红黑树依旧是一个 搜索二叉树 ，它的查找效率仍旧是 log N ；比 AVL 略微差一点。

	bool find(const pair<K, V>& kx)
	{
		Node* tail = _root;
		while (tail)
		{
			if (kv.first > tail->_kv.first)
			{
				tail = tail->_right;
			}
			else if (kv.first < tail->_kv.first)
			{
				tail = tail->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

五、红黑树验证

说了这么多，现在来看一下如何验证一个树是不是红黑树。

首先去检查最长路经和最短路径是不可行的，因为如果满足最长路径不超过最短路径的 2 倍，但是颜色也可能不满足规则。

也也能存在问题；

所以我们需要去检查红黑树的四条规则

  • 对于规则一，我们使用枚举常量，就保证了颜色不是黑色就是红色。
  • 规则二，直接检查跟节点颜色即可。
  • 规则三，使用前序遍历检查，遇到红色节点（可能不存在孩子节点，有可能存在一个/两个），非常不方便；这里可以反过来检查，遇到红色节点检查其父节点即可。
  • 规则四，在遍历的过程中，用形参来记录根节点到当前节点的 BLACK_num （黑色节点个数），前序遍历遇到黑色节点就 ++BLACK_num ，遍历到空就计算出了一条路径的黑色节点个数，再将任一条路径黑色节点个数作为参考值，依次比较即可。

六、红黑树的删除

对于红黑树的删除，这里暂时不做讨论，等以后再深入研究。

感兴趣的可以参考书籍 《算法导论》 和 《STL源码剖析》 。

到这里本篇内容就结束了，希望对你有所帮助。

制作不易，感谢大佬的支持。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

更新于 2025-03-15
 开发语言, Stl, Rb, C
返回 | 主页