红黑树：高效平衡二叉树的奥秘

🌟 快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。🌟

在这里插入图片描述

引言

在数据结构的奇妙世界里🧐，二叉搜索树就像一把神奇的钥匙，能高效地查找数据。但这把钥匙也有“失灵”的时候，普通二叉搜索树在某些极端情况下，会像没了骨架的软体动物，退化成链表，性能那叫一个“惨不忍睹”😫。为了解决这个麻烦，平衡二叉树闪亮登场✨，而红黑树就是其中的“明星选手”🌟。

今天，咱们就结合实际代码，深入探索红黑树的奥秘，看看它是如何做到高效平衡的吧😜。

红黑树的概念

红黑树呀，其实就是一种特殊的二叉搜索树🎄。它给每个节点都配上了一个“小标签”🏷️，用来表示节点的颜色，颜色就两种选择：红色（Red）或者黑色（Black）。通过巧妙地给从根节点到叶子节点路径上的各个节点安排颜色，红黑树就像一个严格的纪律委员，确保没有一条路径会比其他路径长出两倍，这样就实现了接近平衡的状态啦🤗。这种平衡特性，让红黑树在增删改查操作时，都能保持较高的效率，是不是很厉害👍？
在这里插入图片描述

红黑树的性质

节点颜色大揭秘：每个节点要么是热情似火的红色，要么是沉稳低调的黑色，没有其他选择哦😏。
根节点的“特殊待遇”：根节点永远是黑色的，就像班级里的班长，有着独特的身份象征🖤。
红色节点的“小规矩”：要是一个节点是红色的，那它的两个孩子节点必定得是黑色，这就好比是一种“家族规定”，有效避免了红色节点连续出现，防止“红色泛滥”🧐。
黑色节点数量的“神秘守恒”：对于每个节点来说，从它出发到所有后代叶节点的简单路径上，黑色节点的数量始终是一样的。这就像是隐藏在树中的一个神秘规律，保证了树的大致平衡性🎯。
叶子节点的“统一着装”：这里说的叶子节点其实就是空节点啦，它们都统一穿着“黑色的衣服”，规规矩矩的😃。

性质保证平衡性的原理

大家可能会好奇🤔，为啥满足这些性质，红黑树就能保证最长路径节点个数不超过最短路径节点个数的两倍呢🧐？这是因为呀，每条路径上黑色节点的数量是相同的，最长路径可能是红黑交替排列，而最短路径全是黑色节点。在最长路径里，红色节点最多和黑色节点数量一样，所以最长路径节点个数自然不会超过最短路径节点个数的两倍啦，是不是很好理解😎？

红黑树节点的定义与结构

节点定义

// 定义节点的颜色枚举，就像给节点准备了两种颜色的衣服选择
enum Colour
{RED,BLACK
};// 红黑树节点的模板类，可存储键值对
template<class K, class V>
class RBTreeNode
{
public:// 构造函数，接收一个键值对作为参数，初始化节点信息// 节点默认颜色为红色，因为插入红色节点在多数情况下不会破坏红黑树性质RBTreeNode(const pair<K, V>& kv) : _kv(kv),_left(nullptr), // 左孩子指针初始化为空_right(nullptr), // 右孩子指针初始化为空_parent(nullptr), // 父节点指针初始化为空_col(RED) // 节点颜色初始化为红色{}RBTreeNode<K, V>* _left; // 指向左孩子节点的指针RBTreeNode<K, V>* _right; // 指向右孩子节点的指针RBTreeNode<K, V>* _parent; // 指向父节点的指针Colour _col; // 节点的颜色pair<K, V> _kv; // 存储的键值对
};

在定义节点的时候，为啥要把默认颜色设为红色呢🧐？这是因为新节点插入时，如果它的双亲节点是黑色，那就不会违反红黑树的性质，也就不需要调整啦。要是双亲是红色，才需要调整，这样设置能减少一开始就需要调整的可能性，是不是很机智😜？
在这里插入图片描述

结构设计

在下面的红黑树类中，只维护了一个根节点指针 _root，通过这个指针可以访问整个红黑树的节点。后续的插入、旋转等操作也都是围绕这个根节点展开的。

