模板网站建设多少钱,软文代写,中国城乡建设部官方网站,网络舆情监测平台前言 前面 学习了 AVL树#xff0c;AVL树虽然在 查找方面始终拥有 O(log N #xff09;的极高效率#xff0c;但是#xff0c;AVL 树在插入 ,删除等等 修改的操作当中非常的麻烦#xff0c;尤其是 删除操作#xff0c;在实现当中细节非常多#xff0c;在实现上非常难掌控…前言 前面 学习了 AVL树AVL树虽然在 查找方面始终拥有 O(log N 的极高效率但是AVL 树在插入 ,删除等等 修改的操作当中非常的麻烦尤其是 删除操作在实现当中细节非常多在实现上非常难掌控。具体可以看以下两篇文章C - AVL 树 介绍 和 实现 上篇_chihiro1122的博客-CSDN博客
C - AVL树实现下篇- 调试小技巧_chihiro1122的博客-CSDN博客 而 红黑树 在构建就下个对容易一些了。
红黑树 介绍
红黑树和 AVL树一样都是 二叉平衡搜索树红黑树的构建是在 每个结点除了 孩子的链接关系和值以外加一个位置存储该结点的颜色一个结点的颜色只有 red 和 black 两种。红黑树通过对 任意一条路径上的各个结点的颜色限制确保没有一条路径会比其他路径长出两倍。 相比于 AVL树红黑树对于平衡的要求更加宽松他只是要求最长路径最多是 最短路径的两倍
而 AVL树 是严格限死了 左右子树高度不能超过 2 。
也就是说红黑树在高度上 要比 AVL树要高一些。
虽然 红黑树 在平衡上更加的宽松但是实际的效率却依旧非常的高并不比 AVL树差至于为什么我们在下述来验证。
而且 红黑树不会进行 旋转尽管在 AVL树当中旋转是常量级的但是数量多了之后还是有很多的消耗。
在AVL树当中插入和删除都要经过很多次的旋转。也就造成不小的消耗。
而 AVL树 相比于 红黑树 多出来的消耗在 红黑树看来是没有必要的。 如下图当中的分析 红黑树树的性质规则
每个结点不是红色就是黑色 根节点是黑色的如果一个节点是红色的则它的两个孩子结点必须是黑色的 。每一条从根结点开始的路径没有重复的红色结点对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点。红黑树当中每一条路径上黑色结点数是相同的在一条路径当中黑色结点的占比一定 大于 或 等于 1 /2 每一个 “叶子结点” 都是黑色的注意此处的叶子结点不是我们以前理解的 最后一个结点在红黑树当中的 这里的 “叶子结点” 实际上是最后一个 NULL 结点所有的 NIL 结点都是 黑色的。如下图所示 在红黑树当中对 这个 NULL 结点进行了重新定义取名为 NIL 结点而且我们上述所说的路径是指从根结点到最后的 NIL 结点为一条路径。 就比如上述如果不加上 NULL 那么计算出来的路径数目就是 5 条但是如果加上 NULL 来计算的话就是 11 条而11 跳才是正确。 也就是说如果你不加上最后一个 NULL 结点来用 红黑树的规则来判断 一颗树是不是红黑树的话机会出错比如下述例子: 如果你按照我们以前认为最后一个结点就是叶子结点而且在算上路径时候没有加上最后的NULL。那么你就会认为这是一颗红黑树
但实际上这不是一颗红黑树。 其实按照上述 的 第五条性质其实就是在每一条路径的后面都加上了 一个 黑色结点。 insert插入函数 首先我们来想一下当一颗红黑树当中已经有结点了如下所示那么当我们插入一个结点是插入红色的结点还是 插入一个黑色的结点好呢 如果插入 黑色结点就会违反 条件4,如果插入 红色结点就会违反 条件3
如果要违反条件的话可能是违反 条件3更好。
因为 如果违反条件4就会影响全部路径而如果 违反条件3 就只会 影响一个路径不会是全部路径。
如下所示我们插入一个黑色结点 在插入A结点之后到A结点的这条路径的 黑色结点的个数就 1了但是其他路径上都没有变化此时就影响到其他 路径了。
但是如果插入的是一个红色的结点只影响一个路径所以当发生错误的时候我们可以修正 上述插入的B结点在 22 的下面22 是红色结点这个位置就不行但是如果是插入在 15 的下面15 是一个黑色的结点是可以的。 如果 红色结点 B 插入到 22 的下面此时 B 的父亲结点是 红色的说明B 一定会有 父亲的父亲也就是说 grandfather。因为 整棵树只有根结点才没有父亲而根结点必须是 黑色的 如上所示红色结点一定有 父亲。也就是说出现上述情况的话grandfather 结点是肯定存在的。 红黑树的插入修改过程 我们上述讨论了插入的结点必须是红色的结点插入红色的结点的话就会影响到父亲新插入结点的路径。 具体例子理解 所以此时我们要从该路径上进行修改。 此时违法的规则就是 B 和 22 两个红色结点连在一起了所以我们就想着把 22 边黑但是变黑的话就会影响这棵树当中的黑节点个数。 所以在更新完 25 这颗子树之后可能会像 AVL 树当中的平衡因子一样往上更新的。 如上述图单次对于子树的修改 需要先找到 新插入结点 父亲的 亲兄弟uncle。 如果 uncle 存在且为 红那么就把 parent 和 uncle 都变 黑 但是此时我们发现变黑之后对于 22 和 27 这两条路径来说黑色结点个数相比于其他路径在增多了一个所以此时我们在让 grandfather 结点变红就可以解决黑色结点个数问题 但是对于 grandfather 结点不一定都是这种的处理方法 如果 grandfather 结点没有父亲说明此时 grandfather 结点是 整棵树的根结点那么把 grandfather 结点变红就行。如果 grandfather 有父亲grandfather 是 黑色就结束了。如果 grandfather 有父亲grandfather 是 红色有和上述问题一样了需要找 uncle。 我们继续来看上述例子 在上述修改之后 发现 17 和 25 又是两个红色结点链接在一起了此时就要对这个链接关系进行修改此时就好比是 新插入了 25 结点。 找 uncle8uncle 为红就把 parent 和 uncle 一起改为黑此时的 grandfather 没有父亲结点了就不用再变黑了 如果按照上述的过程来修改的话我们发现相当于是在每一条路径当中都增加了一个 黑色结点。 黑色结点其实是有好处的比如上述的例子的那种我们插入的新结点一定是 红色的那么插入在黑色结点后面就不用像上述一样进行修改如上图所示我们只有在 6 后面和在 B 后面插入结点才会像上述一样进行修改。 上述是 有uncle的情况如果 parent 没有亲兄弟也就是 cur 没有 uncle的话应该怎么办呢 如上述所示cur 没有 uncle我们不能直接把 parent 变黑因为会多出一个 黑色结点有人又说多出来一个黑色结点的话把 grandfather 在变 红不就行了但是 如果把 grandfather 变红的话指向 uncle 的路径上就少一个 黑色结点了。 而且我们发现如果在 cur 位置插入的话13 的右子树的上的路径长度已经比 左子树 上的路径长度多出 2 倍了。 所以不管是否 多出 2 倍在没有 uncle的情况下我们应该进行旋转来调整位置。 判断旋转方式还是和在 AVL树当中判断方式一样旋转方式请看一下博客: C - AVL 树 介绍 和 实现 上篇_chihiro1122的博客-CSDN博客 像上述就是发生了的右单旋但是旋转之后发现颜色上还是 违反了规则。 所以此时要变色。 所以当uncle 不存在的时候处理规则就是 旋转 变色。 uncle存在且为红的情况在修改之后也有可能会出现 最长路径和最短路径 长度超过两倍的情况uncle 为黑的情况 修改 此时我们发现如果我们单纯的把 17 变黑已经不能解决问题了此时也是需要旋转的。 13 的右子树已经明显的高了要对右子树进行旋转此时发生左单旋。如果是下述情况就是 双旋 cur parent grandfather 构成折线就要发生双旋。 但是在 AVL 树当中我们判断旋转的方式是利用 平衡因子的方式来判断的但是在红黑树当中没有平衡因子我们需要判断 cur parent grandfather 三者的链接关系来 确认要哪一种旋转。 我没发现红黑树优势不仅仅在于旋转变少了他是在修改过程当中就会把很多结点变黑那么在以后插入当中插入到黑节点后面就不必再进行修改了。 小总结
红黑树的插入关键看 uncle。
如果 uncle 存在且为红变色 往上进行处理如果 uncle存在且为黑旋转变色往上进行处理如果 uncle不存在旋转 变色 往上进行处理 抽象图理解 红黑树插入过程 按照上述说明出现需要修改的情况都是 红红黑的结构也就是 cur 为红 parent 为红grandfather 为黑的情况而修改过程当中判别不用的修改方式是看 uncle 的。
我们先来总结一下 解决方案
情况一: cur为红p为红g为黑u存在且为红。 解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。 情况二: cur为红p为红g为黑u不存在/u存在且为黑。 解决方法p为g的左孩子cur为p的左孩子则进行右单旋转 p为g的右孩子cur为p的右孩子则进行左单旋转。 p为g的左孩子cur为p的右孩子则针对p做左单旋转 p为g的右孩子cur为p的左孩子则针对p做右单旋转
具体情况分析
情况一 比如上述是 的抽象图他可能是 一颗子树也可能是 整棵树。 那么当我们在 a b 后面插入的话可能就会应发 情况一 当 c/d/e 子树每条路径当中只有 一个 黑色结点 如上述情况我们就要使用 情况一的处理方式了。 对于情况一因为不旋转对于新结点的插入位置是不管的主要是 在 a 和 b 的四个位置插入都是引发情况一或者不引发。 至于 cur 可能本来就是 grandfather 的黑色结点只是在 ab当中没有个进行修改把 grandfather 修改为了 红色。 当然还有 cur 本来就是 新增结点的情况也就是 a 和 b 两个子树都是 空 但是处理方式还是情况一的方式。 当 c/d/e 子树每条路径当中有两个黑色结点 c/d/e 子树每条路径当中有两个黑色结点的情况太多了上图当中只是简单列出一些。 在 上述 只有一个黑结点的路径当中只用一层就修改就修改到了 cur 结点而在当前 路径当中有两个黑结点就是修改两层才修改到 cur 结点的颜色的。这里的层一层就是 一个 cur parent grandfather 组合子树 反正就是 路径当中有两个黑色结点的情况要比 只有一个黑结点的情况复杂得多但是最终还是属于情况一都是使用 情况一的方式来进行解决。 情况二 情况二当中的uncle有两种情况 一种是 uncle不存在 如果 uncle 不存在那么 cur 一定是新插入的结点因为如果 cur 不是新插入结点那么 cur 和 p 当中一定至少有一个是 黑色的。 另一种是 uncle 的颜色是 黑色 如果 uncle 是黑色的话cur 这个结点一定不是 新插入的结点因为假设在插入之前也就相当于是没有 cur 这个结点g - p - null 路径 和 g - u - ········ 路径 两个路径上 黑色结点个数不一样。所以插入之前的树不可能是红黑树。
所以uncle 为黑的这种情况一定是 cur 当中的子树发生了修改往上修改的时候影响到了 cur 修改过程如下都是旋转 变色的方式。只不过旋转当中有四种方式具体要看 cur parent grandfather 三者之间的链接关系。 像上述这种情况 c 子树的路径当中每条之后一个黑结点d 和 e 可能为空也可能有一个 红结点。 同样的c d e 三个子树当中的黑色结点可以按照上述的规律增加那么就是不同的具体例子。
比如c是 两个黑色结点的红黑树那么 d 和 e 就是一个结点的红黑树。 红黑树的结果是无穷无尽的每一种结构也相对复杂但是上述都是属于 情况二解决方式都是一样的。 情况二当中旋转变色之后就不需要网上进行处理了为在旋转变色之后这棵子树的根结点一定是 黑色的不会是 红色的那么黑色的结点不管和 红色的结点还是和 黑色的结点链接都是不会出现问题的。在情况一当中之所以要继续往上更新是因为情况一修改出来的根结点是红色的。 红黑树的验证 红黑树的检测分为两步
检测其是否满足二叉搜索树(中序遍历是否为有序序列) 检测其是否满足红黑树的性质 检测是否满足红黑树性质
bool CheckColor(Node* root, int blacknum, int benchamark){// 当走到叶子结点的 null 指针处也就是 NIL结点处if (root nullptr){// 如果计算出的路径黑色结点长度 和 外部计算的不一样// 说明不是红黑树if (blacknum ! benchamark){cout 路径黑色结点个数不一样 endl;return false;}return true;}// 用于递归计算 路径的黑色结点个数if (root-_color BLACK)blacknum;// 如果当前结点为 红色且当前结点的父亲也是红色就不是红黑树if (root-_parent root-_parent-_color RED root-_color RED){cout 有连续红色 endl;return false;}// 左右子树递归return CheckColor(root-_left, blacknum, benchamark) CheckColor(root-_right , blacknum, benchamark);}// 外部调用接口bool isBalance(){return isBalance(_root);}// 内部封装函数bool isBalance(Node* root){if (root nullptr)return true;// 如果整棵树的 根结点不是 黑色的就不是红黑树if (root-_color ! BLACK){cout 根结点不是黑色 endl;return false;}// 基准值// 在递归外部计算出左路第一条路径的 黑色结点值int benchmark 0;Node* cur root;while(cur){if (cur-_color BLACK)benchmark;cur cur-_left;}return CheckColor(root, 0, benchmark);}
我们使用两个函数相互调用来实现外层函数判断整棵树的根结点是不是 黑色的
而且计算左边第一条路径的黑色结点个数。其实可以随便找一条路径因为这个只是一个基准值不需要是正确的因为红黑树当中的每一条路径都需要黑色结点数相同。
然后用内层函数递归遍历红黑树。
内层函数当中计算出每一条黑色结点的个数判断是否有连续的红色结点
检测其是否满足二叉搜索树就直接中序遍历打印就行了这里就不实现了。 红黑树的删除
红黑树的删除和 AVL树一样都比插入要复杂可以看下面这个博客来了解红黑树 - _Never_ - 博客园 (cnblogs.com)
完整代码实现 #pragma once// 节点的颜色
enum Color { RED, BLACK };// 红黑树节点的定义
templateclass K, class V
struct RBTreeNode
{RBTreeNode(pairK ,V kv , Color color RED): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _color(color){}RBTreeNodeK, V* _left; // 节点的左孩子RBTreeNodeK, V* _right; // 节点的右孩子RBTreeNodeK, V* _parent; // 节点的双亲(红黑树需要旋转为了实现简单给出该字段)pairK, V _kv; // 节点的值域Color _color; // 节点的颜色
};templateclass K ,class V
class RBTree
{typedef RBTreeNodeK,V Node;
public:bool insert(pairK , V kv){// 搜索二叉树的插入逻辑// // 如果当前树为空直接用头指针只想新结点if (_root nullptr){_root new Node(kv);_root-_color BLACK;return true;}// 不为空接着走Node* cur _root; // 用于首次插入时候指针的迭代Node* parent nullptr;while (cur){// 如果当前新插入的 key 值比 当前遍历的结点 key 值大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-_color RED;// 再次判断大小判断 cur应该插入到 parent 的那一边if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}// 链接 新插入结点 cur 的_parent 指针cur-_parent parent;// 红黑树调整高度平衡高度的逻辑while (parent parent-_color RED){// parent 为 红parent-_parent 一定不为空Node* grandfather parent-_parent;// 如果父亲是在 祖父的左if (parent grandfather-_left){Node* uncle grandfather-_right;// 叔叔存在且为红if (uncle uncle-_color RED){// 变色parent-_color uncle-_color BLACK;grandfather-_color RED;// 向上迭代cur grandfather;parent cur-_parent;}// uncle 不存在 或者 存在且为黑else{if (cur parent-_left){// g// p// cRotateR(grandfather);parent-_color BLACK;grandfather-_color RED;}else // cur parent-_right{// g// p// cRotateL(parent);RotateR(grandfather);cur-_color BLACK;grandfather-_color RED;}break; // 不需要再往上更新}}else // parent grandfather-_right{Node* uncle grandfather-_left;// uncle 存在 且 uncle 的颜色是红色if (uncle uncle-_color RED){parent-_color uncle-_color BLACK;grandfather-_color RED;cur grandfather;parent cur-_parent;}else // 不存在 或者 存在且为黑色{if (cur parent-_right){// g// p// cRotateL(grandfather);parent-_color BLACK;grandfather-_color RED;}else // cur parent-_left{// g// p// cRotateR(parent);RotateL(grandfather);cur-_color BLACK;grandfather-_color RED;}break; // 不用再往上更新}}}// 不管上述如何修改红黑树的根结点永远是黑的// 所以我们这里既直接硬性处理_root-_color BLACK;return true;}void RotateL(Node* parent){Node* cur parent-_right; // 存储 parent 的右孩子Node* curleft cur-_left; // 存储 cur 的左孩子parent-_right curleft;if (curleft) // 判断 cur 的左孩子是否为空{curleft-_parent parent; // 不为空就 修改 cur 的左孩子的_parent 指针}cur-_left parent;// 留存一份 根结点指针Node* ppnode parent-_parent;parent-_parent cur;// 如果parent 是根结点if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}void RotateR(Node* parent){Node* cur parent-_left;Node* curRight cur-_right;parent-_left curRight;if (curRight){curRight-_parent parent;}cur-_right parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}bool CheckColor(Node* root, int blacknum, int benchamark){// 当走到叶子结点的 null 指针处也就是 NIL结点处if (root nullptr){// 如果计算出的路径黑色结点长度 和 外部计算的不一样// 说明不是红黑树if (blacknum ! benchamark){cout 路径黑色结点个数不一样 endl;return false;}return true;}// 用于递归计算 路径的黑色结点个数if (root-_color BLACK)blacknum;// 如果当前结点为 红色且当前结点的父亲也是红色就不是红黑树if (root-_parent root-_parent-_color RED root-_color RED){cout 有连续红色 endl;return false;}// 左右子树递归return CheckColor(root-_left, blacknum, benchamark) CheckColor(root-_right , blacknum, benchamark);}// 外部调用接口bool isBalance(){return isBalance(_root);}// 内部封装函数bool isBalance(Node* root){if (root nullptr)return true;// 如果整棵树的 根结点不是 黑色的就不是红黑树if (root-_color ! BLACK){cout 根结点不是黑色 endl;return false;}// 基准值// 在递归外部计算出左路第一条路径的 黑色结点值int benchmark 0;Node* cur root;while(cur){if (cur-_color BLACK)benchmark;cur cur-_left;}return CheckColor(root, 0, benchmark);}
private:Node* _root nullptr;
};
