准确的名字是红黑二叉查找树

红黑树是2-3树的变体，用一棵二叉树去表示一棵2-3树

红黑树到2-3树

将红黑树中的链接分为两种

  • 红链接：将2个2-节点连在一起，表示一个3-节点（注意，为了保持通过红链接相连的节点的有序性，红链接只能是左链接）
  • 黑链接：与2-3树中的普通链接等价（空链接视为黑链接）

以这种方式，从2-3树转换而来的红黑树有下面这些特性：

  • 一个结点最多有一条红链接
  • 这棵树是黑色完美平衡的

节点表示代码

有了上面的两种树之间的转换方式，我们可以写出表示节点的类

    // BST helper node data type
    private class Node {
        private Key key;           // key
        private Value val;         // associated data
        private Node left, right;  // links to left and right subtrees
        private boolean color;     // color of parent link
        private int size;          // subtree count

        public Node(Key key, Value val, boolean color, int size) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.size = size;
        }
    }

注意boolean color这个变量，它用来表示父节点用什么颜色的节点指向本节点

3个基础操作：旋转，颜色转换，移动

如果2-3树总是保持只含有2-节点，和3-节点，那么我们不需要额外的操作，但是不要忘记可能存在一种临时的节点：4-节点。这两种操作的目的就是为了将等价的2-3树中的4-节点转换到2-节点和3-节点上

旋转

左旋与右旋除了方向上是完全一样的，毕竟这两个操作是对称的（运算上的对称）

左旋是将一条红色的右链接转化为左链接

对应的方法（函数）接受的参数是一个节点的引用（或者说指针），在对节点上的子树进行调整之后返回子树新的根节点。

左旋
image-20210811170225713

调用下面代码

    // make a right-leaning link lean to the left
    private Node rotateLeft(Node h) {
        assert (h != null) && isRed(h.right);
        // assert (h != null) && isRed(h.right) && !isRed(h.left);  // for insertion only
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = x.left.color;
        x.left.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

变为

image-20210811170612732
右旋
image-20210811170826163
    // make a left-leaning link lean to the right
    private Node rotateRight(Node h) {
        assert (h != null) && isRed(h.left);
        // assert (h != null) && isRed(h.left) &&  !isRed(h.right);  // for insertion only
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = x.right.color;
        x.right.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }
image-20210811170855151

颜色转换

用于处理这样一种临时状态：一个父节点通过2条红色链接，连接2个子节点（即2-3树中的4-节点）

将2条红色链接变为黑色，并将指向父节点的原本黑色的链接转换为红色（相当于再2-3树中，将一个键值插入到父节点中去）

据此我们可以写出颜色转换的代码

    // flip the colors of a node and its two children
    private void flipColors(Node h) {
        // h must have opposite color of its two children
        // assert (h != null) && (h.left != null) && (h.right != null);
        // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right))
        //    || (isRed(h)  && !isRed(h.left) && !isRed(h.right));
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }
根节点总是黑色的

原本，指向“根节点”的链接为红色的话表明根节点是某个2-3节点的一部分，不过这种情况下因为有链接指向“根节点”，那么这就不是根节点

由于我们是使用被链接指向的节点中的一个变量来表示链接的颜色，用一个数据结构表示链接及其颜色，为了不出额外的差错，每次手动将根节点设置为黑色