当前位置： 首页 > news >正文

【数据结构高阶】红黑树

news 来源：原创 2024/9/29 15:33:40

目录

一、红黑树的概念

二、红黑树的性质

2.1 红黑树与AVL树的比较

三、红黑树的实现

3.1 红黑树节点的定义

3.2 数据的插入

3.2.1 红黑树的调整思路

3.2.1.1 cur为红，f为红，g为黑，u存在且为红

3.2.1.2 cur为红，f为红，g为黑，u不存在/u存在且为黑

3.2.1.2.1 g、f、cur构成一条直线

3.2.1.2.2 g、f、cur构成一条折线

3.2.2 调整部分的代码实现

3.3 红黑树的验证

3.4 测试代码

四、红黑树实现完整代码

一、红黑树的概念

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

二、红黑树的性质

● 每个结点不是红色就是黑色

● 根节点是黑色的

● 如果一个节点是红色的，则它的两个孩子结点是黑色的（不允许出现连续的红色节点）

● 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（从根节点到每个叶子节点的空孩子路径上有相同数目的黑色节点）

● 每个叶子结点的空孩子节点都是黑色的

根据上述的五条性质，我们可以发现一个红黑树中如果有N个黑色节点，则根节点到任意一个叶子节点的距离：最短为㏒⑵N，最长为2㏒⑵N

2.1 红黑树与AVL树的比较

我们来看到下面的红黑树：

对于这棵红黑树，如果将其看成一个AVL树，是需要进行旋转的，但是在红黑树结构中却不需要

所以红黑树是近似平衡的，在搜索效率上会略逊AVL树一些，但是红黑树在结构上不要求绝对的平衡，这就造成插入相同的数据红黑树翻转的次数少于AVL树

实际使用中，在经常进行增删的场景下红黑树性能比AVL树更优，并且红黑树实现比较简单，所以实际运用中红黑树更多

三、红黑树的实现

3.1 红黑树节点的定义

enum Colour
{RED,BLACK
};template<class Key, class Val>
struct RBTreeNode
{RBTreeNode<Key, Val>* _left;RBTreeNode<Key, Val>* _right;RBTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作pair<Key, Val> _kv;Colour _col;//颜色标识RBTreeNode(const pair<Key, Val>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//构造时,优先将节点的颜色置为红色{}
};

在这里提一下为什么要默认将节点的颜色置为红色：

在我们向红黑树中插入一个新节点时，如果将该节点置为黑色，就肯定会影响红黑树性质中的第四条：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

例如：

我们现在在上面这棵树中，不管在哪个叶子节点的下方插入一个黑色的新增节点，从根节点到插入的节点的空孩子的路径上的黑色节点数目会变为4，而从根节点到其他叶子节点的空孩子的路径上的黑色节点数目会都为3

所以我们将新增节点的颜色置为红色就一定不会违反第四条红黑树性质，但是第三条呢？如果插入节点的父节点是红色的怎么办？

怎么办我们后面再说，反正总归比置为黑色一定会违反第四条性质好吧

3.2 数据的插入

由于红黑树也是平衡二叉搜索树的一种，我们在插入数据时也要找到合适的位置进行插入：

template<class Key, class Val>
class RBTree
{typedef RBTreeNode<Key, Val> Node;
public:bool Insert(const pair<Key,Val>& kv){Node* cur = _root, * parent = nullptr;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{cout << "插入的值重复" << endl;return false;}}cur = new Node(kv);cur->_parent = parent;//将插入的节点连接上二叉树if (parent == nullptr){_root = cur;}else if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}return true;}private:Node* _root = nullptr;
};

插入到合适的位置之后，我们还要检查是否破坏了红黑树的结构（由于我们插入的是红色节点，所以只会出现两个红色节点连续的情况），如果出现了该情况，我们就要对其进行分类讨论并解决：

3.2.1 红黑树的调整思路

下面我们将出现异常情况的两个节点的那个子节点叫做cur，cur的父节点叫做father（简称f），father的父节点叫做grandfather（简称g），father的兄弟节点叫做uncle（简称u）

例如：

接下来，我们分类讨论：

3.2.1.1 cur为红，f为红，g为黑，u存在且为红

下面画出的情况表示的是抽象出的情况：A、B、C、D、E都是满足构成红黑树的子树

对于这种情况我们先将f和u节点变黑，再将g节点变红即可：

调整完后，要记得再向上检查g节点的父节点是否为红色哦~（如果g节点为整棵红黑树的根，最后要将其颜色置为黑）

3.2.1.2 cur为红，f为红，g为黑，u不存在/u存在且为黑
3.2.1.2.1 g、f、cur构成一条直线

对于这种情况：若f为g的左孩子，cur为f的左孩子，则进行右单旋：

