数据结构之红黑树

2-3树

在了解红黑树之前，我们先来认识2-3树，在算法（第4版）里也是先从2-3树切入到红黑树的。并且了解2-3树对于理解B类树也会有帮助，因为2-3树可以说就是基础的B类树。

2-3树的特性：

• 满足二分搜索树的基本性质
• 节点可以存放一个元素或者两个元素，或者说数据项
• 每个节点有2个或者3个子节点，这也是2-3树的名称由来
• 2-3树是一棵绝对平衡的树，对于任意节点的左右子树的高度一定是相等的

2-3树为了维持绝对平衡，需要满足以下条件：

1. 2节点有且只能有两个子节点，并只能包含一个数据项
2. 3节点有且只能有三个子节点，并只能包含两个数据项，大小关系从左至右依次递增
3. 添加数据项时不能将该数据项添加到一个空节点上，因为新的节点只能通过分裂或者融合产生
4. 当2-3树只有2节点的时候，其只能是一棵满二叉树

2-3树的两类节点：

image.png

• 可以看到，2节点有两个子节点，5和15，且自身只包含一个数据项，即10。3节点则有三个子节点，自身只能包含两个数据项，从左至右依次递增：5 < 6 < 7 < 8 < 9

下图是一颗完整的2-3树：

image.png

从上图中可以看到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树时，其流程如下：

image.png

1. 添加元素1，创建一个2节点类型的根节点

2. 添加元素2，此时元素1和2存在同一个节点中，成为一个3节点。为什么添加元素2时，不能生成一个新的节点作为元素1所在节点的右子节点呢？因为“添加数据项时不能将该数据项添加到一个空节点上，新的节点只能通过分裂或者融合产生”

3. 添加元素3，元素1、2、3，暂时存在同一个节点中，形成一个4节点

4. 分裂，2-3树中最多只有3节点，不能存在4节点，所以暂时形成的4节点要进行分裂，将中间的元素作为根节点，左右两个元素各为其左右子节点。这时可见形成了一棵满二叉树

5. 添加元素4，根据元素的大小关系，将会存放到元素3所在的节点。因为新添加的元素不能添加到一个空节点上，所以元素4将根据搜索树的性质找到最后一个节点与其融合。即元素3和4将融合为一个三节点。并且根据大小关系元素4要位于元素3的右侧

6. 添加元素5，同插入元素4，元素5一路查找到元素3、4所在的三节点，与其融合，暂时形成一个4节点

7. 分裂，元素3、4、5所在的4节点同上面元素1、2、3形成的4节点一样，进行分裂操作。根据大小关系，4元素将会作为根节点，元素3、5则各为其左右子节点

8. 融合，前面的分裂操作已经导致该2-3树不满足其第四条性质“当2-3树只有2节点的时候，其只能是一棵满二叉树”，所以该2-3树将要向上融合以满足2-3树的性质。我们只需要将元素4所在节点与其父节点即元素2所在的节点进行融合即可。这时，元素2、4就形成了一个3节点

如果我们继续往2-3树中添加元素6和7，那么最终形成的2-3树如下图所示：

image.png

如果在这个案例中我们使用的是二分搜索树，那么该二分搜索树将会退化为一个链表，而2-3树则通过分裂、融合的方式成为了一颗满二叉树。

---

红黑树与2-3树的等价性

了解了2-3树后，我们来看下红黑树与2-3树的等价性，严格来说是左倾红黑树才是与2-3树是等价的。与2-3树一样，红黑树具有二分搜索树的性质，并且也是自平衡的，但不是绝对平衡，甚至平衡性比AVL树还要差一些。

之前提到了2-3树是绝对平衡的，对于任意节点的左右子树的高度一定是相等的。而AVL树则是任意节点的左右子树高度相差不超过 1 即可，属于高度平衡的二分搜索树。

红黑树则是从根节点到叶子节点的最长路径不超过最短路径的2倍，其高度仅仅只会比AVL树高度大一倍，所以在性能上，下降得并不多。由于红黑树也是自平衡的树，也会采取一些机制来维持树的平衡。

