devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++笔记：从零开始一步步手撕高阶数据结构红黑树

作者：你好赵伟 | 2024-08-18 23:31:47

赞

踩

C++笔记：从零开始一步步手撕高阶数据结构红黑树

文章目录

红黑树概念

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

在这里插入图片描述

红黑树的性质

红黑树主要靠以下几条性质或者说规则达到高度近似平衡：

  1. 结点的颜色不是 黑色 就是 红色。
  2. 根结点的颜色是 黑色。
  3. 任意一条路径中不存在连续的红色结点。
  4. 每条路径上的黑色结点数量相同。
  5. 规定空结点才是叶子结点，叶子结点都是黑色的（主要作用：数路径）。

为什么满足以上几条规则，红黑树就能保证：最长路径的有效结点个数不超过最短路径结点个数的 2 倍，接下来举个例子证明一下：
在这里插入图片描述

红黑树 VS AVL树

  1. 平衡条件的严格性：

AVL 树要求达到的是一种左右子树高度差的绝对值不超过 1 的绝对平衡；
红黑树要求达到的是一种最长路径上的结点数不超过最短路径上的结点数的 2 倍的近似平衡。

  1. 查找的效率分析：

假设红黑树和 AVL 树都具有 N N N 个结点:

对于AVL树：高度最多达到 l o g 2 ( N + 1 ) log_2(N+1) log2​(N+1)，最坏的情况下的查找次数为 2 log ⁡ 2 ( N + 1 ) 2\log_2(N+1) 2log2​(N+1)；

对于红黑树：高度最多达到 2 log ⁡ 2 ( N + 1 ) 2\log_2(N+1) 2log2​(N+1)，最坏的情况下的查找次数为 2 log ⁡ 2 ( N + 1 ) 2\log_2(N+1) 2log2​(N+1)；

虽然从分析来看红黑树的查找效率稍差于 AVL 树，但是由于 l o g 2 ( N + 1 ) log_2(N+1) log2​(N+1) 这个数值足够小，它们之间的差异其实可以忽略不计。

举个例子来说，当 N = 10 亿 N = 10亿 N=10亿 时，AVL 树最多查找 30 次，红黑树最多也才查找 60 次，对于现代每秒钟运算上亿次的 CPU 来说，差异几乎不存在。

  1. 旋转操作的频率：

由于AVL树对平衡要求更严格，因此在插入或删除结点时可能需要更频繁地执行旋转操作来保持平衡；相比之下，红黑树对于树的平衡性有更宽松的要求，因此在实际操作中可能需要更少的旋转操作。

红黑树的结点与树的描述——定义类

// 结点的颜色
enum COLOR 
{
	RED,
	BLACK
};

// 结点类
template<class K, class V>
struct RBTreeNode 
{
	RBTreeNode(const pair<K, V>& kv)
		: _parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _color(RED)
		, _kv(kv)
	{}

	RBTreeNode *_parent;
	RBTreeNode *_left;
	RBTreeNode *_right;
	COLOR _color;
	pair<K, V> _kv;
};

template<class K, class V>
class RBTree 
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree() : _root(nullptr) {}
protected:
	Node *_root;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

【说明】

  1. 枚举类型COLOR： 用于表示红黑树结点的颜色。这样的设计是为了提高可读性，如结点->_color == RED 表示结点是红色，结点->_color == BLACK 表示结点是黑色的。
  2. RBTreeNode 结构体(类)： 用于描述红黑树结点，包含了红黑树节点的基本属性和数据。
    • _parent：指向父节点的指针。
    • _left、_right：分别指向左子节点和右子节点的指针。
    • _color：节点的颜色位，是一个枚举类型（红色或黑色）。
    • _kv：表明设计的红黑树结点中存储的数据是键值对结构。
  3. RBTree 类： 描述红黑树的结构，只包含一个指向根节点的指针成员_root，红黑树的所有操作都是在这个基础上进行的。
    • RBTree() 是红黑树的无参默认构造函数，构造一棵空的红黑树。

关于结点类，这里有一个问题：为什么新构造的结点是红色的，不能是黑色的吗？

答案是不能，因为红黑树中有这样的两条规则：“ 任意一条路径中不存在连续的红色结点。 ”、“ 每条路径上的黑色结点数量相同。 ”

由于在插入和删除操作过程中，难免会违反规则其中的一或者两条规则，但是在这两条规则中违反后者比违反前者的代价来得更大，新构造的结点是红色的在插入过程中很容易出现连续的红色结点，但是可以通过对结点的颜色重新调整或者旋转来处理，但是如果新增加黑色却很难处理，因为黑色结点的数量关乎到所有路径。

红黑树的插入操作

