[TOC] ## 概述 红黑树，Red-Black Tree，是一种自平衡（大致平衡）二叉查找树。红黑树在进行插入和删除时通过特定操作保持二叉树的平衡，从而获得较高的查找性能。 &nbsp; 红黑树具有以下五个特性： **1. 节点是红色或黑色。 2. 根是黑色。 3. 所有叶子都是黑色（叶子是NIL节点）。 4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。） 5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。** &nbsp; 下面是一个具体的红黑树实例：  &nbsp; 通过以上约束强制了红黑树的关键性质：**从根到叶子的最长的可能路径不多余最短的可能路径的两倍长**。结果是这个树大致上是平衡的，插入、删除、查找操作的最坏情况都与树的高度成比例，不会出现二叉查找树中左右子树极度不平衡的情况。 &nbsp; 再来解释一下为什么"从根到叶子的最长的可能路径不多余最短的可能路径的两倍长"？ 根据性质4和性质5，红黑树中最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点，并且最短路径和最长路径有相同数量的黑色节点，这就表明了最长的可能路径不多余最短的可能路径的两倍长。 <br/> ## 红黑树的操作 ### 红黑树的插入 红黑树的插入操作可以分成两步来理解： 1. 先把新节点挂到红黑树相应位置上。 2. 调整红黑树，使其满足红黑树的5个性质。 第一步比较简单，从根节点开始，按二叉查找树左子小右子大的规则找到插入位置就可以了。我们重点考虑另外一个问题，新插入节点是否会破坏红黑树的平衡（不满足红黑树的5个性质），还有如何恢复平衡？ &nbsp; 新增节点或删除节点之后，红黑树为了恢复平衡，有两大操作： * **recolor 重新标记颜色** * **rotation 旋转** 先尝试 recolor，如果 recolor 不能达到红黑树的5点要求，接着尝试 rotation。弄清楚 recolor 和 rotation 的规则也是掌握红黑树的关键，接下来看看红黑树中插入新节点X的逻辑： 1. **将新插入的节点X标记为红色。（因为标记为红色不会破坏性质5）** 2. **如果X是根节点root，标记为黑色。** 3. **如果X的父节点是黑色。这种情况不会破坏红黑树的特性，不需要处理。** 4. **如果X的父节点是红色：** 4.1 **如果X的叔父节点也是红色：** 4.1.1. **将父节点和叔父节点都标记为黑色。** 4.1.2. **将祖父节点标记为红色** 4.1.3. **然后对X的祖父节点重复步骤2、3。**  上面几种情况都是 recolor 操作，也就是父节点和叔父节点同为红色的情况下应该执行的操作。下面来看一下旋转操作： &nbsp; 4.2. **如果X的叔父节点是黑色，要分4种情况处理：** 4.2.1. **左左：P是G的左节点，且X是P的左节点** 对G节点执行右旋操作，之后交换 P、G 颜色。  &nbsp; 4.2.2. **左右（P是G的左节点，且X是P的右节点）** 先对P节点执行左旋，用X节点替换P节点，然后再应用左左情况。  &nbsp; 4.2.3. **右右（P是G的右节点，且X是P的右节点）** 对G节点执行左旋操作，之后交换 P、G 颜色。  &nbsp; 4.2.4. **右左（P是G的右节点，且X是P的左节点）** 先对P节点执行右旋操作，用X节点替换P节点，然后再应用右右情况  <br/> ### 红黑树的删除 为了容易理解，先列一下红黑树删除的大体思路： 1. 删除节点： 1.1 如果要删除的节点没有子节点，直接删除节点。 1.2 如果要删除的节点有一个子节点，删除节点之后，用子节点顶替上来。 1.3 如果要删除的节点有两个子节点，那么问题可以被转化成删除另一个只有一个子节点的节点。就是回到了上面1.2这种情况，具体怎么转化后面会讲。 2. 删除节点之后，调整红黑树，使其满足红黑树的5个性质。 先看这个问题"如果要删除的节点有两个子节点，那么问题可以被转化成删除另一个只有一个子节点的节点"。 &nbsp; 在删除带有两个子节点的节点的时候，我们要么找到它左子树中的最大元素、要么找到它右子树中的最小元素，并把它的值复制到要删除的节点中（不复制颜色），接着去删除我们从中复制出值的那个节点，它必定只有一个子节点或没有子节点（因为它是最大或最小元素，不可能有两个子节点）。不好理解就直接看图：  图中实例使用的是左子树的最大元素6来代替8，实际上，找右子树的最小值也是可以的，两者选其一即可。 &nbsp; 接着，**怎么删除有一个子节点的节点呢？**假设要删除节点X，子节点是N。 1. **X是红色节点，删除X之后用N顶替，仅仅是少了一个红色节点，不会破坏红黑树的性质。**  &nbsp; 2. **X是黑色节点：** 2.1 **子节点N是红色。** 删除X之后用N顶替。由于经过N的路径上少了个黑色节点，所以要把N改成黑色。  &nbsp; 2.2 **子节点N也是黑色：** &nbsp;&nbsp;&nbsp;&nbsp;2.2.1 **节点X是树根。** &nbsp;&nbsp;&nbsp;&nbsp;N成为新根，在所有路径上少了个黑色节点，然后又出现一个黑色的新根，所以保持了红黑树的性质。 &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.2 **节点S是红色。** &nbsp;&nbsp;&nbsp;&nbsp;在节点P上做左旋，接着互换P节点和S节点的颜色，之后按后面的2.2.4、2.2.5、2.2.6来处理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.3 **节点P、节点S、S的子节点都是黑色。** &nbsp;&nbsp;&nbsp;&nbsp;直接把节点S改成红色，之后按2.2.2来处理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.4 **节点P是红色，节点S和S的子节点都是黑色。** &nbsp;&nbsp;&nbsp;&nbsp;交换节点P和节点S的颜色，经过S的路径上黑色节点保持不变，经过N的路径上新增了一个黑色节点，正好填补已删除的黑色节点。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.5 **节点S是黑色，S的左子节点是红色，S的右子节点是黑色，并且N是它父节点的左子节点。** &nbsp;&nbsp;&nbsp;&nbsp;在节点S上右旋，交换节点L和节点S的颜色，之后按2.2.6处理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.6 **节点S是黑色，S的右子节点是红色，并且N是它父节点的左子节点。** &nbsp;&nbsp;&nbsp;&nbsp;在P节点上做左旋，接着交换节点P和节点S的颜色，并把节点R改成黑色，这样，经过节点N的路径、经过L的路径、经过R的路径上的黑色数目与原来保持一致了。  &nbsp; 以上就是红黑树的删除操作，多处都涉及到了递归逻辑，所以稍微难懂一点。结合图例多看几遍还是能看懂的。