共计 5210 个字符，预计需要花费 14 分钟才能阅读完成。
2-3树
在理解红黑树之前，咱们先来意识 2 - 3 树，在算法里也是先从 2 - 3 树切入到红黑树的。并且理解 2 - 3 树对于了解 B 类树也会有帮忙，因为 2 - 3 树能够说就是根底的 B 类树。
2-3树的个性：
- 满足二分搜寻树的根本性质
- 节点能够寄存一个元素或者两个元素，或者说数据项
- 每个节点有 2 个或者 3 个子节点，这也是 2 - 3 树的名称由来
- 2- 3 树是一棵相对均衡的树，对于任意节点的左右子树的高度肯定是相等的
2- 3 树为了维持相对均衡，须要满足以下条件：
- 2 节点有且只能有两个子节点，并只能蕴含一个数据项
- 3 节点有且只能有三个子节点，并只能蕴含两个数据项，大小关系从左至右顺次递增
- 增加数据项时不能将该数据项增加到一个空节点上，因为新的节点只能通过决裂或者交融产生
- 当 2 - 3 树只有 2 节点的时候，其只能是一棵满二叉树
2- 3 树的两类节点：
- 能够看到，2 节点有两个子节点，5 和 15，且本身只蕴含一个数据项，即 10。3 节点则有三个子节点，本身只能蕴含两个数据项，从左至右顺次递增：5 < 6 < 7 < 8 < 9
下图是一颗残缺的 2 - 3 树：
从上图中能够看到 2 - 3 树是满足二分搜寻树的根本性质的，只有两个节点的状况，如 42 这个节点，右子节点小于父节点，左子节点大于父节点。而有三个节点时，右子节点依然小于父节点，两头的子节点大于父节点的左数据项，小于父节点的右数据项（如图中 18 大于 17，小于 33），左子节点则大于父节点。
2-3树的相对平衡性
之前咱们提到了 2 - 3 树插入节点时不能将该节点插入到一个空节点上，新的节点只能通过决裂或者交融产生。咱们晓得对二分搜寻树顺次增加有序的数据时，如顺次增加 1、2、3、4、5，会产生间断的节点，使得二分搜寻树进化成链表。
为了防止进化成链表，具备均衡个性的树状构造，会采取一些伎俩来维持树的均衡，例如 AVL 是通过旋转节点，而 2 - 3 树则是通过决裂和交融。当咱们顺次增加 1、2、3、4、5 到 2 - 3 树时，其流程如下：
- 增加元素 1，创立一个 2 节点类型的根节点
- 增加元素 2，此时元素 1 和 2 存在同一个节点中，成为一个 3 节点。为什么增加元素 2 时，不能生成一个新的节点作为元素 1 所在节点的右子节点呢？因为“增加数据项时不能将该数据项增加到一个空节点上，新的节点只能通过决裂或者交融产生”
- 增加元素 3，元素 1、2、3，临时存在同一个节点中，造成一个 4 节点
- 决裂，2- 3 树中最多只有 3 节点，不能存在 4 节点，所以临时造成的 4 节点要进行决裂，将两头的元素作为根节点，左右两个元素各为其左右子节点。这时可见造成了一棵满二叉树
- 增加元素 4，依据元素的大小关系，将会寄存到元素 3 所在的节点。因为新增加的元素不能增加到一个空节点上，所以元素 4 将依据搜寻树的性质找到最初一个节点与其交融。即元素 3 和 4 将交融为一个三节点。并且依据大小关系元素 4 要位于元素 3 的右侧
- 增加元素 5，同插入元素 4，元素 5 一路查找到元素 3、4 所在的三节点，与其交融，临时造成一个 4 节点
- 决裂，元素 3、4、5 所在的 4 节点同下面元素 1、2、3 造成的 4 节点一样，进行决裂操作。依据大小关系，4 元素将会作为根节点，元素 3、5 则各为其左右子节点
- 交融，后面的决裂操作曾经导致该 2 - 3 树不满足其第四条性质“当 2 - 3 树只有 2 节点的时候，其只能是一棵满二叉树”，所以该 2 - 3 树将要向上交融以满足 2 - 3 树的性质。咱们只须要将元素 4 所在节点与其父节点即元素 2 所在的节点进行交融即可。这时，元素 2、4 就造成了一个 3 节点
如果咱们持续往 2 - 3 树中增加元素 6 和 7，那么最终造成的 2 - 3 树如下图所示：
如果在这个案例中咱们应用的是二分搜寻树，那么该二分搜寻树将会进化为一个链表，而 2 - 3 树则通过决裂、交融的形式成为了一颗满二叉树。
红黑树与 2-3 树的等价性
理解了 2 - 3 树后，咱们来看下红黑树与 2 - 3 树的等价性，严格来说是左倾红黑树才是与 2 - 3 树是等价的。与 2 - 3 树一样，红黑树具备二分搜寻树的性质，并且也是自均衡的，但不是相对均衡，甚至平衡性比 AVL 树还要差一些。
之前提到了 2 - 3 树是相对均衡的，对于任意节点的左右子树的高度肯定是相等的。而 AVL 树则是任意节点的左右子树高度相差不超过 1 即可，属于高度均衡的二分搜寻树。
红黑树则是从根节点到叶子节点的最长门路不超过最短门路的 2 倍，其高度仅仅只会比 AVL 树高度大一倍，所以在性能上，降落得并不多。因为红黑树也是自均衡的树，也会采取一些机制来维持树的均衡。
红黑树的定义：
- 每个节点或者是红色的，或者是彩色的
- 根节点是彩色的
- 每一个叶子节点（最初的空节点）是彩色的
- 如果一个节点是红色的，那么它的左右子节点都是彩色的
- 从任意一个节点到叶子节点，通过的彩色节点是一样的
这里的第三点要求“每一个叶子节点（最初的空节点）是彩色的”，略微有些奇怪，它次要是为了简化红黑树的代码实现而设置的。咱们也能够了解为，只有是空的节点，它就是彩色的。
在理解了 2 - 3 树之后，咱们晓得 2 - 3 树是通过决裂和交融来产生新的节点并维持均衡的。2- 3 树有两类节点，2 节点和 3 节点。除此之外，还会有一种长期的 4 节点。接下来咱们看看 2 - 3 树向红黑树转换的过程，下图展现了 2 - 3 树的这三种节点对应于红黑树的节点：
- 2 节点：对应于红黑树的彩色节点
- 3 节点：对应于红黑树中彩色的父节点和红色的左子节点
- 长期的 4 节点：对应于红色的父节点和彩色的左右子节点。这里须要说一下，为什么是红色的父节点而不是彩色的呢？次要是因为 2 - 3 树的 3 节点须要将决裂后的父节点进行向上交融，红色的合乎咱们向红黑树中插入任何一个节点默认都是红色的实现形式。如果该父节点是红黑树的根节点的话，那它必定须要变色，这一点就不属于 2 - 3 树向红黑树的变换规定了，而属于红黑树的性质。
依据这个对应关系，咱们将这样一颗 2 - 3 树：
转换成红黑树，就是这样子的，能够看到其中的红色节点都对应着 2 - 3 树的 3 节点：
如果这样看着不太好对应的话，咱们也能够将其绘制成这个样子，就更容易了解红黑树与 2 - 3 树是等价的了：
从 2 - 3 树过渡到红黑树后，接下来，咱们就着手实现一个红黑树。首先，编写红黑树的友链交易根底构造代码，如节点定义等。具体代码如下所示：
package tree;
/**
* _红黑树_
*
* @author 01
* @date 2021-01-22
**/
public class RBTree<K extends Comparable<K>, V> {
/**
* _因为只有红色和彩色，这里用两个常量来示意_
*/
private static final boolean RED = true;
private static final boolean BLACK = false;
/**
* _定义红黑树的节点构造_
*/
private class Node {
public K key;
public V value;
public Node left, right;
// _示意节点是红色还是彩色_
public boolean color;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
// _默认新节点都是红色_
color = RED;
}
}
/**
* _根节点_
*/
private Node root;
/**
* _红黑树中的元素个数_
*/
private int size;
public RBTree() {
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* _判断节点__node__的色彩_
*/
private boolean isRed(Node node) {
if (node == null) {
// _空节点咱们都认为是彩色的叶子节点_
return BLACK;
}
return node.color;
}
}
放弃根节点为彩色和左旋转
后面介绍了红黑树的五个定义，这些定义使得红黑树可能维持自均衡。咱们都分明，当对一颗树增加或删除节点时，就有可能会毁坏这棵树的均衡。红黑树也不例外，所以这个时候就须要作出一些调整，来让红黑树持续满足这五个定义。调整的办法有两种，变色 和旋转，其中旋转又分为 左旋转 和右旋转。
变色：
- 为了从新合乎红黑树的规定，尝试把红色节点变为彩色，或者把彩色节点变为红色
从下面咱们编写的红黑树的根底构造代码能够看到，在增加一个节点时，默认是红色。如果新增加的这个红色节点不能满足红黑树的定义，那么咱们就须要对其进行变色。例如，当增加的节点是一个根节点时，为了放弃根节点为彩色，就须要将其色彩变为彩色：
左旋转：
- 逆时针旋转红黑树的两个节点，使得父节点被本人的右子节点取代，而本人成为本人的左子节点
在上图中，身为右子节点的 Y 取代了 X 的地位，而 X 变成了本人的左子节点，因而为左旋转。例如，咱们往根节点 1 增加一个元素 2，其左旋转过程如下：
- Tips：本文中设定红黑树是左倾的
左旋转的具体实现代码如下：
// 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;
}
假如咱们要对 37 这个 node 进行左旋转，其右子节点 X 为 42，依据下面的代码，其左旋转的具体过程如下：
色彩翻转和右旋转
在上一大节中，咱们理解了变色和左旋转。基于之前的例子，当咱们再增加一个节点 66 时，该节点会被增加到左边成为右子节点，此时只须要做一下色彩的翻转即可，如下所示：
对应的代码如下：
/**
* _色彩翻转_
*/
private void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
咱们再看另一种增加节点的状况，就是增加的节点比左子节点还要小，此时该节点就会挂到左子节点下：
对于这种状况，咱们就要进行 右旋转：
- 顺时针旋转红黑树的两个节点，使得父节点被本人的左子节点取代，而本人成为本人的右子节点
在上图中，身为左子节点的 Y 取代了 X 的地位，而 X 变成了本人的右子节点，因而为右旋转。
对于下面那种状况，右旋转。
还有一种状况就是增加的元素比 node 和 X 都要大，此时就会挂载到 X 的左边，此时就须要多做一步左旋转操作。
右旋转的实现代码如下：
// node x
// / _右旋转_ /
// x T2 ——-> 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 {
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;
}
