AVL树 是高度平衡的二叉搜索树，使用它主要是为了方便查找，以及减少查询次数，但如果我们添加和删除的次数比较多的时候，使用他显然就不合适了，因为他频繁的旋转增加了算法的时间复杂度，这个时候我们就可以使用另外一种树就是红黑树，红黑树也会旋转但不会像 AVL树 那么频繁。红黑树有 5 个重要的性质。
- 节点是红色或黑色。
- 根节点是黑色。
- 所有叶子都是黑色。（叶子是null节点）
- 从根节点到所有的叶子节点的路径上不能有两个连续的红色节点。
- 从任一节点到其每个叶子的路径都包含相同数目的黑色节点。
其中第 3 条如果不理解，基本上是搞不懂红黑树的，他说的叶子不是二叉树中定义的叶子节点，是一种空的节点，他意思告诉我们任一节点如果只有一个子节点，那么该节点也是有两条路径的，这样就限制了另一条路径的长度。其实也在变相的告诉我们红黑树中如果一个节点只有一个子节点，那么这个子节点必定是红色的，结合第 4 和第 5 条就明白了。
红黑树中根到叶子的所有路径中，最长路径不会超过最短路径的两倍。我们可以反证一下，假设超过两倍会怎么样？比如最短路径长度是 a，最长路径长度是 2a+1 。根据性质 4 ，路径上不能有两个连续的红色节点，即便最短路径上全部都是黑色节点，那么在最长路径上也会有 a+1 个红色节点，因为根节点是黑色的，也就是说在剩下的 a-1 个黑色节点之间插入 a+1 个红色的节点，并且红色节点不能有连续的，无论如何也是做不到的，所以最长路径不可能超过最短路径的两倍。
红黑树的插入：
红黑树也是一棵二叉搜索树，他的查找，插入和删除我们可以参照前面讲的二叉搜索树和 AVL树 ，不过在插入和删除之后有可能打破树的平衡，所以在插入和删除之后还需要进行调整，我们先来看下红黑树插入的调整。
如果插入的是黑色节点，根据红黑树的性质 5 ，肯定会破坏这一规则，所以这里插入的节点都是红色的。但插入红色节点有可能会打破坏性质 4 ，也有可能不会。如果没有破坏就不需要调整，如果破坏我们在调整。下面来分别讨论插入遇到的几种情况，为了方便描述，我们把父节点的父节点称为爷爷节点，和父节点有共同父节点的称为叔叔节点。插入之后主要涉及涂色和旋转，这里只讨论插入节点的父节点是他爷爷的左子节点，如果是右子节点就不在介绍，因为原理都一样，就是左旋和右旋的区别。
1，插入的是根节点。
如果插入的是根节点，直接把它涂黑然后返回即可。
2，如果插入节点的父节点是黑色。
因为插入的节点是红色，如果插入节点的父节点是黑色，没有破坏任何一条性质，不需要做任何调整。
3.1，如果插入节点的父节点是红色，叔叔节点也是红色。
因为插入的节点是红色，父节点也是红色，所以破坏了性质 4 ，需要把父节点涂成黑色。因为父节点之前是红色的，所以他肯定不是根节点，插入的节点肯定有爷爷节点，并且爷爷节点一定是黑色的。把父节点涂成黑色之后，经过父节点的这条路径就多了一个黑色节点，根据性质 5 ，需要把爷爷节点涂成红色，但这样叔叔节点这条路径上少了一个黑色节点，所以还需要把叔叔节点涂成黑色。如果爷爷节点是根节点，还需要把它涂成黑色（根节点是黑色的），否则爷爷的父节点如果也是红色，就破坏了性质 4 ，需要继续往上判断，如下图所示。
总结：把父节点和叔叔节点涂成黑色，爷爷节点涂成红色，继续往上判断爷爷节点。
3.2，如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左子节点。
这种情况下也是先把父节点涂成黑色，因为父节点变成黑色之后，经过父节点的这条路径上就多了一个黑色节点，所以还需要把爷爷节点涂成红色。那么这里有个疑问，叔叔节点怎么处理？有的同学可能会说像 3.1 那样把叔叔节点也涂成黑色不就行了。其实这样是不行的，主要有两点，第一如果叔叔节点是空的怎么办，因为根据性质 3 ，空节点也是黑色的，所以这样就没法涂了。第二如果叔叔节点不是空，那么他就是从 3.1 转化过来的（ 3.1 涂完之后会继续往上判断），这种情况下他本来就是黑色的，你在把它涂成黑色相当于没涂。既然不能改变叔叔节点的颜色，那么叔叔节点这条路径就比父节点这条路径少了一个黑色节点（因为爷爷节点变红了，叔叔节点这条路径就少了一个黑色的），唯一的解决方式就是对爷爷节点进行右旋，让父节点成为这棵子树的根节点，那么这个父节点黑色的个数就可以被他的两棵子树共享了，如下图所示。
总结： 父节点涂黑，爷爷节点涂红，对爷爷节点右旋，因为父节点已经变黑了就不在继续判断。
3.3，如果插入节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的右子节点。
这种情况下和 3.2 中讲的类似，如果我们对爷爷节点进行右旋的话，会导致一条路径缺少了一个黑色节点，如下图所示。注意这里大家可能会有疑惑，插入的 X 节点怎么会有子节点？实际上这里的 X 节点有可能是插入的也有可能是 3.1 往上调整得到的，我们要放在一起看。
很明显直接对爷爷节点旋转是不行的，那该怎么办呢？其实我们可以对 X 的父节点进行左旋，就变成 3.2 中介绍的那样了，后面的就按照 3.2 中的那样处理就行了，如下图所示。
总结： 让 X 节点指向父节点，对 X 节点左旋，后面参照 3.2 。
4.1，如果插入节点的父节点是红色，父节点是爷爷节点的右子节点。
这里也分几种情况，和上面类似，只不过是左旋和右旋的区别，这里就不在介绍。最后来看下代码。
// 如果是空节点就返回黑色。
private static <K, V> boolean colorOf(TreeMap.Entry<K, V> p) {
return (p == null ? BLACK : p.color);
}
// 对插入元素的调整。
private void fixAfterInsertion(TreeMap.Entry<K, V> x) {
x.color = RED;// 插入节点是红色的。
// 只有父节点不为空且是红色才会操作。
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// 父节点是爷爷的左子节点。
// y 是叔叔节点。
TreeMap.Entry<K, V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {// 叔叔节点是红色，参考3.1。
setColor(parentOf(x), BLACK);// 父节点涂黑。
setColor(y, BLACK);// 叔叔节点也涂黑。
setColor(parentOf(parentOf(x)), RED);// 爷爷节点涂红。
x = parentOf(parentOf(x));// 继续往上判断爷爷节点。
} else {
// 当前节点是父节点的右子节点，参考3.3。
if (x == rightOf(parentOf(x))) {
x = parentOf(x);// X节点指向父节点。
rotateLeft(x);// 对父节点左旋，变成 3.2。
}
// 参考3.2。
setColor(parentOf(x), BLACK);// 父节点涂黑。
setColor(parentOf(parentOf(x)), RED);// 爷爷节点涂红。
rotateRight(parentOf(parentOf(x)));// 对爷爷节点右旋。
}
} else {
// 父节点是爷爷的右子节点，和上面类似。
TreeMap.Entry<K, V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 最后把根节点变成黑色。
root.color = BLACK;
}
红黑树的删除：
删除操作可以参考 AVL树 的删除，我们也可以看下，这是红黑树 TreeMap 中的源码。
private void deleteEntry(TreeMap.Entry<K, V> p) {
modCount++;
size--;
// 如果 p 有两个子节点，找到他的后继节点，移形换位。
if (p.left != null && p.right != null) {
// 查找 p 的后继节点 s。
TreeMap.Entry<K, V> s = successor(p);
// 把 s 的值赋值给 p ，相当于删除 s。
p.key = s.key;
p.value = s.value;
p = s;// p 用 s 替换。
} // p has 2 children
// replacement 是 p 的子节点，p 最多只有一个子节点。
TreeMap.Entry<K, V> replacement = (p.left != null ? p.left : p.right);
// 判断 p 是不是叶子节点。
if (replacement != null) {
// p 不是叶子节点，先删除 p 节点。
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
// 如果删除的是黑色节点才调整，replacement节点必定是红色的。
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // p 是根节点。
root = null;
} else { // p 是叶子节点。
if (p.color == BLACK)// p 是黑色才会调整。
fixAfterDeletion(p);
// 删除 p 节点。
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
如果 p 有两个子节点，删除的时候不是直接删除 p 节点，而是用 p 的后继节点来替换 p 节点，然后删除 p 的后继节点。所以删除的节点要么是叶子节点要么只有一个子节点，不可能有两个子节点。我们看到上面代码中如果 p 的后继节点是叶子节点，是先调整 p 节点然后在删除，如果不是叶子节点，是先删除 p 节点然后在调整 replacement ，这里为什么不都是调整完之后在删除呢？这是因为删除调整的节点必须是黑色的，如果 p 不是叶子节点，他就只能有一个子节点 replacement，根据红黑树性质这个子节点必定是红色的，所以如果先把 p 节点删除，调整 replacement 节点的时候直接把它变成黑色，不需要做任何其他变色和旋转操作，简单省事。
private void fixAfterDeletion(TreeMap.Entry<K, V> x) {
while (x != root && colorOf(x) == BLACK) {// 是黑色才会调整。
if (x == leftOf(parentOf(x))) {
// ……
} else { // symmetric
// ……
}
}
setColor(x, BLACK);
}
fixAfterDeletion 函数到底是调整 p 节点还是调整 p 的子节点，我们不需要管，只需要记住在调整的这个节点的路径上少了一个黑色节点即可，有兴趣的大家可以自己看，这里就不带大家逐步分析了。
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