步骤一：按照二叉搜索树的规则插入新结点

  1. 树为空，则构造新结点，让_root 指针指向该结点，由于根结点必定是黑色的规定，将根结点的颜色置为黑，返回true。
  2. 树不空，按key的大小寻找插入位置，如果已存在，按插入失败处理，返回false。
  3. 走到空表示找到合适位置，然后插入构造的新结点，插入时要判断左边插入或者右边插入。

【步骤一部分的代码如下：】

/**
 * 函数介绍：插入一个键值对。
 *
 * 函数参数：
 *		kv: 要插入的键值对，其中第一个元素为键，第二个元素为值。
 *
 * 返回值：插入成功返回true，否则返回false。
 */
bool insert(const pair<K, V>& kv) 
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_color = BLACK;

		return true;
	}
	else
	{
		Node *parent = nullptr;
		Node *cur = _root;

		while (cur != nullptr)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 待插入kv已存在，插入失败
				return false;
			}
		}// 循环结束，构造新结点并链接

		cur = new Node(kv);

		if (parent->_kv.first < cur->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;
		
		// 检测新节点插入后，红黑树的性质是否造到破坏
		// 如果被性质被破坏要进行特殊处理
		// 步骤二的代码写在这里
		// ...
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

步骤二：检测新节点插入后，红黑树的性质是否造到破坏

新插入节点的默认颜色是红色，插入之后又可能存在两种情况：

  1. 新节点的双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整插入结束；
  2. 新插入节点的双亲节点颜色为红色，违反了不能有连续红色节点的规则，需要重新设置结点颜色；

而结点颜色具体怎么设置和 以下 4 个结点的情况有关：
在这里插入图片描述

仔细想一下，我们不难发现，cur、parent、grandparent这三个结点的颜色基本固定为红、红、黑，cur可能是新插入的结点，也有可能是从黑色变成红色的结点（为什么等下会说），所以唯一的变量就是uncle结点。

情况一：uncle存在且为红

满足情况一时不关注结点位置，只进行颜色转换处理：

  • 将parent和uncle变成黑色；
  • 将grandparent变成红色；
  • 让cur成为grandparent后重新判断；
    在这里插入图片描述

情况二：uncle不存在或者uncle存在且为黑

当遇到情况二时，单纯的颜色调整就不管用了，得旋转 + 颜色调整一起上，这里的旋转和AVL树的旋转几乎是一样的，关于旋转的部分的细节我就不多分析了，旋转的细节可以参考我之前写的《C++笔记：从零开始一步步手撕高阶数据结构AVL树》

当uncle不存在时：
在这里插入图片描述

当uncle存在且为黑时
在这里插入图片描述
综上所述：

  • parent为grandparent的左孩子时
    • cur为parent的左孩子时，右单旋，parent置黑，grandparent置红。
    • cur为parent的右孩子时，左右双旋，cur置黑，grandparent置红。
  • parent为grandparent的右孩子时
    • cur为parent的右孩子时，左单旋，parent置黑，grandparent置红。
    • cur为parent的左孩子时，右左双旋，cur置黑，grandparent置红。

【完整的红黑树插入代码如下，仅供参考】

bool insert(const pair<K, V>& kv) 
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_color = BLACK;

		return true;
	}
	else
	{
		Node *parent = nullptr;
		Node *cur = _root;

		while (cur != nullptr)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 待插入kv已存在，插入失败
				return false;
			}
		}// 循环结束，构造新结点并链接

		cur = new Node(kv);

		if (parent->_kv.first < cur->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		// 满足该条件下执行特殊处理
		while (parent && parent->_color == RED)
		{
			Node *grandparent = parent->_parent;

			if (parent == grandparent->_left)
			{
				Node *uncle = grandparent->_right;

				// 情况1：uncle存在且为RED ---> recolor(只变色处理)
				if (uncle != nullptr && uncle->_color == RED)
				{
					// recolor
					parent->_color = uncle->_color = BLACK;
					grandparent->_color = RED;

					// 继续往上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else // 情况2：uncle不存在 或者 uncle存在且为BLACK
					 // 调整颜色 + 旋转
				{
					if (cur == parent->_left)
					{
						// recolor + 右旋
						//       g
						//   p       u
						// c
						R_Rotate(grandparent);

						parent->_color = BLACK;
						grandparent->_color = RED;
					}
					else
					{
						// recolor + 左右双旋
						//       g
						//   p       u
						//     c
						L_Rotate(parent);
						R_Rotate(grandparent);

						cur->_color = BLACK;
						grandparent->_color = RED;
					}

					break;
				}
			}
			else // parent == grandparent->_right
			{
				Node *uncle = grandparent->_left;
				
				// 情况1：uncle存在且为RED ---> recolor(只变色处理)
				if (uncle != nullptr && uncle->_color == RED)
				{
					// recolor
					parent->_color = uncle->_color = BLACK;
					grandparent->_color = RED;

					// 继续往上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else // 情况2：uncle不存在 或者 uncle存在且为BLACK
				     // 调整颜色 + 旋转
				{
					if (cur == parent->_right)
					{
						// recolor + 左旋
						//       g
						//   u       p
						//             c
						L_Rotate(grandparent);

						parent->_color = BLACK;
						grandparent->_color = RED;
					}
					else
					{
						// recolor + 右左双旋
						//       g
						//   u       p
						//         c
						R_Rotate(parent);
						L_Rotate(grandparent);

						cur->_color = BLACK;
						grandparent->_color = RED;
					}

					break;
				}
			}
		}

		// parent == nullptr || parent->_color == BLACK
		// 暴力处理，根节点一定为黑色
		_root->_color = BLACK;		
		return true;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149

验证一棵红黑树是否符合规则

使用上面的插入接口构建的红黑树，我们不能保证一定就没有问题，也许过程中存在某一处违反规则的情况出现，所以这里要针对红黑树的定义和规则写一个函数来验证它是否符合规则。

红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树，即中序遍历是否为有序序列；
void _inorder(Node *root)
{
	if (root == nullptr)
		return;

	_inorder(root->_left);
	cout << root->_kv.first << endl;
	_inorder(root->_right);
}

void inorder()
{
	_inorder(_root);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  1. 检测其是否满足红黑树的性质，主要有以下三条：
    • 根结点的颜色是 黑色。
    • 任意一条路径中不存在连续的红色结点。
    • 每条路径上的黑色结点数量相同。
bool isRBTree()
{
	// 规则：根结点是黑色的
	if (_root && _root->_color == RED)
	{
		return false;
	}

	// 规则：每条路径的黑色结点数量一致 -> EqualBLACK
	int numOfBLACK = 0;
	Node *cur = _root;
	while (cur)
	{
		if (cur->_color == BLACK)
		{
			++numOfBLACK;
		}

		cur = cur->_left;
	}
	
	// 规则：不存在连续红结点 -> DiscontinuousRED
	return DiscontinuousRED(_root) && EqualBLACK(_root, 0, numOfBLACK);
}

bool DiscontinuousRED(Node *root)
{
	if (root == nullptr)
	{
		return true;
	}

	if (root->_color == RED && root->_parent->_color == RED)
	{
		return false;
	}

	return DiscontinuousRED(root->_left) && DiscontinuousRED(root->_right);
}

bool EqualBLACK(Node *root, int curPathBLACK, int &standardNumOfBALCK)
{
	if (root == nullptr)
	{
		// 走到空说明一条路径已经走完，该路径上的黑色结点数也同统计好了
		return curPathBLACK == standardNumOfBALCK;
	}

	if (root->_color == BLACK)
	{
		++curPathBLACK;
	}

	return EqualBLACK(root->_left, curPathBLACK, standardNumOfBALCK)
		&& EqualBLACK(root->_right, curPathBLACK, standardNumOfBALCK);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

【顺带一提，这是优化后的代码】

判断是否存在连续红结点的函数和判断每条路径黑色结点数量是否相同的思路相似的，完全可以二合一。

bool isRBTree()
{
	// 规则：根结点是黑色的
	if (_root && _root->_color == RED)
	{
		return false;
	}

	// 规则：每条路径的黑色结点数量一致
	int numOfBLACK = 0;
	Node *cur = _root;
	while (cur)
	{
		if (cur->_color == BLACK)
		{
			++numOfBLACK;
		}

		cur = cur->_left;
	}
	
	return Check(_root, 0, numOfBLACK);
}

bool Check(Node* root, int curPathBLACK, int& standardNumOfBALCK)
{
	if (root == nullptr)
	{
		if (curPathBLACK != standardNumOfBALCK)
		{
			// 走到空说明一条路径已经走完，该路径上的黑色结点数也同统计好了
			return false;
		}

		return true;
	}

	if (root->_color == BLACK)
	{
		++curPathBLACK;
	}

	if (root->_color == RED && root->_parent->_color == RED)
	{
		return false;
	}

	return Check(root->_left, curPathBLACK, standardNumOfBALCK)
		&& Check(root->_right, curPathBLACK, standardNumOfBALCK);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

至于红黑树的删除操作，这里留一个坑，之后有时间再填，完整的代码已经上传gitee仓库，这里是链接：https://gitee.com/ljinhao03/study-achievement/tree/master/RBTree

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/999715
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号