武进网站建设价位,城乡规划建设网站,招商网站平台,如何建设淘客网站#x1f341;你好#xff0c;我是 RO-BERRY #x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 #x1f384;感谢你的陪伴与支持 #xff0c;故事既有了开头#xff0c;就要画上一个完美的句号#xff0c;让我们一起加油 目录 前言1.红黑树的概念2.红黑… 你好我是 RO-BERRY 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 感谢你的陪伴与支持 故事既有了开头就要画上一个完美的句号让我们一起加油 目录 前言1.红黑树的概念2.红黑树的性质3.已经学了BST和AVL树为啥还要学红黑树4.红黑树节点的定义5. 红黑树旋转5.1 左旋示例5.2 右旋示例5.3 代码实现 6.红黑树插入情况一父节点为空情况二父节点是黑色情况三父节点是红色叔叔也为红色。情况四父节点是红色叔叔为黑色。插入小结 7. 删除7.1 删除节点仅存在一个孩子7.2删除节点不存在孩子删除小结 8.红黑树的验证9. 红黑树的查找9. 红黑树与AVL树的比较10.map底层为什么用红黑树实现红黑树.平衡二叉树AVL树 11. 源码11.1 RBTree.h11.2 Test.cpp 前言
这篇文章我们再来学习一种平衡搜索二叉树——红黑树 如果要说常见的数据结构里哪个数据结构最麻烦、最难以掌握 绝对非红黑树莫属了如果只是自己看的话很多人可能看很多遍都不太懂红黑树。 红黑树和AVL树都是常见的自平衡二叉搜索树它们都可以用于高效地支持插入、删除和查找等操作。虽然它们都能够保持树的平衡性但在不同的应用场景下红黑树和AVL树有各自的优势和适用性。 1.红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍最长路径也不会超出最短路径的两倍因此红黑树的平衡性要求相对宽松没有AVL树那样严格从而使搜索树达到一种相对平衡的状态。 2.红黑树的性质
红黑树是特殊的二叉查找树又名R-B树(RED-BLACK-TREE)由于红黑树是特殊的二叉查找树即红黑树具有了二叉查找树的特性而且红黑树还具有以下特性 每个节点要么是黑色要么是红色根节点是黑色每个叶子节点是黑色并且为空节点(还有另外一种说法就是每个叶子结点都带有两个空的黑色结点被称为黑哨兵如果一个结点n的只有一个左孩子那么n的右孩子是一个黑哨兵如果结点n只有一个右孩子那么n的左孩子是一个黑哨兵。)每个红色节点必须有两个黑色的子节点从每个叶子到根的所有路径上不能有两个连续的红色节点从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 有几点需要注意的是
特性3中指定红黑树的每个叶子节点都是空节点但是在Java实现中红黑树将使用null代表空节点因此遍历红黑树时看不到黑色的叶子节点反而见到的叶子节点是红色的特性4保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍例如黑色高度为3的红黑树其最短路径(路径指的是根节点到叶子节点)是2(黑节点-黑节点-黑节点)其最长路径为4(黑节点-红节点-黑节点-红节点-黑节点)。 思考为什么满足上面的性质红黑树就能保证其最长路径中结点个数不会超过最短路径结点个数的两倍其实不带第4条就可以加不加第4条都不会影响每条路径黑色结点数量是否相等
那通过上面的性质我们可以得知红黑树中的结点要么是黑色要么是红色这没什么可说的然后要求根结点一定是黑色的红色结点不能连续出现如果出现了红色结点那它的子结点必须是黑色的然后还要求每条路径黑色结点的数量必须相等。 那这样其实就可以保证一棵红黑树中最长路径不超高最短路径的两倍。 当然实际中不同的红黑树情况是不一样的所以我们这里来分析一种极端的情况 大家想如果一棵红黑树有红有黑它里面如果有一条全黑的路径那这条全黑的路径一定就是最短路径 如果有一条是一黑一红一黑一红…这样黑红相间的那他就是最长的路径。 然后它们里面的黑色结点个数又是相同的的所以最长路径最多是最短路径的两倍不可能超过最短路径两倍。 所以这样红黑树的高度就能够保持在一个相对平衡的范围内当然他就没有AVL树那么严格。 比如这样的 那另外:
其实分析上面的性质红黑树是可以全黑的全部黑色结点只要满足上面的性质即可。 然后大家思考一个问题上面第四条性质——每个叶子结点都是黑色的(此处的叶子结点指的是空结点也被称为NIL节点)有什么用
那大家先算一下这个红黑树有多少条路径 如果不带空的话我们可能会认为有5条但是这里计算路径其实应该走到空NIL所以正确的应该是有11条路径。 所有我们可以认为这条规则就是为了更好的帮我们区分不同路径的。
然后再补充一个概念
结点的黑高黑色高度从某结点出发不含该结点到达任一空叶结点的路径上经过的黑结点总数 3.已经学了BST和AVL树为啥还要学红黑树
然后我们再来分析一个问题
大家想对于一棵红黑树来说如果它里面全部的黑色结点一共有N个的话那它的最短路径长度就差不多是 l o g 2 ( N ) log_2 (N) log2(N)。 然后整棵树的节点数量就是在【N2N】之间。 所以最长路径长度就可以认为差不多是2 l o g 2 ( N ) log_2 (N) log2(N) 所以红黑树的查找最少是 l o g 2 ( N ) log_2 (N) log2(N)次最多是2 l o g 2 ( N ) log_2 (N) log2(N)次所以红黑树查找的时间复杂度是O( l o g 2 N log_2 N log2N)计算时间复杂度前面的常数项可以省略嘛。 而AVL树也是O( l o g 2 N log_2 N log2N但AVL树是比较严格的O( l o g 2 N log_2 N log2N而红黑树是省略了常数项。 所以严格来说红黑树的查找效率是比不上AVL树的但对于计算机来说是没什么差别的但是它们是同一个数量级的都是O( l o g 2 N log_2 N log2N。
那既然好像都差不多为什么我们已经学了AVL树了还要学红黑树呢红黑树有什么优势吗 由于AVL树要求更加严格的平衡所以在进行插入和删除操作时可能需要更频繁地进行旋转操作来调整树的结构以保持平衡。相比之下红黑树的插入和删除操作需要旋转的次数相对较少因此在插入和删除操作频繁的情况下红黑树可能更加高效。 这个如果大家学完这篇文章或许能更好的理解。 所以综合而言 红黑树是牺牲了严格的高度平衡的优越条件为代价它只要求部分地达到平衡要求降低了对旋转的要求从而提高了性能。 红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外由于它的设计任何不平衡都会在三次旋转之内解决。 当然还有一些更好的但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡但红黑树能够给我们一个比较“便宜”的解决方案。 相比于BST因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度所以可以看出它的查找效果是有最低保证的。 在最坏的情况下也可以保证O(logN)的这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。 红黑树的算法时间复杂度和AVL相同但统计性能比AVL树更高所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多 但是他们的查找效率都是O(logN)所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据。 如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。 4.红黑树节点的定义
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
templateclass ValueType
struct RBTreeNode
{RBTreeNode(const ValueType data ValueType()Color color RED): _pLeft(nullptr),_pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNodeValueType* _pLeft; // 节点的左孩子RBTreeNodeValueType* _pRight; // 节点的右孩子RBTreeNodeValueType* _pParent; // 节点的双亲(红黑树需要旋转为了实现简单给出该字段)ValueType _data; // 节点的值域Color _color; // 节点的颜色
};思考在节点的定义中为什么要将节点的默认颜色给成红色的 我们来分析一下如果我们插入一个新结点给的是黑色那它一定会违反上面提到的红黑树的第5条性质——每条路径上黑色结点的数量一致。如图 因为原来每条路径黑色结点数量是相同的现在新插入一个黑色结点的话那插入的这条路径会增加一个黑色结点但是其它路径数量不变所以其它所有的路径黑色结点数量都和这一条不相等这样就比较麻烦了。 那如果我们插入结点默认给红色呢会违反规则吗 那红色的话其实要看具体情况了 如果插入一个红色结点但是它的父亲也是红色那就出事了因为红黑树里面不能出现连续的红色结点那这种情况就需要调整了。 但如果它的父亲是黑色那就没问题不需要进行什么处理。
所以我们新插入的结点给成红色当然如果是第一次插入根结点我们可以直接给黑色因为红黑树要求根结点必须是黑色。
5. 红黑树旋转
在分析插入和删除操作前我们需要先说明一下旋转操作这个操作在后续操作中都会用得到。旋转操作分为左旋和右旋左旋是将某个节点旋转为其右孩子的左孩子而右旋是节点旋转为其左孩子的右孩子。
5.1 左旋示例 5.2 右旋示例 5.3 代码实现 void RotateL(Node* parent) //左单旋{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}}void RotateR(Node* parent) //右单旋{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}6.红黑树插入
红黑树的插入过程和二叉查找树插入过程基本类似不同的地方在于红黑树插入新节点后需要进行调整以满足红黑树的性质。性质1规定红黑树节点的颜色要么是红色要么是黑色那么在插入新节点时这个节点应该是红色还是黑色呢
我都想不说答案大家直接看性质5 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。你插个黑的是不是必然会影响是不是就要调整了是不是必然就是红的了对的吧红的出现两红连续了可能才需要调整对的吧所以插入的节点应该是红色的。
插入我们可能感觉很迷茫不知道如何下手这玩意这可咋插入呀一想到就头大就逃避哈哈哈凡复杂事情其实按情况去划分把每种情况都克服了整体也就克服了。我们站在待插入节点的角度去看我要往哪个父节点下插入那么看父节点的话那插入的几种情况我们就来看看哈我们这里待插入的节点为N节点
情况一父节点为空
当父节点为空也就是到根节点了因为性质2所以将节点 N 直接变黑作为根节点即可。
情况二父节点是黑色
当父节点是黑色这种情况下性质4和性质5没有受到影响不需要调整。
情况三父节点是红色叔叔也为红色。
待插入节点N的父节点为红色叔叔也是红色的情况时性质4就会被打破此时需要进行调整。这种情况下先将 父节点 和 叔叔节点 染成黑色再将 爷爷节点 的颜色染成红色。此时经过爷爷的路径上的黑色节点数量不变想想是不是性质5仍然满足。但需要注意的是 G 被染成红色后可能会和它的父节点形成连续的红色节点此时需要递归向上调整。 当然此情况下的这些情况都属于情况三哈。
情况四父节点是红色叔叔为黑色。
这种情况跟情况三的不同关键点就在于叔叔的节点颜色情况三叔叔是红色而情况四叔叔是黑色的哈。我们的角度从父节点的左右以及待插入节点是父节点的左右可以分成细拆成4种情况我们来看下这四种情况的处理 1父节点为左子树待插入节点为父节点的左子树 2父节点为左子树待插入节点为父节点的右子树 小记当父节点为左子树时待插入的节点都要往左靠这个理解不你看上图待插入N在父节点P的右边时是不是先左旋了一下都靠左边了然后跟待插入节点在左子树时保持都靠左边啦然后父节点和爷爷换色然后右旋的。
3父节点为右子树待插入节点为父节点的右子树 4父节点为右子树待插入节点为父节点的左子树 小记可以看到跟左子树的思路其实差不多先把节点都往右靠只是旋转方向不一样右子树是左旋左子树是右旋。
插入小结
针对插入我们看到划分情况来处理哈
父节点为空的话就直接变黑即可父节点为黑的话保持位置不变即可父节点为红的话就要观察叔叔节点的颜色父节点为红叔叔为红直接父亲和叔叔变黑爷爷变红然后以爷爷为中心继续递归处理父节点为红叔叔为黑就要父亲是左子树还是右子树以及待插入的是父亲的左子树还是右子树父亲是左子树就要往左靠所以待插入如果在父亲的右子树就要先左旋然后父亲和爷爷换色然后以爷爷为中心右旋哈父节点为红叔叔为黑父亲是右子树就要往右靠所以待插入如果在父亲的左子树就要先右旋然后父亲和爷爷换色然后以爷爷为中心左旋哈。
实现代码 bool Insert(const pairK, V kv){if (_root nullptr) //空树{_root new Node(kv); //新增节点为根节点_root-_col BLACK; //根节点为黑色新节点默认为红我们修改为黑色return true;}Node* parent nullptr; //父亲Node* cur _root; //根节点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为空这里就是要插入的位置cur new Node(kv); // 红色的//连接if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}//链接父亲cur-_parent parent;//如果插入以后它的parent是红色的就需要处理while (parent parent-_col RED){Node* grandfather parent-_parent;//如果父亲是爷爷的左孩子那右孩子就是叔叔if (parent grandfather-_left){Node* uncle grandfather-_right;// 情况一叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理//更新cur为grandfather判断它的父亲是什么情况//1.如果不存在或者为黑就需要继续处理也不会进行循环//2.如果它的父亲存在且为红重新循环进行调整cur grandfather;parent cur-_parent;}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{Node* uncle grandfather-_left;// 情况一叔叔存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right){RotateL(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;}7. 删除
相较于插入操作红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子如果有孩子不能直接删除该节点。我们看上边插入的时候看的是叔叔节点的眼色而删除是看的待删除节点的兄弟节点的颜色。还是一样我们站在待删除节点的角度我们可以从如下两个方面去考虑
节点的颜色节点有红黑两种可能那么删除黑节点就会造成节点失衡。节点的构造有三种可能其一是删除节点的孩子都为null其二是删除节点的一个孩子节点为null其三是删除节点的两个孩子节点都不为null。而如果两个节点都不为null那么我们就需要找替代节点(前驱或者后继结点)来替代删除而删除替代结点就会是情况一和情况二。
删除的第三种情况大家应该知道吧跟我们二叉排序树删除是不是要找一个前驱或者后继节点来替换然后将前驱或者后继节点的值赋值给待删除的节点然后删除前驱或者后继节点。而前驱或者后继结点的判断可以使用下图的方式将节点Key落入X轴中(实质是中序排序)其后一个结点就是后继节点前一个就是前驱节点那么我们看一下后继节点替代删除的方案比如删除-1那么可以将0替换到-1的位置然后删除0这样就回到情况一 再比如删除4那么使用5来代替然后删除5这样就回到了情况二。 由于前驱和后继至多只有一个孩子节点这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题问题被简化了一些。这个大家理解的吧不理解的话建议大家先去看一下二叉排序树的东西比如二叉排序树的删除再来这里看红黑树就好理解一点了。
那么针对红黑树的删除我们这里可分为三种情形
删除的节点有一个孩子节点删除节点只能是黑色其子节点也必为红色此时用删除节点的子节点接到父节点且将子节点颜色涂黑保证黑色数量。 删除的节点没有孩子节点如果是红色还好直接删除即可如果是黑色就需要考虑平衡了 删除的节点有两个孩子节点与二叉排序树一样使用前驱或者后继节点作为替换的删除节点场景转至为1或2处理。 接下来我们就仔细分析下情形一和情形二。
7.1 删除节点仅存在一个孩子
删除节点存在一个孩子那么此时不需要考虑节点的颜色因为该节点必然为黑色 (因为性质4红下必有俩黑或者俩null节点而我们这里的情况是只有一个孩子所以必为黑且孩子节点必然为红(如果为黑那么D节点就会有一方黑色节点比另一方多一这个理解么因为我们说过红黑树的任一黑节点为根的树也必是一颗红黑树)。那么情况一的所有情况如下 这种情况处理较为简单只需要将节点P的指针指向DL或者DR然后将DL或者DR的颜色变更为黑色 就保证了红黑树的平衡如下 上述情况需要注意当D是根节点时删除操作之后孩子节点会成为新的根节点
7.2删除节点不存在孩子
删除节点不存在孩子那么此时就需要考虑节点的颜色。
删除节点为红色 如果为红色因为性质4那么父节点肯定为黑色那么直接删除即可哈P节点断掉指向节点D的指针指向就好了。 删除节点为黑色 我们考虑黑色这种情况较为复杂因为黑色节点被删除之后红黑树会失去平衡此时需要调整平衡。那么可能的情况有如下几种(如果D为根节点删除操作后红黑树变为空树即可下面以非根节点的情况为例来分析) 父节点为红色兄弟节点不存在孩子 父节点为红色兄弟节点不存在孩子(兄弟节点必然存在且为黑色)这种情况稍微好处理因为将父节点变为黑色兄弟节点变为红色即可保证红黑树平衡。 父节点为红色兄弟节点存在孩子 父节点为红色兄弟节点存在孩子此时无法像情况 3.3.2.1 那么处理因为兄弟节点存在的孩子必然为红色理解么因为我们说了要删除的节点D没有孩子父亲是红兄弟就必是黑节点黑节点下如果还有黑节点是不是父节点为根的子树就不是红黑树了对不对那么此时就需要进行旋转。 父节点为黑色 当兄弟结点不存在孩子节点此时无法通过旋转来实现平衡即P节点无法继续调整那么就B设置为 红色保证P这个子树平衡然后通过P节点向上递归维持平衡。
比如P的父亲是红色的话 删除小结
1删除节点之后看看这个节点是不是黑色的叶子节点如果不是简单处理就可以达到平衡了
2先看N是不是根节点是的话啥都不用管不是的话看兄弟什么颜色 兄弟是红色进行旋转涂色去到兄弟为黑色那里处理 兄弟是黑色看看兄弟子节点是不是全部都是黑。 全黑的话看父节点什么颜色进行对应处理 不全黑看兄在的位置兄在左的话看兄的左子是不是红色进行对应处理兄在右的话看兄的右子是不是红色进行对应处理。
8.红黑树的验证
验证其是否平衡且满足红黑树性质 那如何判断它是否满足是一棵红黑树呢
其实就是去检查那几条规则性质
首先结点颜色要么是黑色要么是红色这没什么好检查的。 然后根结点必须是黑色这个可以检查一下如果根结点不是黑色是红色直接就不符合了 bool IsBalance(){if (_root _root-_col RED)return false;return Check(_root);}
然后如果出现连续的红色结点那也不符合。 那怎么检查有没有出现连续红色结点呢 我们可以去遍历这棵树然后遇到红色结点判断它的孩子是不是红色结点如果存在红色结点它的孩子也是红色那就不符合。 这样确实可以但是不太好因为孩子的话要检查两个而且结点的孩子有还有可能不存在为空那还得再加一个判断。 所以我们可以这样做遍历遇到红色结点我们去看它的父亲如果它的父亲也为红色那就不行。 而判断父亲的话只有根结点没有父亲但是根结点是黑色的也不会去检查它。 所以这样写会好一点 bool Check(Node* cur){if (cur nullptr)return true;if (cur-_col RED cur-_parent-_col RED){cout cur-_kv.first 存在连续的红色节点 endl;return false;}return Check(cur-_left) Check(cur-_right);}bool IsBalance(){if (_root _root-_col RED)return false;return Check(_root);}
然后还剩一个我们要检查每条路径黑色结点数量是否相等存在不相等的情况就不符合。 那这个要如何检查呢 我们可以先求出一条路径的黑色结点数量把它作为基准值然后再递归求出每条路径的黑色结点数量和它比较如果存在不相等的情况就不符合。 bool Check(Node* cur, int blackNum, int refBlackNum){if (cur nullptr){//走到空就是一条路径走完了比较一下是否相等if (refBlackNum ! blackNum){cout 黑色节点的数量不相等 endl;return false;}//cout blackNum endl;return true;}if (cur-_col RED cur-_parent-_col RED){cout cur-_kv.first 存在连续的红色节点 endl;return false;}if (cur-_col BLACK)blackNum;return Check(cur-_left, blackNum, refBlackNum) Check(cur-_right, blackNum, refBlackNum);}bool IsBalance(){if (_root _root-_col RED)return false;//先求出一条路径黑色结点数量int refBlackNum 0;Node* cur _root;while (cur){if(cur-_col BLACK)refBlackNum;cur cur-_left;}//检查是否出现连续红色结点及所有路径黑色结点数量是否相等return Check(_root, 0, refBlackNum);}9. 红黑树的查找
那红黑树的查找就也和搜索二叉树的查找一样之前讲过这里就不再说了。
9. 红黑树与AVL树的比较
红黑树和AVL树都是高效的自平衡搜索二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)。 红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍所以AVL树的插入和删除操作比红黑树更耗时。 因为AVL树在插入和删除节点后会进行更多的旋转操作以维持一个较为严格的平衡所以插入和删除操作的时间复杂度更高。 相对而言红黑树对平衡的控制比较宽松降低了插入删除时需要旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 在实际应用中红黑树的使用更广泛。许多编程语言和库都使用红黑树作为基础数据结构例如C STL中的std::map和std::set就是基于 红黑树实现的。
10.map底层为什么用红黑树实现
红黑树
红黑树是一种二叉查找树但在每个节点增加一个存储位表示节点的颜色可以是红或黑非红即黑。 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制红黑树确保没有一条路径会比其它路径长出两倍 因此红黑树是一种弱平衡二叉树相对于要求严格的AVL树来说它的旋转次数少所以对于搜索插入删除操作较多的情况下通常使用红黑树。
性质
每个节点非红即黑根节点是黑的;每个叶节点叶节点即树尾端NULL指针或NULL节点都是黑的;如果一个节点是红色的则它的子节点必须是黑色的。对于任意节点而言其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;
.平衡二叉树AVL树
红黑树是在AVL树的基础上提出来的。
平衡二叉树又称为AVL树是一种特殊的二叉排序树。其左右子树都是平衡二叉树且左右子树高度之差的绝对值不超过1。
AVL树中所有结点为根的树的左右子树高度之差的绝对值不超过1。
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1则该二叉树就是不平衡的。
11. 源码
11.1 RBTree.h
#pragma once
enum Colour
{RED,BLACK,
};
template class T
struct RBTreeNode
{RBTreeNodeT* _parent;RBTreeNodeT* _left;RBTreeNodeT* _right;T _data;Colour _col;
RBTreeNode(const T data):_parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(RED){}
};
template class T
class RBTree
{typedef RBTreeNodeT Node;
public:bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (data cur-_data){parent cur;cur cur-_left;}else if (data cur-_data){parent cur;cur cur-_right;}else{return false;}}//走到这里cur为空就是key应该插入的位置cur new Node(data);//链接if (data parent-_data)parent-_left cur;if (data parent-_data)parent-_right cur;
//链接父亲指针cur-_parent parent;
//如果插入之后它的parent是红的就需要进行调整while (parent parent-_col RED){Node* grandfather parent-_parent;//如果父亲是祖父的左孩子那右孩子就是叔叔if (parent grandfather-_left){Node* uncle grandfather-_right;//这里处理的情况是叔叔存在且为红变色向上继续处理if (uncle uncle-_col RED){//将p,u改为黑g改为红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;
//更新cur为grandfather判断它的父亲是什么情况//1.如果不存在或者为黑就需要继续处理了也不会进行循环了//2.如果它的父亲存在且为红重新循环进行调整cur grandfather;parent cur-_parent;}else//叔叔不存在/叔叔存在且为黑的情况{// g// p u// c if (cur parent-_left)//左左——右单旋变色{RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//左右——左右双旋变色{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}//这里调整完就可以break了因为颜色都变的合适了而相关的链接关系旋转会帮我们处理break;}}//如果父亲是祖父的右孩子那左孩子就是叔叔else //parent grandfather-_right{Node* uncle grandfather-_left;//这里处理的情况是叔叔存在且为红if (uncle uncle-_col RED){//将p,u改为黑g改为红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;
//更新cur为grandfather判断它的父亲是什么情况//1.如果不存在或者为黑就需要继续处理了也不会进行循环了//2.如果它的父亲存在且为红重新循环进行调整cur grandfather;parent cur-_parent;}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;}void InOrder(){_InOrder(_root);cout endl;}bool IsBlance(){if (_root _root-_col RED){cout 根结点是红色 endl;return false;}
//先求出一条路径黑色结点数量int mark 0;Node* cur _root;while (cur){if (cur-_col BLACK)mark;cur cur-_left;}
//检查是否出现连续红色结点及所有路径黑色结点数量是否相等return _Check(_root, 0, mark);}int TreeHeight(){return _TreeHeight(_root);}
private:int _TreeHeight(Node* root){if (root nullptr)return 0;int RightH _TreeHeight(root-_left);int leftH _TreeHeight(root-_right);return RightH leftH ? RightH 1 : leftH 1;}bool _Check(Node* root, int blackNum, int mark){if (root nullptr){//走到空就是一条路径走完了比较一下是否相等if (blackNum ! mark){cout 存在黑色结点数量不相等 endl;return false;}return true;}
if (root-_col BLACK)blackNum;
if (root-_col RED root-_parent-_col RED){cout 出现连续红色结点 endl;return false;}
return _Check(root-_left, blackNum, mark) _Check(root-_left, blackNum, mark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;
//旋转并更新_parent指针parent-_right subRL;if (subRL)subRL-_parent parent;
//先保存一下parent-_parent因为下面会改它Node* pparent parent-_parent;
//旋转并更新_parent指针subR-_left parent;parent-_parent subR;
//若pparent为空则证明旋转的是一整棵树因为根结点的_parent为空if (pparent nullptr){//subR是新的根_root subR;_root-_parent nullptr;}//若pparent不为空则证明旋转的是子树parent上面还有结点else{//让pparent指向子树旋转之后新的根if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}//同时也让新的根指向pparentsubR-_parent pparent;}}
//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;
//旋转并更新_parent指针parent-_left subLR;if (subLR)subLR-_parent parent;
//先保存一下parent-_parent因为下面会改它Node* pparent parent-_parent;
//旋转并更新_parent指针subL-_right parent;parent-_parent subL;
//若parent等于_root则证明旋转的是一整棵树这也是一种判断方法if (parent _root){_root subL;_root-_parent nullptr;}else{//让pparent指向子树旋转之后新的根if (parent pparent-_left){pparent-_left subL;}else{pparent-_right subL;}//同时也让新的根指向pparentsubL-_parent pparent;}}
private:Node* _root nullptr;
};11.2 Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include iostream
using namespace std;
#include time.h
#include RBTree.h
void RBTest1()
{//int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int arr[] { 95,47,32,29,7,7,2,50,74,30 };
RBTreeint t1;for (auto e : arr){t1.Insert(e);}t1.InOrder();
cout t1.IsBlance() endl;
}
void RBTest2()
{srand((unsigned int)time(nullptr));const int N 100000;RBTreeint t;for (int i 0; i N; i){int x rand() i;t.Insert(x);}cout t.TreeHeight() endl;
AVLTreeint, int t2;for (int i 0; i N; i){int x rand() i;t2.Insert(make_pair(x, x));}cout t2.TreeHeight() endl;
}
int main()
{RBTest2();return 0;
}
