为什么会出现红黑树？
之前我们提过AVL树-自平衡的二叉搜索树，但是一旦树的节点发生变化，AVL树为了维持绝对平衡（虽然说AVL也容忍左右两个子树最多为1的高度差，但这里仍视为绝对平衡），需要频繁地进行旋转操作。那么一旦我们插入、删除操作比例相较查询操作变多的时候，AVL树的效率就显得较为低下了。
红黑树的定义
首先，红黑树是一个二叉搜索树，它同时满足以下特性：
- 每个节点要么是黑色，要么是红色
- 根节点是黑色
- 如果节点是红色的，那么它的子节点必须是黑色的（反之，不一定需要成立）
- 从根节点到叶节点或空子节点的每条路径，都包含相同数目的黑色节点（我们将空子节点记为黑色的）
红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍。
最长路径等于最短路径的2倍的极限情况：最长路径为红黑相间，最短路径为全黑。
红黑树的变换操作
红黑树除根节点外所有插入的点默认为红色。
为了维持一棵红黑树，有三种变换操作。
改变颜色
红色节点变为黑色节点，黑色节点变为红色节点。
左旋
和AVL树一样，以中间结点为轴，中间结点的左子节点变为原根节点的右子节点，再以中间结点为根节点，把原根节点连到左子节点上。
右旋
和左旋类似的操作
红黑树的操作
插入
变颜色的情况
要插入的位置的父节点是红色，且父节点的兄弟节点也是红色，则：
- 把父节点和父节点的兄弟节点设为黑色
- 把父节点的父节点(祖父节点)设为红色(如果祖父节点是根节点，不能变颜色)
- 定位到父节点的父节点，分析下一步的变换规则
我们看下面这个例子，插入6这个节点，出现两个红色节点上下相邻，开始变颜色，将7、13变为黑色，12变为红色，并定位到12，分析接下来要进行的操作。
旋转的情况
非常类似AVL，一旦变完颜色还出现红色的节点相邻，进行旋转操作。
- 折线式失衡（博主自己想出来的概念），双旋
我们继续上面那张图的例子，定位到12后，发现仍然出现上下两个红色节点相邻，此时5-12-7-6形成折线式失衡，和AVL的方法一样先左旋再右旋。
注意右旋后原根节点要变为红色，新根节点变为黑色。
- 直线式失衡，单旋
直线式失衡就只是单独进行左旋或右旋。旋转完成后也要进行原根节点要变为红色，新根节点变为黑色的操作。
（旋转后的变颜色实质就是维护从根节点到叶节点或空子节点的每条路径，都包含相同数目的黑色节点的性质）
删除
删除操作类似二叉查找树的删除，但删除之后若不满足一棵红黑树的性质则使用一系列着色操作来重新让它成为一棵红黑树。
具体操作参考目前最详细的红黑树原理分析（大量图片+过程推导！！！）_Y先森0.0-CSDN博客
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%bc%b1%e5%b9%b3%e8%a1%a1%e7%9a%84%e4%ba%8c%e5%8f%89%e6%9f%a5%e6%89%be%e6%a0%91-%e7%ba%a2%e9%bb%91%e6%a0%91/
