树 - 红黑二叉树（2-3树查找树） - 《算法和数据结构》

概念
时间复杂度
操作

概念

红黑二叉树的背后基本思想是用标准二叉树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。

红链接

将两个2-结点链接起来构成一个3-结点

黑链接

普通2-结点

定义

红链接均为左链接；
没有任何一个结点同时和两条红链接相连；
该树是完美黑色平衡的，即任意空链接到根根节点的路径上的黑连接数相同。

时间复杂度

最差2lgN，平均lgN

操作

旋转

某些操作会导致出现红色右链接或者两条连续的红链接，旋转会改变红链接的指向。

作用

保证红黑树的有序性和完美平衡性

左旋转

将一条红色右链接转换为左连接

Node rotateLeft(Node h) { // 图中E所指向的结点
    Node x     = h.right;     
    h.right = x.left;      // 将右链接的左子结点移动到左链接的右结点
    x.left     = h;           // 连接起来
    x.color = h.color;       // 置换颜色
    h.color = RED;          // 必定为红色
    x.N     = h.N;              // 只是发生了旋转，x的节点个数并没有变化
    h.N     = 1 + size(h.left) + size(h.right);  // 左链接个节点数要重新计算
    return x;
}

右旋转

将一个红色左连接转换为一个红色右链接

Node rotateRight(Node h) {
    Node x  = h.left;
    h.left  = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    x.N     = h.N;
    h.N        = 1 + size(h.left) + size(h.right);
    return x;
}

颜色置换

转换一个节点的两个红色子节点颜色，并且将父节点的颜色由黑变红

插入

向单个2-结点插入新键

根据新结点老结点大小做对比，按以下两种情况插入，最终结果与3-结点等效

新结点小于老结点：直接新增一个红链接，即插入左子结点，设置结点红色
新结点大于老结点：插入之后马上进行左旋转

向树底部的2-结点插入新键

情况与上面类似，新键小于老键就立即新增，新键大于老键则需要在新增后进行左旋转。

向一颗双键树（即一个3-结点）中插入新键

存在三种情况：

新键大于原树中的两个键
新键小于原树中的两个键
新建处于原树中两个键之间

插入完成之后需要将根节点都设为黑链接，结点本身变成一个3-结点，所以需要变成红链接

向树底部的3-结点插入新键

除了讨论上述三种情况。指向新结点的链接可能是3-结点的
右链接（只转换颜色），
左连接（右旋转再换颜色），
中链接（先左旋转下层链接然后右旋转上层链接，最后转换颜色）

旋转条件：

如果右字节点是红色，左字节点是黑色，需要进行左旋；
如果左节点是红色，并且他的左子节点也是红色，进行右旋；
如果左右子节点都为红色，则进行颜色转换
```
void flipColors(Node h) {
 h.color = RED;
 h.left.color = BLACK;
 h.right.color = BLACK;
}
```
```java private static final boolean RED = true; private static final boolean BLACK = false;

private class Node { Key key; // 键 Value val // 相关联的值 Node left, right; // 左右子树 int N; // 这棵子树中的结点总数 boolean color; // 由其父节点指向它的链接的颜色

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

}

private boolean isRed(Node x) { if (x == null) return false; return x.color == RED; }

```java
private static final boolean RED =      true;
private static final boolean BLACK = false;
public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node
    private boolean isRed(Node h)
    private Node rotateLeft(Node h)
    private Node rotateRight(Node h)
    private void filpColors(Node h)
    private int Size()
    private void put(Key key, Value val) {
        // 查找key，找到则更新，否则创建新节点
        root = put(root, key, val);
        root.color = BLACK;
    }
    private void put(Node h, Key key, Value val) {
        if (h == null) { // 执行插入操作
            return new Node(key, value, RED);
        }
        int cmp = key.compareTo(h.key);
        if          cop < 0    h.left  = put(h.left, key, val);
        else if  com > 0    h.right = put(h.right, key, val);
        else                h.val = val;  // 可以啥也不做
        // 进行旋转操作
        if (isRed(h.right) && !isRed(h.left)) rotateLeft(h);        // 右字节点是红色，左字节点是黑色，需要进行左旋
        if (isRed(h.left)  && isRed(h.left.left)) rotateRight(h);    // 左节点是红色，并且他的左子节点也是红色，进行右旋
        if (isRed(h.right) && isRed(h.left)) filpColors(h);            // 左右子节点都为红色，则进行颜色转换
        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }
}

删除

删除最小键

从树的底部的3-结点中删除很简单。
2-结点中删除会破坏树的平衡性，要沿着左链接向下进行变换，确保当前结点不是2-结点（3- or 4-）。
如果是2-结点且它的两个子节点都是2-结点，直接将三个结点变成4-结点，
否则需要保证根节点的左子结点不是2-结点。在沿着左链接向下的过程中保证一下情况之一成立：

如果当前结点的左子节点不是2-结点，完成；
如果当前结点的左子节点是2-结点而它的亲兄弟结点不是2-结点，将左子结点的兄弟结点中的一个键移动到左子结点中；
如果当前节点的左子结点和它的亲兄弟结点都是2-结点，将左子结点、父结点中的最小键和左子结点最近的兄弟结点合并为一个4-结点，使父亲点由3-结点变为2结点或者由4-结点变为3-结点