摘要
红黑树是数据结构中重要的一种结构，其本质是通过定义一些性质，让二叉树分布结构变的相对合理，并在动态添加或者删除的过程中去修复结构。红黑树在搜索、添加、删除这 3 种操作的效率相对比较均衡，所以有很多实际的应用场景。
红黑树是一种自平衡的二叉搜索树，是一种重要的数据结构，后面的集合、映射等数据结构，都可以从这基础上去搭建。同时也是内容和逻辑比较多的数据结构，需要多花费一些精力去学习它。
红黑树有 5 条性质，凡是满足这 5 条，才能称为红黑树，这 5 条性质有：
1、 节点必须是RED或者BLACK，也可以理解为存在一个Boolean的标志，不是false就是ture；
2、 根节点是BLACK；
3、 叶子节点都是BLACK，这里要特别留意，叶子节点存在两个空节点，只有一个子树的节点，另外一个不存在的子树也是一个空节点；
4、 RED节点的子节点都是BLACK，RED节点的父节点也都是BLACK保证**从根节点到叶子节点的所有路径上，不会出现2个连续的RED节点；
5、 从任意一个节点到叶子节点的所有路径上包含的BLACK节点数量相同；
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eLaOobUI-1640349225584)(https://cdn.jsdelivr.net/gh/shPisces/writing_pic/img/RBT-image1.png)]
注意：如上图的红黑树，必须是要有 null（空节点）节点。后面的示例图中省略，节省作图时间，但一定要有。
为什么满足这 5 条性质，就能保证平衡呢？
先来温习一个平衡的标准，参照 AVL 树中的定义，节点的左右子树的高度差要不大于 1，即是平衡的。
红黑树在满足上面的 5 条性质之后，第 5 条性质中说明 BLACK 节点数量相关也就可以推断出节点的左右子树高度差是不大于 1 的（考虑到空节点，所以有可能是 1）。
红黑树与 4 阶 B 树
看红黑树中，黑色节点和它的左右子节点合并就变成 4 阶 B 树。红黑树的黑色节点和 4 阶 B 树的节点数量也是一样多的。一般情况都是这样，还有其他的特殊情况。如下图：
辅助准备
在开始红黑树之前，先定义一些属性和函数，帮助实现红黑树的代码。
先要给节点（下面统称 node）添加一些判断与其他 node 的关系函数。
- parent：父节点，在 node 的结构中已经定义父节点的属性
- sibling：兄弟节点，若 node 是 parent 的 left，兄弟节点就是 parent 的 right
public Node<E> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
- uncle：叔父节点，就是 parent 的兄弟节点。
- grand：祖父节点，就是 parent 的父节点
写下来，先实现一些处理红黑树节点的函数（比如看节点的颜色等）。在这之前，需要提前全局定义两个值，用 Boolean 值来定义RED 和 BLACK。
private static final boolean RED = false;
private static final boolean BLACK = true;
- 染色，把 node 上色：
private Node<E> color(Node<E> node, boolean color) {
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}
- 染成红色：
private Node<E> red(Node<E> node) {
return color(node, RED);
}
- 染成黑色：
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
- 获取 node 的颜色：
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>)node).color;
}
- 是否是红色：
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
- 是否是黑色：
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
添加和删除
红黑树的添加和删除和 AVL 树的添加和删除的原则大致一样，即添加元素都是添加称为叶子节点，删除元素的时候就要区分删除的是叶子节点还是非叶子节点。
在添加或者删除元素之后，要判断当前树是否依然符合红黑树的 5 条性质，若不符合就要做恢复为红黑树的操作。这就是红黑树的重点，内容很多，后面文章专门分析添加和删除处理。
AVL 树和红黑树
AVL 树的平衡标准比较严格，即一个节点的左右子树的高度差不能超过 1，搜索、添加和删除操作都是 O(logn)，添加元素只需要 O(1) 次旋转，删除元素最多需要 O(logn) 次旋转。
红黑树是比较宽松的，没有一条路径的节点数量会大于其他路径节点数量的 2 倍。搜索、添加和删除操作都是 O(logn)，添加或者删除元素都只需要 O(1) 次的旋转。
因为AVL 树的平衡标准比红黑树要高，所以在搜索方面，AVL 树的效率也是比红黑树大。但是在添加或者删除后需要旋转的次数比红黑树要多。这就可以总结出搜索次数远远大于插入和删除时，选择 AVL 树；搜索、插入、删除的次数都差不多，可以选择红黑树。
在实际应用中，选择更多的是红黑树，因为应用红黑树统计的平均性能要比 AVL 好一些。