template<class K, class V>
class RBTree
{
public:typedef RBTreeNode<K, V> Node; // 为节点类定义一个别名，方便后续使用// 插入操作，向红黑树中插入一个键值对bool insert(const std::pair<K, V>& key){// 如果根节点为空，说明树为空，直接创建一个新节点作为根节点if (_root == nullptr){_root = new Node(key);// 根节点颜色必须为黑色_root->_col = BLACK; return true;}Node* cur = _root; // 从根节点开始查找插入位置Node* parent = nullptr; // 记录当前节点的父节点// 遍历树，找到合适的插入位置while (cur){parent = cur; // 更新父节点if ((cur->_kv).first < key.first){cur = cur->_right; // 键值比当前节点大，向右子树查找}else if ((cur->_kv).first > key.first){cur = cur->_left; // 键值比当前节点小，向左子树查找}else{return false; // 键值已存在，插入失败}}// 新增节点，颜色为红色cur = new Node(key); cur->_parent = parent; // 设置新节点的父节点// 根据键值大小，将新节点插入到父节点的左或右子树if ((parent->_kv).first < (cur->_kv).first){parent->_right = cur;}else{parent->_left = cur;}// 如果父节点存在且为红色，需要调整树结构以满足红黑树性质while (parent && parent->_col == RED){// 找到祖父节点Node* grandfather = parent->_parent; Node* uncle = nullptr;// 根据父节点是祖父节点的左孩子还是右孩子，确定叔叔节点if (parent == grandfather->_left){uncle = grandfather->_right;}else{uncle = grandfather->_left;}// 情况一：叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父亲和叔叔节点变黑，爷爷节点变红parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续向上更新，将祖父节点作为当前节点，其父节点作为父节点cur = grandfather; parent = grandfather->_parent; }else // 叔叔节点不存在或存在且为黑{if (parent == grandfather->_left && cur == parent->_left){// 右单旋RotateR(grandfather); // 变色，父亲变黑，爷爷变红parent->_col = BLACK; grandfather->_col = RED; }else if (parent == grandfather->_right && cur == parent->_right){// 左单旋RotateL(grandfather); // 变色，父亲变黑，爷爷变红parent->_col = BLACK; grandfather->_col = RED; }else if (parent == grandfather->_left && cur == parent->_right){// 先左后右双旋RotateLR(grandfather); // 变色，当前节点变黑，爷爷变红cur->_col = BLACK; grandfather->_col = RED; }else if (parent == grandfather->_right && cur == parent->_left){// 先右后左双旋RotateRL(grandfather); // 变色，当前节点变黑，爷爷变红cur->_col = BLACK; grandfather->_col = RED; }}}// 确保根节点颜色为黑色_root->_col = BLACK; return true;}// 中序遍历打印红黑树void printTree() const {inorderPrint(_root);std::cout << std::endl;}
private:Node* _root = nullptr; // 红黑树的根节点// 左单旋操作，用于调整树的结构void RotateL(Node* parent) {Node* subR = parent->_right; // 父节点的右孩子Node* subRL = subR->_left; // 父节点右孩子的左孩子parent->_right = subRL; // 将父节点的右孩子更新为 subRLif (subRL){subRL->_parent = parent; // 如果 subRL 不为空，更新其父亲节点为父节点}subR->_left = parent; // 将 subR 的左孩子更新为父节点Node* parentParent = parent->_parent; // 父节点的父亲节点parent->_parent = subR; // 更新父节点的父亲节点为 subRif (parentParent == nullptr){_root = subR; // 如果父节点的父亲节点为空，说明父节点是根节点，更新根节点为 subRsubR->_parent = nullptr; // subR 成为新的根节点，其父节点为空}else{if (parentParent->_left == parent){parentParent->_left = subR; // 如果父节点是其父节点的左孩子，更新左孩子为 subR}else{parentParent->_right = subR; // 如果父节点是其父节点的右孩子，更新右孩子为 subR}subR->_parent = parentParent; // 更新 subR 的父节点为原父节点的父节点}}// 右单旋操作，用于调整树的结构void RotateR(Node* parent) {Node* subL = parent->_left; // 父节点的左孩子Node* subLR = subL->_right; // 父节点左孩子的右孩子parent->_left = subL->_right; // 将父节点的左孩子更新为 subLRif (subLR){subLR->_parent = parent; // 如果 subLR 不为空，更新其父亲节点为父节点}subL->_right = parent; // 将 subL 的右孩子更新为父节点Node* parentParent = parent->_parent; // 父节点的父亲节点parent->_parent = subL; // 更新父节点的父亲节点为 subLif (parentParent == nullptr){_root = subL; // 如果父节点的父亲节点为空，说明父节点是根节点，更新根节点为 subLsubL->_parent = nullptr; // subL 成为新的根节点，其父节点为空}else{if (parentParent->_left == parent){parentParent->_left = subL; // 如果父节点是其父节点的左孩子，更新左孩子为 subL}else{parentParent->_right = subL; // 如果父节点是其父节点的右孩子，更新右孩子为 subL}subL->_parent = parentParent; // 更新 subL 的父节点为原父节点的父节点}}// 先右后左双旋操作void RotateRL(Node* parent){// 先对父节点的右孩子进行右单旋RotateR(parent->_right); // 再对父节点进行左单旋RotateL(parent); }// 先左后右双旋操作void RotateLR(Node* parent){// 先对父节点的左孩子进行左单旋RotateL(parent->_left); // 再对父节点进行右单旋RotateR(parent); }// 中序遍历递归函数，用于打印红黑树的节点信息void inorderPrint(Node* node) const {if (node) {// 递归遍历左子树inorderPrint(node->_left); std::cout << "Key: " << node->_kv.first << ", Value: " << node->_kv.second << ", Color: ";if (node->_col == Colour::RED) {std::cout << "RED";}else {std::cout << "BLACK";}std::cout << std::endl;// 递归遍历右子树inorderPrint(node->_right); }}
};

