C++高阶：红黑树实现

news/2024/10/21 9:52:22/

目录

一.红黑树的概念

1.1红黑树的规则

1.2红黑树的效率

二.红黑树的实现

2.1红黑树的结构

 2.2红黑树的插入

2.2.1插入的大致过程

2.2.2情况一：变色

​编辑 2.2.3情况二：单旋+变色

 2.2.4情况三：双旋+变色

 2.3插入代码实现

2.4红黑树的查找

2.5红黑树的验证

一.红黑树的概念

红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

1.1红黑树的规则

1. 每个结点不是红色就是黑色

2. 根结点是黑色的

3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。

4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点

就像是这样： 

• 由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就就是全是黑色结点的路径，假设最短路径长度为bh(black  height)。

• 由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为2*bh。

• 综合红黑树的4点规则而言，理论上的全黑最短路径和一黑⼀红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x，那么bh<=h<=2*bh。

1.2红黑树的效率

假设N是红黑树树中结点数量，h最短路径的长度，那么2^h − 1 <= N < 2^2∗h − 1 ,由此推出h ≈ logN 2 ∗ logN。 也就是意味着红黑树增删查改最坏也就是走最长路径 ，那么时间复杂度还是 O(logN) 。

红黑树的表达相对AVL树要抽象⼀些，AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

二.红黑树的实现

2.1红黑树的结构

这里用枚举表示颜色。

enum Colour
{RED,BLACK
};
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;RETreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr),_parent(nullptr){}
};
template<class K,class V>
class BRTree
{typedef RBTreeNode<K, V> Node
private:Node* _root = nullptr;
};

 2.2红黑树的插入

2.2.1插入的大致过程

1. 插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的4条规则。

2. 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4是很难维护的。

3. 非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束

4. 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。进一步分析，c是红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。

说明：下图中假设我们把新增结点标识为c(cur)，c的父亲标识为p(parent)，p的父亲标识为 g(grandfather)，p的兄弟标识为u（uncle）。

2.2.2情况一：变色

c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。在把g当做新的c，继续往上更新。 分析：因为p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加⼀个黑色结点，g再变红，相 当于保持g所在子树的黑色结点的数量不变，同时解决了c和p连续红色结点的问题，需要继续往上更新是因为，g是红色，如果g的父亲还是红色，那么就还需要继续处理；如果g的父亲是黑色，则处理结束 了；如果g就是整棵树的根，再把g变回黑色。 情况1只变色，不旋转。所以无论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。

图1将以上类似的处理进行了抽象表达，d/e/f代表每条路径拥有hb个黑色结点的子树，a/b代表每 条路径拥有hb-1个黑色结点的根为红的子树，hb>=0。

图2/图3/图4，分别展示了hb==0 / hb == 1 / hb == 2的具体情况组合分析，当hb等于2时，这里组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理方式⼀样的，变色再继续往上处理即可，所以我们只需要看抽象图即可。

图一：

 图二：

图三：

图四：

 2.2.3情况二：单旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑。u不存在，则c一定是新增结点，u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。

分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。

 如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。

如果p是g的右，c是p的右，那么以g为旋转点进行左单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。 

 2.2.4情况三：双旋+变色

注意为什么说u存在且为黑c一定不是新增节点，因为如果是新增节点，c就是红色，那么当前路径下的黑色节点数量一定会比其他路径小于1 

 2.3插入代码实现

	bool Insert(const pair<K, V>& kv){//空树直接插入if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//找到需要插入的地方Node* cur = _root;Node* parent = cur->_parent;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//到这里找到了cur = new Node(kv);// 新增结点。颜色为红 cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = 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){//		 g//	 p	     u//c// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}//uncle为nullptr 或者 uncle不为nullptr但为黑色else{if (cur == parent->_left)//对应情况二，单旋+变色{//     g//   p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//对应情况三，双旋+变色{//      g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//对应情况一//   g// u   pNode* uncle = grandfather->_left;// 叔叔存在且为红，->变色即可if (uncle && uncle->_col == RED)//对应情况一,直接变色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}//uncle为nullptr 或者 uncle不为nullptr但为黑色else{if (cur == parent->_right)//对应情况二，单旋+变色{// 旋转+变色//   g// u   p//       cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//对应情况三，双旋+变色{//   g// u   p//    cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

2.4红黑树的查找

还是二叉搜索树的逻辑

	Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}

