深入解析红黑树：平衡与插入全攻略
一、红黑树的定义：
1.1、什么是红黑树？
红黑树是一种自平衡的二叉查找树，在计算机科学中广泛应用，满足以下性质：
每个节点是红色或黑色
根节点是黑色
所有叶子节点（NIL节点）是黑色
红色节点的子节点必须是黑色
从任一节点到其每个叶子的所有路径包含相同数目的黑色节点
需要注意的是，红黑树本身也是一棵二叉搜索树，所以二叉搜索树的规则红黑树也必须满足。
如上图所示，这就是一棵标准的红黑树。
1.2、关键性质详解：
黑高的概念：
什么是黑高呢？从x结点出发到叶子结点的任意路径中，黑色结点的数量称为黑高，记为BH(x)。
重要结论：
红黑树的黑高至少为h/2。
红黑树的树高最多为2log(n+1)，n为红黑树中全部结点的数量。
平衡性是如何保证的？
n>=2*bh-1
bh>h/2
所以n>=2*(h/2)-1
立即推--->h<=2log(n+1)
重点：为什么红黑树可以保证：最长路径中结点个数不会超过最短路径结点个数的二倍？
因为：
最短路径：全黑，一条路径黑色结点的数量换句话说就是等于黑高。
最长路径：一黑一红的相间的路径，也就是2*bh加上红色结点个数，因为红结点不能相邻，必须由黑结点隔开，那么红色结点的数量是<=黑色结点的数量的，那么也就是说此时最长路径，也就是黑色结点加上红色结点的数量是<=2*bh的，所以说最长路线<=2*bh，这里的bh也就是黑高，也就是最短路径，那么所以说最长路径中结点个数不会超过最短路径结点个数的二倍。
二、红黑树的插入操作：
在进行红黑树的插入之前，需要弄清一个问题：
提到红黑树的插入操作，需要注意的一点就是要插入的结点必须是红色，那么这是为什么呢？我将从多个角度来解释这个原因：
1、红黑树的黑高性质是红黑树的核心约束：
红黑树的关键规则是：从任意结点到叶子结点的所有路径中，黑色结点的数量(黑高)必须完全相同。如果直接插入黑色结点，会直接导致其所在路径的黑高+1，那么会直接破坏红黑树这个重要的规则，需要对所有路径进行调整，这个调整是全局性的（因为所有路径都要动）。
2、插入红色结点仅仅引发局部影响：
相比如插入黑色结点，插入红色结点所引起的调整仅仅只是局部性的，而插入黑色结点所需要的调整是全局性的？那么可想而知，插入红色结点会更好。
总结来说就是一句话：插入结点是红色的是以局部冲突来代替全局破坏。
红黑树的插入操作分为三种情况：
这三种情况也可以合并为两种情况，那么具体有哪三种情况，接着往下看：
在插入之前，先要弄清楚红黑树的结构：
enum Color
{
RED, BLACK
};
template<class K, class V>
class RBTreeNode
{
K _key;
V _value;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parents;
Color _col;
RBTreeNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
, _parents(nullptr)
, _col(RED)
{
}
};
template<class K, class V>
class RBTree
{
private:
RBTreeNode* _root = nullptr;
public:
typedef RBTreeNode<K, V> Node;
}变量说明：
cur:要调整的结点
parents:父结点，这里简称p。
grandparents,下面将简称g
uncle:叔叔结点，为g的两个孩子结点之一，下面简称u。
1、第一种情况：当cur为红，p结点为红，u存在且为红，g为黑。
那么此时是最容易调整的情况，但是需要注意的一点是，这里g不一定是根结点，也可能只是这一整棵树的子树。所以我们需要采用向上调整的方式，一直调整到根结点才算完成任务！
为什么说这是最简单的情况呢？因为这种情况并不需要进行旋转操作，只需要进行一个简单的变色。
把父亲结点也就是p和叔叔结点u变成黑，再把g变红即可，然后cur上移到g位置，向上继续调整就结束了。
从文字上来看或许有些抽象，那么我将画图来进行解释，方便大家理解！
第二种情况：
当cur为红的时候，p为红，g为黑，u不存在或者u存在且为黑，那么这种情况就不能仅仅使用变色了，需要使用变色+旋转。
如上图所示，当p为g的左孩子，cur为p的左孩子，那么此时要对g进行一个右单旋
若p为g的右孩子，cur为p的左孩子，那么将对g进行左单旋。
然后将p变成黑色，再把g变红就完成了。
第三种情况：
插入操作只有这三种情况，也可以说是两种情况，其他情况都可以变成这三种情况，或者说是其他情况就是这些情况的反方向。
我将分步画图来给大家看一下创建红黑树以及插入的详细过程：
这就是红黑树的构建过程，和二叉搜索树及其类似，因为红黑树本质上也是一棵二叉搜索树。
这里的旋转操作与AVL树一样，没有任何区别。所以这里就不做解释了，如果有不懂的可以看一下本博主的深入理解ALV树。https://blog.csdn.net/2501_91607282/article/details/149808998?spm=1001.2014.3001.5501
https://blog.csdn.net/2501_91607282/article/details/149808998?spm=1001.2014.3001.5501
在这篇文章中详细地讲解了旋转操作。
至于插入操作的代码实现，实际上与二叉搜索树一致，在此基础上增加了调节结点的，保证红黑树的规则。
插入操作不要被下列代码里的6种情况所吓到，因为实际上他们只是不同的方向，也就是说只有三种情况是需要认真考虑的，其他的情况只是与这三种情况换一个方向而已。
插入操作代码如下：
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parents = nullptr;
while (cur)
{
if (cur->_key < key)
{
parents = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parents = cur;
cur = cur->_left;
}
else
{
return false;//已经存在了就返回false，因为，红黑树本质也是一个二叉搜索树,二叉搜索树不允许重复。
}
}
cur = new Node(key, value);
cur->_col = RED;
if (parents->_key < key)
{
parents->_right = cur;
cur->_parents = parents;
}
else
{
parents->_left = cur;
cur->_parents = parents;
}
while (parents && parents->_col == RED)//只要父亲存在并且父亲的红色为红就继续先上调整！
{
Node* grandparents = parents->_parents;
if (parents == grandparents->_left)
{
//父亲为祖父的左
//1、第一种情况，叔叔存在且为红
Node* uncle = grandparents->_right;
if (uncle && uncle->_col == RED)
{
//叔叔存在且为空
//此时不需要旋转，只需要变色处理即可
parents->_col = uncle->_col = BLACK;
grandparents->_col = RED;
cur = grandparents;
parents = cur->_parents;
}//继续向上调整
else
{
//叔叔不存在
//第二种情况
if (cur == parents->_left)
{
//说明此时左面高，需要进行右单旋
RotateR(grandparents);
grandparents->_col = RED;
parents->_col = BLACK;
}
else
{
//第三种情况，这种 g g c
// p u --》 c u --》 p g
// c u
// p
//
//上面这种情况cur在p左面的else就说明cur在p的右面
RotateL(parents);
RotateR(grandparents);
grandparents->_col = RED;
cur->_col = BLACK;
}
break;
}
}
else
{
//这个else考虑的情况就是父亲为祖父的右
// g
// u p
// c//这种情况也可以理解为第四种情况，但实际上它的本质就是一个镜像，与上面的三种情况所对应的另一侧而已
Node* uncle = grandparents->_left;
if (uncle && uncle->_col == RED)
{
uncle->_col = parents->_col = BLACK;
grandparents->_col = RED;
cur = grandparents;
parents = cur->_parents;
}
else
{
//所谓的第五种情况 cur为红，p为红，叔叔存在且为黑
// g
// u p
// c
//对g进行左单旋 再把p变黑，g变红，c不需要处理，因为c本身就是红色
if (cur == parents->_right)
{
RotateL(grandparents);
grandparents->_col = RED;
parents->_col = BLACK;
}
else
{
//情况六 说明此时有需要双旋加变色了
// g g c
// u p --》 u c --》 g p
// c p u
RotateR(parents);
RotateL(grandparents);
cur->_col = BLACK;
grandparents->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//根结点一定是黑的（红黑树的规则）
return true;
}注释部分有的地方画出了过程，可仔细阅读，配上代码肯定能看懂。
下面是测试代码：
#include <iostream> #include "RBTree.h" using namespace std; using namespace SpaceRBTree; int main() { //// 1. 创建红黑树对象 RBTree<int, int> rbt; // 2. 测试插入操作，插入一系列节点 int testKeys[] = { 10, 20, 5, 15, 25, 3, 7 }; cout << "=== 测试插入功能 ===" << endl; for (int key : testKeys) { bool success = rbt.Insert(key, key * 10); // value 设为 key * 10 cout << "插入键值对 (" << key << ", " << key * 10 << ")：" << (success ? "成功" : "失败（已存在）") << endl; } // 3. 测试重复插入 cout << "=== 测试重复插入 ===" << endl; bool repeatSuccess = rbt.Insert(10, 100); // 重复插入键 10 cout << "重复插入键 10：" << (repeatSuccess ? "错误（不应成功插入重复键）" : "正确（拦截重复插入）") << endl; cout << endl; // 4. 测试中序遍历，验证二叉搜索树特性（中序遍历结果应为升序） cout << "=== 测试中序遍历（验证二叉搜索树升序特性） ===" << endl; cout << "中序遍历结果：" << endl; rbt.Inorder(); cout << endl; return 0; }
三、红黑树的应用：
谈起红黑树的应用，不得不提到在C++STL中，map和set的底层结构都是一棵红黑树。
思考一下，为什么我们需要红黑树？
红黑树是一棵二叉搜索树，但不是一棵普通的二叉搜索树，为什么红黑树应用如此广泛，因为与ALV树相比，红黑树所要求的并不是绝对平衡，而是大致平衡，这也是它的优点所在，它并不需要像ALV树那样频繁地进行调整，这使得红黑树在插入和删除操作时所需要的旋转次数更少，性能更加综合。
四、总结：
总结： 再次强调红黑树通过相对简单的规则和旋转操作，实现了高效的自平衡，是工程中的瑰宝。
复杂性分析： 提及插入操作的时间复杂度是O(log N)，因为最坏情况下只需要从叶子走到根，而旋转操作是常数时间O(1)。
与二叉搜索树（BST）和ALV树的对比：
特性 二叉搜索树(BST） ALV树 红黑树 平衡性 不平衡，可能退化为链表 严格平衡 弱平衡 查找效率 平均o(logn)最差O(n） o(logn),稳定最快 o(logn)，非常稳定 插入/查找效率 平均o(logn)，最差o(n) 下来较低，旋转操作频繁代价大 效率极高，旋转次数少 维护成本 无 高 低 存储开销 无 需要存储平衡因子(bf)int类型 仅需要储存1bit的颜色信息 适用场景 数据随机或一次性构建 查询密集型应用 增删频繁的综合场景
以上就是本次全部的内容，如有错误可在评论区支持，本人会及时更正。
更多推荐
28
0- 0
已为社区贡献1条内容
所有评论(0)