杀无赦！斩了 Java 拦路虎之红黑树篇

它是一种查找次数小于等于树高的数据结构。如图中树有 4 层，即树高为 4，当我们需要查找 8 时，经过的路线是这样的：

1、8<9，往左查找

2、8>5，往右查找

3、8>7，往右查找

4、8=8，找到结果

总共查找 4 次，等于树高。这棵树不管怎么找，查找次数总是小于等于树高。

二叉树的插入同样遵循上述规则，会一步一步对比，从而找到插入的位置，可以想象上图中的 8 不存在，而是需要插入一个 8，结果与上述路线一致。

二叉树的删除会涉及到无子节点和有子节点两种情况，无子节点直接删除即可，有子节点会需要用左边最大值或右边最小值替换当前删除节点，具体不细聊。

当二叉树插入数值不均衡时，会出现树结构的变形与查找性能的损耗，比如现在二叉树有 8，9，12 三个值，然后需要插入 7，6，5，4，3 这五个值时，产生的结构如下图所示。

树高会不合理的增高，查找效率也无法得到保证。红黑树就是为了解决这种情况而诞生的。

红黑树又称为自平衡二叉树，它符合二叉树的规则同时比它的规则更加的复杂，具体规则如下：

1、所有节点都是红色或黑色

2、根节点为黑色

3、所有叶子都是黑色(NIL 节点)

4、每个红色节点必须

【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

有两个黑色的子节点。（不能有两个连续的红色节点。）

5、从任一节点到其每个叶子的所有简单路径(不要回退)都包含相同数目的黑色节点。

具体样子如下图所示：

解释一下几个规则的含义：

1，2 很好理解，节点都是红和黑，根节点是黑色的。

3 所有叶子都是黑色的，叶子与叶子节点是两个概念，叶子不是一个节点，可以理解为没有数值的空节点，也就是图中的 NIL。

4 也很好理解，红色节点的子节点都是黑色的，这就保证了没有两个连续的红色节点。

5 稍微解释一下，简单路径就是说一次到底，不要回退，叶子就是 NIL，比如从 8 这个节点出发，不管是去 1 下面的叶子，11 下面的叶子，还是 6 下面的叶子，都是经过一个黑色节点，从任何节点出发都是一样的规则，经过相同数量的黑色节点。

以上 5 个规则，加上二叉树的规则，就组成了红黑树这一极具特点的树型数据结构。

红黑树的查找与二叉树类似，都是查找次数小于等于树高，但红黑树由于平衡的规则会使树高相对平衡，不会出现某条路径远远大于其他路径的情况。

红黑树的插入较为复杂，有时为了维持规则需要做结构的调整，常用的调整手段是改变颜色、左旋转和右旋转。由于规则 5，如果插入的值为黑色节点，会导致黑色节点数量很难相同，所以默认每次插入的值都为红色节点。和二叉树一样，通过对比找到插入的位置，默认插入一个红色节点的数值，这里会分为很多情况，大概列举如下：