2.5红黑树的验证

1. 枚举颜色类型，天然实现保证了颜色不是黑色就是红色。

2. 直接检查根即可。

3. 前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查⽗亲的颜色就方便多了。

4. 前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。

	bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历走到空时，意味着⼀条路径走完了 //cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值 int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}

 


http://www.ppmy.cn/news/1540760.html

相关文章

阿里云验证码短信发送服务搭建（flask)

阿里云验证码短信发送服务搭建（flask)

参考&#xff1a;https://next.api.aliyun.com/api-tools/sdk/Dysmsapi?version2017-05-25&languagejava-async-tea&tabprimer-doc 我们需要思考验证服务一些要求&#xff1a; 1.验证码只能被验证一次&#xff0c;所以需要状态字段 2.验证码有失效时间&#xff0c;超…
阅读更多...
智能听诊器：宠物健康数据的守护者

智能听诊器：宠物健康数据的守护者

智能听诊器的出现&#xff0c;为宠物健康数据的管理提供了新的解决方案。它能够收集宠物的生理数据&#xff0c;并将其安全地存储在云端&#xff0c;这样即使宠物主人更换设备或遗失数据&#xff0c;也能轻松恢复宠物的健康记录。这种数据的长期保存和备份&#xff0c;对于宠物…
阅读更多...
【从零开始的LeetCode-算法】908. 最小差值 I

【从零开始的LeetCode-算法】908. 最小差值 I

给你一个整数数组 nums&#xff0c;和一个整数 k 。 在一个操作中&#xff0c;您可以选择 0 < i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] x &#xff0c;其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i &#xff0c;最多 只能 应用 一次 此操…
阅读更多...
金融衍生品中的风险对冲策略分析

金融衍生品中的风险对冲策略分析

金融衍生品是现代金融市场中不可或缺的一部分&#xff0c;它们通过标的资产的价格波动为投资者提供了多样的风险管理工具。随着市场的不确定性和复杂性增加&#xff0c;风险对冲成为企业和个人投资者的首要任务。本文将深入探讨金融衍生品中的常见风险对冲策略&#xff0c;分析…
阅读更多...
git分支操作简记

git分支操作简记

一、分支名规则 1、默认分支 版本库中的默认分支命名为master 2、/ 可以使用斜杠&#xff08;/&#xff09; 创建一个分层的命名方案。 但是&#xff0c; 该分支名不能以斜线结尾。 3、- 分支名不能以减号&#xff08;-&#xff09; 开头。 4. 以斜杠分割的组件不能以点&…
阅读更多...
【配色网站分享】

【配色网站分享】

个人比较喜欢收藏一些好看的插画、UI设计图和配色&#xff0c;于是有了此篇&#xff0c;推荐一些配色网站&#xff0c;希望能对自己和大家有些帮助。 1.uiGradients 一个主打渐变风网站&#xff0c;还可以直接复制颜色。 左上角的“show all gradients”可以查看一些预设的渐…
阅读更多...
find_library、pkg_check_modules、pkg_search_module的区别

find_library、pkg_check_modules、pkg_search_module的区别

在CMake中&#xff0c;find_library、pkg_check_modules和pkg_search_module是用于查找和使用库的三种不同命令。以下是具体介绍&#xff1a; find_library 功能&#xff1a;find_library用于查找指定的库文件&#xff08;动态库或静态库&#xff09;&#xff0c;不依赖于库提供…
阅读更多...
完美解决 PyCharm 2024.2.2 等新版本无法使用经典布局-旧布局的问题

完美解决 PyCharm 2024.2.2 等新版本无法使用经典布局-旧布局的问题

原始老版本可以的操作 【pycharm】将pycharm新界面切换为旧界面_pycharm使用旧版ui-CSDN博客 新版本解决方案 对于 PyCharm 2024.2.2 及更高版本&#xff0c;如果通过上述方法找不到修改经典布局选项&#xff0c;可以按照官方文档的步骤进行操作&#xff1a; 新 UI |PyChar…
阅读更多...
最新文章

Copyright @ 2022~2023