再将f变黑，g变红：

相反， f为g的右孩子，cur为f的右孩子，则进行左单旋转：

再将f变黑，g变红：

3.2.1.2.2 g、f、cur构成一条折线

f为g的左孩子，cur为f的右孩子，则做左右双旋，旋转完后将cur节点颜色置黑、g节点颜色置红：

相反， f为g的右孩子，cur为f的左孩子，则做右左双旋，旋转完后将cur节点颜色置黑、g节点颜色置红：

对于旋转操作还不熟悉的同学可以看到这里：【数据结构高阶】AVL树

3.2.2 调整部分的代码实现

template<class Key, class Val>
class RBTree
{typedef RBTreeNode<Key, Val> Node;
public:bool Insert(const pair<Key, Val>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root, * parent = nullptr;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{cout << "插入的值重复" << endl;return false;}}cur = new Node(kv);//将插入的节点连接上二叉树if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//开始调整while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点{Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红{parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新cur = grandfather;parent = cur->_parent;}elsecur为红，p为红，g为黑，u不存在/u存在且为黑{if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线{//右单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur在p的右边,p在g的左边，构成一条折线{//左右双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//调整完跳出}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红{parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新cur = grandfather;parent = cur->_parent;}elsecur为红，p为红，g为黑，u不存在/u存在且为黑{if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线{//左单旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur在p的左边,p在g的右边，构成一条折线{//右左双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//调整完跳出}}}_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑return true;
}private:void RotateL(Node* parent)//左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_right = subRL;//更新parent的右节点if (subRL)//防止该节点为空{subRL->_parent = parent;//更新subRL的父节点}parent->_parent = subR;//更新parent的父节点subR->_left = parent;//subR的左子树置为parentsubR->_parent = pparent;//更新subR的父节点if (pparent == nullptr)//旋转的是整棵树{_root = subR;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}}}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;parent->_left = subLR;//更新parent的左节点if (subLR)//防止该节点为空{subLR->_parent = parent;//更新subLR的父节点}parent->_parent = subL;//更新parent的父节点subL->_right = parent;//subL的右子树置为parentsubL->_parent = pparent;//更新subL的父节点if (pparent == nullptr)//旋转的是整棵树{_root = subL;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}}}private:Node* _root = nullptr;
};

3.3 红黑树的验证

下面我们来写段代码来验证一课树是不是红黑树：

template<class Key, class Val>
class RBTree
{typedef RBTreeNode<Key, Val> Node;
public:bool IsBalance(){if (_root && _root->_col == RED){cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}// 连续红色节点return _Check(_root, 0, benchmark);}private:bool _Check(Node* root, int blackNum, int benchmark)//计算每条路径上黑色节点的个数{if (root == nullptr){if (benchmark != blackNum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED&& root->_parent&& root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left, blackNum, benchmark)&& _Check(root->_right, blackNum, benchmark);}private:Node* _root = nullptr;
};

3.4 测试代码

void Test_RBTree()
{const size_t N = 50000;RBTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand() + i;t.Insert(make_pair(x, x));}t.InOrder();cout << t.IsBalance();
}int main()
{Test_RBTree();return 0;
}

测试效果：

四、红黑树实现完整代码

#include<iostream>using namespace std;enum Colour
{RED,BLACK
};template<class Key, class Val>
struct RBTreeNode
{RBTreeNode<Key, Val>* _left;RBTreeNode<Key, Val>* _right;RBTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作pair<Key, Val> _kv;Colour _col;//颜色标识RBTreeNode(const pair<Key, Val>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//默认构造时,优先将节点的颜色置为红色{}
};template<class Key, class Val>
class RBTree
{typedef RBTreeNode<Key, Val> Node;
public:bool Insert(const pair<Key, Val>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root, * parent = nullptr;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{cout << "插入的值重复" << endl;return false;}}cur = new Node(kv);//将插入的节点连接上二叉树if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//开始调整while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点{Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红{parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新cur = grandfather;parent = cur->_parent;}elsecur为红，p为红，g为黑，u不存在/u存在且为黑{if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线{//右单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur在p的右边,p在g的左边，构成一条折线{//左右双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//调整完跳出}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红{parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新cur = grandfather;parent = cur->_parent;}elsecur为红，p为红，g为黑，u不存在/u存在且为黑{if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线{//左单旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur在p的左边,p在g的右边，构成一条折线{//右左双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//调整完跳出}}}_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑return true;
}void InOrder()//中序遍历{_InOrder(_root);cout << endl;}bool IsBalance(){if (_root && _root->_col == RED){cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}// 连续红色节点return _Check(_root, 0, benchmark);}private:void RotateL(Node* parent)//左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_right = subRL;//更新parent的右节点if (subRL)//防止该节点为空{subRL->_parent = parent;//更新subRL的父节点}parent->_parent = subR;//更新parent的父节点subR->_left = parent;//subR的左子树置为parentsubR->_parent = pparent;//更新subR的父节点if (pparent == nullptr)//旋转的是整棵树{_root = subR;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}}}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;parent->_left = subLR;//更新parent的左节点if (subLR)//防止该节点为空{subLR->_parent = parent;//更新subLR的父节点}parent->_parent = subL;//更新parent的父节点subL->_right = parent;//subL的右子树置为parentsubL->_parent = pparent;//更新subL的父节点if (pparent == nullptr)//旋转的是整棵树{_root = subL;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}}}void _InOrder(Node* root){if (root == NULL)//如果是空树就直接结束{return;}_InOrder(root->_left);//先递归遍历其左子树cout << root->_kv.first << " ";//再遍历其根节点_InOrder(root->_right);//最后递归遍历其右子树}bool _Check(Node* root, int blackNum, int benchmark){if (root == nullptr){if (benchmark != blackNum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED&& root->_parent&& root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left, blackNum, benchmark)&& _Check(root->_right, blackNum, benchmark);}private:Node* _root = nullptr;
};

