在了解红黑树之前,我们先来认识2-3树,在算法(第4版)里也是先从2-3树切入到红黑树的。并且了解2-3树对于理解B类树也会有帮助,因为2-3树可以说就是基础的B类树。
2-3树的特性:
2-3树为了维持绝对平衡,需要满足以下条件:
2-3树的两类节点:
下图是一颗完整的2-3树:
从上图中可以看到2-3树是满足二分搜索树的基本性质的,只有两个节点的情况,如 42 这个节点,右子节点小于父节点,左子节点大于父节点。而有三个节点时,右子节点仍然小于父节点,中间的子节点大于父节点的左数据项,小于父节点的右数据项(如图中18大于17,小于33),左子节点则大于父节点。
之前我们提到了2-3树插入节点时不能将该节点插入到一个空节点上,新的节点只能通过分裂或者融合产生。我们知道对二分搜索树依次添加有序的数据时,如依次添加 1、2、3、4、5,会产生连续的节点,使得二分搜索树退化成链表。
为了避免退化成链表,具有平衡特性的树状结构,会采取一些手段来维持树的平衡,例如AVL是通过旋转节点,而2-3树则是通过分裂和融合。当我们依次添加 1、2、3、4、5 到2-3树时,其流程如下:
如果我们继续往2-3树中添加元素6和7,那么最终形成的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树:
转换成红黑树,就是这样子的,可以看到其中的红色节点都对应着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,其左旋转过程如下:
左旋转的具体实现代码如下:
// 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;
}