红黑树的定义：

1. 每个节点或者是红色的，或者是黑色的
2. 根节点是黑色的
3. 每一个叶子节点（最后的空节点）是黑色的
4. 如果一个节点是红色的，那么它的左右子节点都是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的

这里的第三点要求“每一个叶子节点（最后的空节点）是黑色的”，稍微有些奇怪，它主要是为了简化红黑树的代码实现而设置的。我们也可以理解为，只要是空的节点，它就是黑色的。

下图是一颗典型的红黑树：

image.png

在了解了2-3树之后，我们知道2-3树是通过分裂和融合来产生新的节点并维持平衡的。2-3树有两类节点，2节点和3节点。除此之外，还会有一种临时的4节点。接下来我们看看2-3树向红黑树转换的过程，下图展示了2-3树的这三种节点对应于红黑树的节点：

image.png

• 2节点：对应于红黑树的黑色节点
• 3节点：对应于红黑树中黑色的父节点和红色的左子节点
• 临时的4节点：对应于红色的父节点和黑色的左右子节点。这里需要说一下，为什么是红色的父节点而不是黑色的呢？主要是因为2-3树的3节点需要将分裂后的父节点进行向上融合，红色的符合我们向红黑树中插入任何一个节点默认都是红色的实现方式。如果该父节点是红黑树的根节点的话，那它肯定需要变色，这一点就不属于2-3树向红黑树的变换规则了，而属于红黑树的性质。

根据这个对应关系，我们将这样一颗2-3树：

image.png

转换成红黑树，就是这样子的，可以看到其中的红色节点都对应着2-3树的3节点：

image.png

如果这样看着不太好对应的话，我们也可以将其绘制成这个样子，就更容易理解红黑树与2-3树是等价的了：

image.png

从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;
    }
 }

---

保持根节点为黑色和左旋转

前面介绍了红黑树的五个定义，这些定义使得红黑树能够维持自平衡。我们都清楚，当对一颗树添加或删除节点时，就有可能会破坏这棵树的平衡。红黑树也不例外，所以这个时候就需要作出一些调整，来让红黑树继续满足这五个定义。调整的方法有两种，变色和旋转，其中旋转又分为左旋转和右旋转。

变色：

• 为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色

从上面我们编写的红黑树的基础结构代码可以看到，在添加一个节点时，默认是红色。如果新添加的这个红色节点不能满足红黑树的定义，那么我们就需要对其进行变色。例如，当添加的节点是一个根节点时，为了保持根节点为黑色，就需要将其颜色变为黑色：

image.png

左旋转：

• 逆时针旋转红黑树的两个节点，使得父节点被自己的右子节点取代，而自己成为自己的左子节点

image.png

在上图中，身为右子节点的Y取代了X的位置，而X变成了自己的左子节点，因此为左旋转。例如，我们往根节点 1 添加一个元素 2，其左旋转过程如下：

image.png

• 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，根据上面的代码，其左旋转的具体过程如下：

image.png

---

颜色翻转和右旋转

在上一小节中，我们了解了变色和左旋转。基于之前的例子，当我们再添加一个节点 66 时，该节点会被添加到右边成为右子节点，此时只需要做一下颜色的翻转即可，如下所示：

image.png

对应的代码如下：

/**
 * 颜色翻转
 */
private void flipColors(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}

我们再看另一种添加节点的情况，就是添加的节点比左子节点还要小，此时该节点就会挂到左子节点下：

image.png

对于这种情况，我们就要进行右旋转：

• 顺时针旋转红黑树的两个节点，使得父节点被自己的左子节点取代，而自己成为自己的右子节点

image.png

在上图中，身为左子节点的Y取代了X的位置，而X变成了自己的右子节点，因此为右旋转。

对于上面那种情况，右旋转的流程如下：

image.png

还有一种情况就是添加的元素比 node 和 X 都要大，此时就会挂载到 X 的右边，此时就需要多做一步左旋转操作。如下所示：

image.png

右旋转的实现代码如下：

//     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;
}