共计 4545 个字符，预计需要花费 12 分钟才能阅读完成。
红黑树
什么是红黑树
红黑树是一种常见的自均衡二分搜寻树，罕用于关联数组、字典，在各种语言的底层实现中被广泛应用。
满足红黑树的五个性质
- 每个节点是红色或者是彩色
- 根节点是彩色
- 每一个叶子节点（最初的空节点）是彩色
- 如果一个节点是红色的，那么它的孩子节点都是彩色的
- 从任意一个节点到叶子节点，通过的彩色节点是一样的
2- 3 树的定义
红黑树和 2 - 3 树有相似之处，咱们先理解一下什么是 2 - 3 树
满足二分搜寻树的根本性质，然而2- 3 树并不是二叉树
2- 3 树有两个节点，一个能够寄存 1 个元素，一个能够寄存 2 个元素
满足 2 - 3 树的三个性质
- 满足二叉搜寻树的性质
- 节点能够寄存一个或两个元素
- 每个节点有两个或三个子节点
每个节点都有 2 个子节点或者 3 个子节点，所以就叫做2- 3 树
右边节点都比 42 小，而左边节点都比 42 大，所以是满足二分搜寻树的性质。留神，13 和 33 这个节点两头是 18，是比 17 大同时比 33 小。
2- 3 树的相对平衡性
对于 2 - 3 树来说任意一个节点，左右子树的高度肯定是相等的，而相似像 AVL 这种均衡二叉树左右子树的高度相差不超过 1。
而 2 - 3 树是如何维持相对平衡性，就要从它的增加操作说起。
对于一颗空树咱们增加一个节点 42，他既是根节点也是叶子节点，这个时候如果咱们想再增加一个节点 37 应该增加到那里呢？
按均衡二叉树构造的逻辑来讲 37 比 42 小，所以增加到 42 的左孩子的地位。
然而在 2 - 3 树的中并不是这样的，
在 2 - 3 中咱们仍然是从根节点登程，请留神在 2 - 3 树中新的节点永远不会增加进空的地位
发现 42 节点的左子树为空，2- 3 树就会找到最初一个叶子节点上也就是 42 的地位，这时候 37 就会和 42 进行交融，从一个 2 节点变为了 3 节点。这个时候还是一颗相对均衡的二叉树。
如果这个时候咱们再增加一个 12 节点的话，因为 12 节点比 37 小，所以去找 37 的左孩子，然而咱们曾经晓得，37 的左孩子为空，而 2 - 3 并不会将新的节点增加到空的地位中去，这个时候咱们就会变成 4 节点！
然而在 2 - 3 中最多反对 3 个节点所以这个时候就会进行决裂，同时放弃相对均衡。
如果这个时候咱们再增加一个 18 节点，咱们能够很分明的晓得 18 会找到 12 节点然而 12 节点的子节点都为空，所以 18 就会和 12 节点进行交融。
如果这个时候咱们再增加一个 6 节点，大家很分明的晓得是会和 12 节点、18 节点进行交融，这个时候变成了 4 节点，所以要进行决裂成为下图这样。
然而！这样咱们就不是相对均衡的二叉树了！
这个时候就须要咱们 12 节点去找他的父节点，发现 12 的父节点 37 是一个 2 节点，这个时候就简略了，咱们只须要让 12 和 37 节点进行交融为 3 节点，而后让 6 变成 12 和 37 的左孩子，让 18 节点变成两头孩子节点即可！
这个时候咱们顺次退出 5 和 11 节点，就会变成下图这样。
因为不满足 2 - 3 树的性质，所以咱们还是将他们进行决裂。
然而这个时候又不是相对均衡了，所以咱们须要让 6 去找父亲节点，然而父亲节点曾经是 3 节点了，不过没关系，咱们照样把他交融进去成下图这样。
这个时候咱们须要进行决裂，咱们须要把 5 和 11 别离放在 6 的左孩子和右孩子的地位，37 也同理，造成下图这样。仍然放弃着相对平衡性。
其实咱们能够分为两种状况去了解，一种就是以后节点为 3 节点而父节点为 2 节点。
另一种就是以后节点为 3 节点，父节点也为 3 节点的状况。
红黑树和 2 - 3 树的等价性
在 2 - 3 树种，咱们能够示意 2 个节点和 3 个节点。
在红黑树中，咱们能够这样示意，而后用红色的线来示意 bc 是交融的，同时 b 是比 c 小的。因为红色节点是由 3 节点拆分而来，因而所有的红色节点都只会呈现在左子树上。
在下图中只有 6 和 17 和 66 是红色节点，咱们很容易得悉，因为他们都是 3 节点。
如果形象的话能够红色节点上移一下，咱们能够看到其实是和 2 - 3 树是一样的。
放弃根节点为彩色和左旋
在下图上，咱们晓得最初决裂当前，6 持续会向上进行交融，咱们晓得向上交融的节点肯定是红色的，所以咱们晓得 6 是红色的，但发现曾经没有父亲节点的时候，咱们将 6 变为彩色。
最开始的时候咱们想增加一个 42 的话，咱们间接让 42 当根节点就好了，而后咱们须要让 42 变为彩色节点。
这个时候咱们增加一个 37，能够间接放入到 42 左孩子的地位。
然而，如果咱们要插入的节点为根节点的右孩子的节点的时候，咱们须要进行左旋。
伪代码如下：
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = red;Java 代码如下：
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}色彩翻转和右旋
最开始的时候咱们想增加一个 42 的话，咱们间接让 42 当根节点就好了，而后咱们须要让 42 变为彩色节点。
这个时候咱们增加一个 37，能够间接放入到 42 左孩子的地位。
如果这时候咱们再向红黑树中退出 66 节点，会变成如下图这样。
相应的在 2 - 3 树中是这个样子。
在红黑树中红色节点的意思就是和父节点是交融在一起的。
而 37 和 66 都是红色节点，阐明它们都和父亲节点是交融在一起的。
在 2 - 3 树中，咱们解决 4 节点的时候会进行决裂，决裂为 3 个 2 节点。
然而在红黑树中其实彩色节点就是 2 个节点，咱们不须要进行旋转操作，咱们只须要让 37 和 66 进行变色为彩色，就和 2 - 3 树中节点的性质是一样的了。
在 2 - 3 树中，咱们须要持续让 42 节点向下来找父亲节点进行交融，相应的在红黑树中咱们只须要让 42 变为红色即可。
这个就是 色彩翻转（flipColors）
// 色彩翻转
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}另外一种状况就是，咱们树增加成这个样子。咱们增加了 12 节点，其实能够了解为它们是交融在一起的。在 2 - 3 树种就是 4 节点，而后将它进行决裂。
然而在红黑树中咱们怎么变成这个样子呢？其实很简略，咱们只须要进行右旋转即可。
为了不便了解，咱们引入 T1 和 T2 虚构节点来演示。
咱们将 x 的右节点 t1 放到 node 的左孩子上，而后将 node 放在 x 的右孩子的地位即可。
别忘了，在这个时候 node(42)节点其实是交融在 x(37)节点上的，所以它要改为红色，37 要改为彩色。
对应的伪代码：
node.left = t1;
x.right = node;
x.color = node.color;
node.color = red;最终咱们就能够失去和 2 - 3 树结构一样的红黑树了。
// node x
// / \ / \
// x T2 向右旋转 (y) y node
// / \ - - - - - - - -> / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}在红黑树中增加新元素
其实还有一种状况咱们在后面没有讲到，就是在下图中增加一个元素 40 应该怎么做。
依据二分搜寻树的性质，咱们会将 40 增加进 37 的右孩子的地位。
然而这个时候曾经毁坏了红黑树的性质，所以咱们须要进行左旋。
这个时候咱们还须要进行右旋。
而后咱们须要将 40 变彩色，42 变为红色。
最初咱们进行色彩翻转即可维持红黑树的性质。
总结图片如下：
如果咱们增加的第三个元素是最小的话，咱们能够间接从右旋开始。
反之咱们增加的如果是最大的元素，咱们能够间接进行色彩翻转。
// 判断节点 node 的色彩
private boolean isRed(Node node){if(node == null) {return BLACK;}
return node.color;
}
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
// 色彩翻转
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
// node x
// / \ / \
// x T2 向右旋转 (y) y node
// / \ - - - - - - - -> / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
// 向红黑树中增加新的元素(key, value)
public void add(K key, V value){root = add(root, key, value);
// 根节点为彩色
root.color = BLACK;
}
// 向以 node 为根的红黑树中插入元素(key, value)，递归算法
// 返回插入新节点后红黑树的根
private Node add(Node node, K key, V value){if(node == null){
size ++;
return new Node(key, value); // 默认插入红色节点
}
if(key.compareTo(node.key) < 0) {node.left = add(node.left, key, value);
} else if(key.compareTo(node.key) > 0) {node.right = add(node.right, key, value);
} else // key.compareTo(node.key) == 0
{node.value = value;}
// 右孩子为红色，左孩子为彩色，进行左旋
if(isRed(node.right) && !isRed(node.left)){node = leftRotate(node);
}
// 左孩子为红色，并且左孩子的左孩子也是红色，进行右旋
if(isRed(node.left) && isRed(node.left.left)){node = rightRotate(node);
}
// 色彩翻转
if(isRed(node.left) && isRed(node.right)){flipColors(node);
}
return node;
}工夫复杂度剖析
红黑树相比于 AVL 树，其实是就义了平衡性的，红黑树并不齐全满足均衡二叉树的定义，红黑树的最大高度达到了 2logn 的高度，红色节点影响了红黑树的的平衡性。红黑树尽管就义了肯定的查问性能，然而在增删改操作的性能失去了补救，红黑树的综合性能还是要优于 AVL 树的。
