红黑树

红黑树是一个二叉搜索树 ，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束， 红黑树保证最长路径不超过最短路径的二倍 ，因而 近似平衡 （最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：

1. 节点是红色或黑色
2. 根是黑色
3. 叶子节点（外部节点，空节点）都是黑色 ，这里的叶子节点指的是 最底层的空节点 （外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
4. 红色节点的子节点都是黑色 红色节点的父节点都是黑色 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

下面这颗树不是红黑树，因为加上叶子节点(null节点)后，不满足性质5 AVL是靠平衡因子来保持平衡的，比如平衡因子为1，那么左右子树的高度差就不能超过1，是一种强平衡。 对于红黑树而言，为何那5条性质，就能保证红黑树是平衡的？

• == 因为那5条性质，可以保证红黑树等价于4阶B树 ==

B树比较矮，它本身就是平衡的，高度越小越平衡。 红黑树就是能保证这个树高度不会特别高，红黑树的最大高度是 2 ∗ log2(n + 1) ，依然是 O(logn) 级别，因为高度不会很大进而维持一种相对平衡的状态。相比AVL树，红黑树的平衡标准比较宽松： 没有一条路径会大于其他路径的2倍 。 这是是一种弱平衡 、黑高度平衡（黑高度只算黑色节点个数，红黑树的任何一条路径的黑色节点数一样，则黑高度都是一样）。 9.1 AVL树 平衡标准比较严格：每个左右子树的高度差不超过1 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28） 搜索、添加、删除都是 O(logn) 复杂度 ， 其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整 9.2 红黑树 平衡标准比较宽松：没有一条路径会大于其他路径的2倍 最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40） 搜索、添加、删除都是 O(logn) 复杂度，其中 添加、删除都仅需 O(1) 次旋转调整 9.3 如何选择 搜索的次数远远大于插入和删除，选择AVL树 ； 搜索、插入、删除次数几乎差不多，选择红黑树 相对于AVL树来说，红黑树 牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作 ，整体来说性能要优于AVL树 红黑树的平均统计性能优于AVL树， 实际应用中更多选择使用红黑树