欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

深入理解C++系列（16）——红黑树的深度解析及模拟实现

2026-09-19 分类：服务器技术 阅读(2) 评论(0)

⭐️博主： 此生决int-@CSDN博客

 速胜派就是最大的投降派！！！

         🔥热门专栏🔥

      深入理解 C++ 系列 ｜ 算法系列

      快速复习系列 ｜ Java 速通系列

文章目录

    • 上期回顾
  • 红黑树
    • 红黑树的定义
    • 红黑树的4条规则⭐️⭐️⭐️⭐️
    • 红黑树的实现
      • 红黑树的结构
    • insert插入函数的实现
      • 找插入位置（二叉搜索树通用）
      • 颜色更新
      • 1，父亲为红</font>，叔叔存在且为红</font>！
        • 调整策略：变色
      • 2，父亲为红</font>，叔叔不存在或为黑
        • 调整策略：旋转加变色
        • 1，单旋+变色
        • 2，双旋+变色
      • 旋转函数的实现
      • insert完整代码
    • IsBalance，是否是平衡的红黑树
    • 下期预告
    • 封装map和set
    • 结语

上期回顾

上一篇我们主要学习了 AVL树的模拟实现，了解了什么是AVL树，重点学习了平衡因子的更新，左单旋，右单旋，左右双旋，右左双旋。那么，今天我们来看与AVL树类似的，也是对二叉搜索树进行的优化，但是运用更加广泛的——红黑树！

红黑树

红黑树的定义

我们想对二叉搜索树进行优化，目的就是为了避免它出现一边倒的情况（即某棵左右子树中某一棵子树特别高）。 在这里插入图片描述

那 AVL 树是通过平衡因子来完成优化的，平衡因子保证了左右子树的高度差小于等于 1。而红黑树采用了另一种方式，即给每个节点带上颜色（红和黑），通过一些特定的规则来保证树的高度趋向于 log N。

红黑树的4条规则⭐️⭐️⭐️⭐️

一，每个节点不是黑色，就是红色。 二、根节点必须为黑色。 三、红节点的孩子一定不能是红色（即不能有两个相邻的红节点），所以，红节点的孩子一定是黑色或空。 四、每条路径上的黑色节点数量相同。 对于第四点，我们需要知道，这里的路经指的是：从根节点一直走到空的路线，才会算为一条路径！ 例如： 在这里插入图片描述 根据红黑树的四条规则，我们可以得到：对于一棵拥有 N 个节点的红黑树，最短路径为h（即从根到空的最小高度），来说，他满足：2^h – 1 <= n < 2^{2h} – 1

2

h

−

1

≤

n

<

2

2

h

−

1

2^h – 1 \\leq n < 2^{2h} – 1

2h−1≤n<22h−1 所以树的高度 h 就约等于 log n 两颗极端的红黑树： 在这里插入图片描述

红黑树的实现

红黑树的结构

与 AVL 树类似，只不过把平衡因子换成了颜色color，颜色只能为黑或者红

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)
...
};

insert插入函数的实现

还是符合二叉搜索树的插入规则。前面还是一样， 1，先找到插入位置。 2，插入后，判断是否符合红黑树的四条规则。进行调整即可

找插入位置（二叉搜索树通用）

前面已经写过很多遍了，这里直接给代码：

Node* cur = _root;
Node* parent = _root;
while (cur)
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
return false;
}

颜色更新

颜色更新和AVL树哪里一样，更新完插入节点的颜色后，要继续向上更新！即cur=grandfather 首先我们要明确两个基本规则： 1，你插入的节点的颜色一定是红色的，根除外 2，插入之后你插入的节点不能说又立刻变为黑色，那不就等于插入黑色吗？ 解释：如果不插红，插黑，那玩个蛋啊？那一直插黑，整棵树都是黑色，那都不用更新了，那跟普通的二叉搜索树有什么区别？所以，插入节点一定是红色！ 我们后面的研究要用到自己（cur节点）、自己的父亲（parent）、自己的爷爷（grandfather）以及叔叔（uncle） 然后，就会出现以下几种情况：1. The parent node is black: No action needed. 2. The parent node is red: Then we need to look at the situation of the uncle node. (a) The uncle exists and is red: (b) The uncle **does not exist or is black:

1，父亲为红，叔叔存在且为红！

调整策略：变色

即：父亲和爷爷换颜色，即父亲变为黑色，爷爷变为红色。 这是插入节点时的情况： 在这里插入图片描述 还有就是向上更新，更新后，cur为红，cur的父亲也为红！

在这里插入图片描述 代码实现：

while (parent&&parent->_col==RED)//父亲为红
{
Node* grandfather = parent->_parent;
Node* uncle = nullptr;
if (parent == grandfather->_left)
{
uncle = grandfather->_right;//得到叔叔
if (uncle && uncle->_col == RED)//叔叔存在且为红
{
//仅变色
grandfather->_col = RED;
uncle->_col = BLACK;
parent->_col = BLACK;
}

2，父亲为红，叔叔不存在或为黑

调整策略：旋转加变色
1，单旋+变色

适用场景： 满足父亲为红，叔叔不存在或为黑，并且他们之间的关系是这样的，我c和父亲p的关系，和父亲p和爷爷g的关系是一样的！ 在这里插入图片描述 在这里插入图片描述 代码实现：

if (parent == grandfather->_left)//父亲是爷爷的左孩子
{
uncle = grandfather->_right;//得到叔叔
if (uncle && uncle->_col == RED)//叔叔存在且为红
...
else if (parent->_left == cur)//叔叔不存在或为黑，然后有分，我和父亲的关系和父亲和爷爷的关系是一样的，都是左孩子
{
//右单旋
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
break;
}

2，双旋+变色

与单旋的情况正好相反。这里我、父亲、叔叔和爷爷的关系为 在这里插入图片描述 这恰好和单双旋的性质是一样的！ 在这里插入图片描述 代码实现：

if (parent == grandfather->_left)//父亲是爷爷的左孩子
{
uncle = grandfather->_right;//得到叔叔
if (uncle && uncle->_col == RED)//叔叔存在且为红
...
else if (parent->_left == cur)//父亲是左，我也是左
...
else if (parent->_right == cur)//我c是父亲p的右孩子，双旋
{
//左右双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
break;
}

以上都是父亲是爷爷的左孩子的情况，另一种情况大差不差！

旋转函数的实现

这里的旋转函数和AVL树1的几乎一致，不过，不用更新平衡因子 代码：

// 右旋
void RotateR(Node* parent)
{
Node* sub = parent;
Node* subL = parent->_left;
Node* pparent = parent->_parent;
Node* subLR = subL->_right;
sub->_left = subLR;
if (subLR)subLR->_parent = sub;
subL->_right = sub;
sub->_parent = subL;
if (pparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else if (pparent->_left == sub)
{
pparent->_left = subL;
subL->_parent = pparent;
}
else if (pparent->_right == sub)
{
pparent->_right = subL;
subL->_parent = pparent;
}
else
assert(false);
}
// 左旋
void RotateL(Node* parent)
{
Node* sub = parent;
Node* subR = parent->_right;
Node* pparent = parent->_parent;
Node* subRL = subR->_left;
sub->_right = subRL;
if (subRL) subRL->_parent = sub;
subR->_left = sub;
sub->_parent = subR;
if (pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else if (pparent->_left == sub)
{
pparent->_left = subR;
subR->_parent = pparent;
}
else if (pparent->_right == sub)
{
pparent->_right = subR;
subR->_parent = pparent;
}
else
assert(false);
}

insert完整代码

// 插入
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
//依旧先找到插入位置
Node* cur = _root;
Node* parent = _root;
while (cur)
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
return false;
}
cur = new Node(kv);
//还是要根据kv来比！！！！，第三次犯这个错误了！！！
/*if (parent->_left == cur)
{
parent->_left = new Node(kv);
}
else if (parent->_right == cur)
parent->_right = new Node(kv);
else assert(false);*/
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else if (kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
assert(false);
//更新颜色
//情况一：父亲是黑是，不用处理
//情况二：父亲是红色
//1，叔叔存在，也是红色
//2，叔叔不存在，或者是黑色
//2.1单旋+变色
//2.2双旋+变色

while (parent&&parent->_col==RED)//父亲为红
{
Node* grandfather = parent->_parent;
Node* uncle = nullptr;
if (parent == grandfather->_left)//父亲是爷爷的左孩子
{
uncle = grandfather->_right;//得到叔叔
if (uncle && uncle->_col == RED)//叔叔存在且为红
{
//仅变色
grandfather->_col = RED;
uncle->_col = BLACK;
parent->_col = BLACK;
}
else if (parent->_left == cur) // 叔叔不存在或为黑，然后有分，我和父亲的关系和父亲和爷爷的关系是一样的，都是左孩子
{
//右单旋
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
else if (parent->_right == cur)//我c是父亲p的右孩子，双旋
{
//左右双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
break;
}
else
assert(false);

}
else if (parent == grandfather->_right)
{
uncle = grandfather->_left;

if (uncle && uncle->_col == RED)
{
//仅变色
grandfather->_col = RED;
uncle->_col = BLACK;
parent->_col = BLACK;
}
else if (parent->_right == cur)//uncle存在与否已经不重要了
{
//左单旋
RotateL(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
else if (parent->_left == cur)
{
//右左双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
break;
}
else
assert(false);
}
else
assert(false);
//继续更新
cur = grandfather;
parent = cur->_parent;
}
//根一定是黑，最后统一处理，
_root->_col = BLACK;
return true;

}

IsBalance，是否是平衡的红黑树

检查一棵树是否是红黑树，只需要看它是否满足红黑树的四个规则。第一和第二规则很显然，我们用宏定义了红和黑两种颜色，并且插入后都对根进行了变色，强制变为黑，不用测试，只需要验证它是否满足第三和第四个规则即可。 第三个规则，我们只需要前序遍历一棵树。如果是红节点，那我们只需要看他的父亲是否为红节点即可。 第四个规则，我们可以先走出一条路，得到那条路径上黑色节点的数量。 然后进行递归：用一个递归来统计走到空节点时，路径上的黑色节点数量是否等于我们最开始统计的那个数值。

代码如下：

// 检查红黑树是否平衡
bool IsBalance()
{
if (_root == nullptr)return true;
Node* cur = _root;
int refnum = 0;
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)
{
//满足四条规则：
//1,2，肯定不用看，
//3，所有的红节点的父亲是不是红色
//4，路径黑色是不是一样多
//前序遍历
if (root == nullptr)
{
if (blackNum != refNum)
return false;
else
return true;
}
if (root->_col == BLACK)blackNum++;
if (root->_col == RED)
{
if (root->_parent&&root->_parent->_col == RED)
return false;
else if (root->_parent == nullptr)
{
if (root->_col == RED)
{
cout << "根节点为红色！！" << endl;
return false;
}
}
}

return Check(root->_left,blackNum,refNum) && Check(root->_right, blackNum, refNum);
}

下期预告

封装map和set

结语

  本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。   也欢迎订阅我的 深入理解 C++系列：从语法入门到底层原理，系统掌握现代 C++ 算法系列：从入门到精通，蓝桥杯、ACM、LeetCode 与面试算法全路线 快速复习系列：知识梳理、查漏补缺，考前冲刺必备 Java 速通系列：已学 C 语言，快速上手 Java，轻松备战期末考试

  愿每一次敲下键盘，都比昨天更进一步！

  愿每一行代码落下，都让未来多一种可能！

赞(0)
未经允许不得转载：171主机测评 » 深入理解C++系列（16）——红黑树的深度解析及模拟实现
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(60883)#python(20523)#开发语言(17162)#java(15747)#运维(15608)#linux(15141)#大数据(14804)#服务器(13244)#算法(11909)#前端(11132)#网络(9553)#ai(9265)#数据库(9060)#c++(8293)#学习(6914)#课程设计(6890)#机器学习(6805)#区块链(5968)#OpenClaw(5400)#后端(5247)#spring boot(5076)#深度学习(5035)#c语言(4418)#毕业设计(4330)#数据结构(4234)#安全(4229)#docker(3978)#架构(3971)#javascript(3864)#大模型(3737)

热门文章

最新文章

归档

分类