??博客代码已上传至gitee：https://gitee.com/byte-binxin/cpp-class-code ????概念和性质 红黑树的概念： 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是R
|
??博客代码已上传至gitee：https://gitee.com/byte-binxin/cpp-class-code
????概念和性质红黑树的概念： 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。它是通过控制节点颜色的方式来控制这棵树的相对平衡，保证了没有一条路径会比其它路径长出两倍。
红黑树的性质：
上面的五个性质还可以用更通俗的语言描述为三句话：
思考： 为什么红黑树中最长路径的长度不会超过最短路径节点个数的两倍？ 最长路径： 该条路径上节点分布是一红一黑 最短路径： 该条路径上节点分布是全黑 假设每条路径黑色节点数为N，则最长路径为2N，最短路径为N，所以这样就推出红黑树中最长路径的长度不会超过最短路径节点个数的两倍。 ????红黑树的实现????红黑树节点定义这里也是一个三叉链，其中每个节点包含颜色的元素在里面：
????红黑树结构定义里面只包含一个根节点的成员变量，和前面两棵树的结构定义没有什么大的区别，区别在于节点的定义：
????红黑树的插入????方法概述第一步： 我们先按照二叉搜索树树插入节点的方式，插入节点 第二步： 为了不破坏红黑树的规则，我们插入节点后要对红黑树进行相应的调整 思考： 我们插入节点应该默认插入红色节点好还是黑色节点好呢？ 答案是红色节点。为什么呢？我们要考虑哪种方式对红黑树的破坏性更大一点。如果是黑色，此时黑导致该条路径比其它路径上黑色节点数都多一个，这样下来调整红黑树的步骤代价似乎会有点大；如果是红色，不会破坏规则5，只是破坏规则4，可能会出现连续的红色节点，这样我们只需要调整该节点及其附近节点的颜色即可，代价没有前一种方式大，所以我们选择第二种方式。 ????调整节点颜色第一种情况： 如果插入节点的父亲是黑色节点，那么可以直接结束，不需要继续调整了 第二种情况： 如果插入节点为的父亲为红色节点，就需要进行相应的调整 下面讨论父亲节点是祖父节点的左孩子的几种情形（是右孩子的情形和这个类型，大家可以自己推演一下，这里我们把父亲节点叫做p(parent)，祖父叫g(grandfather)，叔叔节点叫u(uncle)）： 情况1： p为红色（g肯定是存在的且为黑），u存在且为红 操作： 把p和u改成黑，g改成红，如果g为根节点就把g的颜色变成黑然后结束，如果g不为根节点，且g的父亲为黑色也节数，为红色就需要迭代向上调整，判断此时处于何种情况 具像图：
如果g的父亲为红，就迭代向上调整：cur = grandfather,grandfather = grandfather->parent
抽象图：抽象图中cur可能是新插入的节点，也可能是迭代调整上来的节点，这里g这棵子树每条路径黑色节点数是相同的，且调整后g这棵子树的每条路径黑色数相同且和之前一样。cur是parent的左孩子和右孩子是一样的，因为这里都是对颜色进行控制，和方向无关。
情况2： p为红色（g肯定是存在的且为黑），u不存在 操作： cur为parent的左孩子时，对g进行右单旋，然后将p的颜色改黑，g的颜色改红；cur为parent的右孩子时，先对p进行左单旋，然后对g进行右单旋，然后将cur的颜色改黑，g的颜色改红 具象图：此时cur一定为新增节点，因为g的右子树没有黑节点，所以cur的下面也不可能有黑节点 cur为parent的左孩子时 一条直线，此时进行右单旋
cur为parent的左孩子时 一条折线，此时进行左右双旋
上面的第二种情况可以先进行左单旋，然后交换cur和p，把折线变为直线，最后都执行直线的情况。 情况3： p为红色（g肯定是存在的且为黑），u存在且为黑 操作： 如果cur为parent的左孩子，对g进行右单旋，然后将p的颜色改为黑，g的颜色改为红；如果cur为parent的右孩子，先对p进行左单旋，对g进行右单旋，然后将cur的颜色改为黑，g的颜色改为红 解释： 假设此时a和b中黑色节点数为a，c的黑色节点数也一定为a，d和e的黑色节点数就是a-1，调整后cur和g的抽象图的黑色节点都是a，整体相等。 抽象图：此时cur一定为调整上来的节点，因为如果是新增节点的话，那么原来g这棵子树左右黑色节点数目不等，所以cur一定是调整上来的节点。 cur为parent的左孩子 一条直线，进行右单旋即可
cur为parent的右孩子 一条折线，此时进行左右双旋
和情况2一样，上面的第二种情况可以先进行左单旋，然后交换cur和p，把折线变为直线，最后都执行直线的情况。 总结： 上面就是p是g的左孩子的所有情形，为g的右孩子是与这个类似。还有注意的是根节点最后一定要改为黑色。 ????插入代码实现旋转代码如下： 这里就是上一篇博客的旋转代码，具体如下
插入代码实现如下：
????红黑树的删除????方法概述第一步： 先按照二叉搜索树删除节点的方式找到要删除节点（也可能是替代节点） 第二步： 然后为了不破坏红黑树的几条规则，要对节点的颜色进行相应地调整 ????调整颜色第一种情况： 删除节点（也可能是替代节点）（之后都叫delNode），如果该节点为红色，则直接删除退出即可，delNode没找到也可以直接退出 第二种情况： delNode为黑色（最多只有一个孩子且为红色，因为替代节点最多只有一个孩子），delNode有一个孩子时，删除delNode节点，然后把孩子节点的颜色改成黑色，也可直接结束 第三种情况： delNode为黑色，且没有孩子时，有下面几种情况（兄弟节点叫b(brother)，父亲节点叫p(parent)）（下面是cur是parent的左孩子的情形，右孩子的情形和它类似，不介绍）： 情况1： p为黑，b为红，两个孩子存在且一定为黑 操作： 对p进行左单旋，然后将p的颜色改成红，b的颜色改成黑 分析： 调整之前抽象三角形的黑色节点都是a，因为cur下面有一个节点要被删除，所以cur下面少了一个黑色节点，也就是p的左边少了一个黑色节点，调整后b两边的黑色节点数不变，cur下面黑色节点数还是少了一个，但是它的兄弟是黑色节点，后面可以通过对cur进行检索，使用其它情况解决这个问题。 抽象图：
情况2： p为红，b为黑，b的两个孩子存在且一定为黑 操作： 把p的颜色改成黑，b的颜色改成红 分析： 调整前，p左边少了一个黑色的节点，调整后，p的左边补上了一个黑色节点，且p的右边的黑色节点数不变，这里可以结束 抽象图：
情况3： p为黑色，且b为黑色，b的两个孩子为黑 操作： 把b的颜色改为红 分析： 调整之前，p左边是缺少一个黑色节点的，调整后，两边黑色节点数相同，但是此时p的右边也少了一个黑色节点，此时p的父亲g，g的右边是比左边多一个黑色节点的，所以需要迭代向上调整，把cur变成p，继续对cur进行检索 抽象图：
情况4： p为任意颜色，b的颜色为黑，b的右孩子为红色 操作： 对p进行左单旋，然后交换p和b的颜色，并把b的颜色改成黑 分析： 调整前，a和b的黑色节点数都是x，c,d,e的黑色节点个数为x+1，也就是p的左边少了一个黑色的节点，调整后，p两边的黑色节点都是x+1，b两边的黑色节点都是x+2，整体都调整好了，所以这里可以结束 抽象图：
情况5： p为任意颜色，b的颜色为黑，b的左孩子为红色 操作： 先对b进行右单旋，然后把b改红，bL改黑，然后对p进行左单旋，然后交换p和b的颜色，并把b的颜色改成黑（情况4） 分析： 和情况四其实是一样的，情况4的b和bR是直线，这里是折线，要通过右单旋变成直线，然后就转为情况4 抽象图：
总结： 删除就是以上几种情况，一般是左边少一个黑色节点，就靠右边补一个，结束，或者右边减少一个，然后两边整体少一个，对父亲节点进行检索。 ????删除代码实现代码实现如下：
????红黑树的查找这里比较简单，直接上代码：
????红黑树的验证这里通过递归计算出每条路径的节点个数来进行比较，同时验证其他的性质是否符合，从而验证是否红黑树：
实例演示：
代码运行结果如下：
????AVL树和红黑树的比较
总结： AVL树是严格意义上的平衡，红黑树是相对的平衡，两者都很高效，但后者用的更多，因为它旋转更是，实现相对简单，付出的代价少一点。 ????总结二叉搜索树的内容就介绍到这，接下来我会给大家介绍map和set两个容器，它们的底层就是红黑树，我会用红黑树给大家模拟实现它们。喜欢的话，欢迎点赞支持和关注~ |
2022-05-13
2022-03-10
2021-07-02
2021-08-14
2021-05-17