相关文章：

  • C_3练习题答案
  • 区间合并|LeetCode100136:统计好分割方案的数目
  • Flink State 状态原理解析 | 京东物流技术团队
  • 区块链媒体宣发：揭示优势与趋势，引领信息传播新时代
  • 操作系统笔记——储存系统、文件系统（王道408）
  • 智能优化算法应用：基于缎蓝园丁鸟算法3D无线传感器网络(WSN)覆盖优化 - 附代码
  • 强化学习（二）——Dueling Network（DQN改进）
  • 公务员常考应用文公文格式模板
  • 定时任务特辑 | Quartz、xxl-job、elastic-job、Cron四个定时任务框架对比，和Spring Boot集成实战
  • 定时补偿方案
  • C#图像处理OpenCV开发指南（CVStar，09）——边缘识别之Scharr算法的实例代码
  • Python----内置模块
  • php实现个性化域名(短网址)和个性化登录模版的解决方案
  • 2023-12-05 Qt学习总结3
  • LV.13 D2 开发板启动流程 学习笔记
  • Just for fun——迅速写完快速排序
  • mockjs让前端开发独立于后端
  • Mysql数据库的条件查询语句
  • 开年巨制！千人千面回放技术让你“看到”Flutter用户侧问题
  • 开源地图数据可视化库——mapnik
  • 每天10道Java面试题，跟我走，offer有！
  • 跳前端坑前，先看看这个！！
  • 写给高年级小学生看的《Bash 指南》
  • 一个6年java程序员的工作感悟，写给还在迷茫的你
  • 用 vue 组件自定义 v-model， 实现一个 Tab 组件。
  • 最简单的无缝轮播
  • ​linux启动进程的方式
  • ​一帧图像的Android之旅 :应用的首个绘制请求
  • ‌分布式计算技术与复杂算法优化：‌现代数据处理的基石
  • # Swust 12th acm 邀请赛# [ A ] A+B problem [题解]
  • #NOIP 2014# day.1 生活大爆炸版 石头剪刀布
  • #考研#计算机文化知识1（局域网及网络互联）
  • （2）从源码角度聊聊Jetpack Navigator的工作流程
  • （3）(3.5) 遥测无线电区域条例
  • （C语言）深入理解指针2之野指针与传值与传址与assert断言
  • （代码示例）使用setTimeout来延迟加载JS脚本文件
  • (回溯) LeetCode 40. 组合总和II
  • （论文阅读笔记）Network planning with deep reinforcement learning
  • （排序详解之 堆排序）
  • (三分钟了解debug)SLAM研究方向-Debug总结
  • (十三)MipMap
  • (原創) 如何將struct塞進vector? (C/C++) (STL)
  • (转)Google的Objective-C编码规范
  • (转)Mysql的优化设置
  • (转)利用ant在Mac 下自动化打包签名Android程序
  • (转)视频码率,帧率和分辨率的联系与区别
  • (转)详解PHP处理密码的几种方式
  • （转载）Linux网络编程入门
  • .htaccess配置常用技巧
  • .net core Redis 使用有序集合实现延迟队列
  • .Net CoreRabbitMQ消息存储可靠机制
  • .Net 访问电子邮箱-LumiSoft.Net，好用
  • .NET/C# 判断某个类是否是泛型类型或泛型接口的子类型
  • .Net程序帮助文档制作
  • .NET应用UI框架DevExpress XAF v24.1 - 可用性进一步增强