红黑树的插入操作

红黑树的插入就像一场精心编排的舞蹈，分两个关键步骤进行💃🕺：

按照二叉搜索树规则插入新节点：首先，要根据二叉搜索树的特性，把新节点安插到合适的位置，就像给新同学找到合适的座位一样🧐。在代码中，通过 insert 函数实现了这个过程，先找到合适的插入位置，再创建新节点并插入到树中。!](https://i-blog.csdnimg.cn/direct/9a824900228743099dbf53880fd7bc21.png)
检测新节点插入后红黑树性质是否被破坏：因为新节点默认是红色的，如果它的双亲节点是黑色，那就万事大吉，红黑树的性质没有被破坏🎉。但要是双亲节点也是红色，那就违反了“不能有连在一起的红色节点”这个性质，这时候就得分情况来讨论啦🧐：
- 情况一：cur 是红色，p 是红色，g 是黑色，u 存在并且也是红色。这时候的解决办法就是把 p 和 u 都变成黑色，g 变成红色，然后把 g 当成 cur，继续向上调整，就像在调整一个复杂的拼图🧩。
- 情况二：cur 是红色，p 是红色，g 是黑色，u 不存在或者 u 存在但为黑色。如果 p 是 g 的左孩子，cur 是 p 的左孩子，那就来个右单旋转；要是 p 是 g 的右孩子，cur 是 p 的右孩子，那就来个左单旋转。旋转完后，p 和 g 还要变变色，p 变黑，g 变红，就像给它们换了身衣服😃。
- 情况三：cur 是红色，p 是红色，g 是黑色，u 不存在或者 u 存在但为黑色。如果 p 是 g 的左孩子，cur 是 p 的右孩子，那就针对 p 来个左单旋转；要是 p 是 g 的右孩子，cur 是 p 的左孩子，那就针对 p 来个右单旋转，转完之后就变成情况二啦，是不是很神奇😎？

红黑树的验证

虽然代码中没有给出红黑树验证的具体实现，但验证过程通常包括两个方面：

检测是否满足二叉搜索树：通过中序遍历这棵树，如果得到的结果是有序的序列，那就说明它满足二叉搜索树的特性，就像学生考试答对了这道题一样🎉。
检测是否满足红黑树的性质：检查根节点是否为黑色，是否存在连续的红色节点，以及每条路径上的黑色节点数量是否相同等。

红黑树的删除

哎呀，红黑树的删除操作有点复杂，代码中没有涉及，这篇文章也先不详细讲啦😅。要是你对它特别感兴趣，可以去参考《算法导论》《STL源码剖析》这些厉害的书籍，或者看看这个网页http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html，里面有更详细的介绍哦🧐。

红黑树与AVL树的比较

红黑树和AVL树都是数据结构里的“尖子生”，它们都是高效的平衡二叉树，在增删改查操作上的时间复杂度都是 $O(log_2 N)$ 。不过呢，红黑树不像AVL树那样追求绝对的平衡，它只要保证最长路径不超过最短路径的2倍就行啦。这样一来，红黑树在插入和旋转的次数上就相对少一些，在那些经常要进行增删操作的结构里，它的性能就比AVL树更胜一筹啦👍。而且红黑树实现起来也比较简单，所以在实际应用中，红黑树出现的频率更高，更受大家的欢迎呢😎。

红黑树的应用

C++ STL库：在C++的标准模板库里，map、set、mutil_map、mutil_set 这些关联式容器，都是靠着红黑树来实现的。红黑树的高效平衡特性，让这些容器在存储和查找元素的时候，就像装上了小马达，速度超快，性能超棒🎉。

其他领域：红黑树还在操作系统、数据库索引等好多领域都发挥着重要作用，就像一个无所不能的小助手，帮助这些系统高效地组织和访问数据🧐。例如，在操作系统的进程调度中，红黑树可以用来管理进程的优先级队列，通过快速的插入、删除和查找操作，确保系统能够高效地分配资源。在数据库索引中，红黑树能够加速数据的检索，提高查询效率，使得数据库能够快速响应用户的请求。