1. 我所理解的平衡性与红链接
2. 插入操作原理
3. Java实现 - 节点
4. Java实现 - 旋转与换色
5. Java实现 - 插入
6. Java实现 - 删除

2-3树

    手提着这里
       |
---------------
1      5      9

应该手提着这里
     |
---------------
1  4   5      9

    |
    4
   / \
  1   5
       \
        9

    |
    5
   / \
  4   9
 /
1

    |
  4---5
 /     \
1       9

    |
    5
   / \
  4   9
 /
1

1. 有没有必要存在两个相连的红链接? 答案是没有必要性, 两个相邻的红链接意味着平衡点组有3个结点, 这其实相当于一个三个数字的尺子, 没有必要用红链接, 直接从当中一拎起来, 还是平衡的, 所以直接改成黑色链接也就是普通链接就可以了.
2. 既然拎一个红链接的左边和拎右边都可以保持平衡, 现在我们是强行规定必须拎右边, 如果已经有了一个拎起左边节点的树, 现在要改成拎右边, 该如何操作呢? 还是用例子来说明: 现在有如下的一个最简单的树, 这个数将5-9看做一个平衡点的话, 左侧有一个元素(3), 右侧有2个元素(7和10), 拎起来哪一端应该都不会影响平衡性:

                |
                5
              /   \
             3     9
                  / \
                 7  10
   

   很显然, 我们现在要做的就是从拎起5改成拎起9, 如果直接拎起来, 显然不行, 这样9下挂了3个节点, 这个时候可以发现, 7代表的树, 一定是小于9而且大于5的部分, 所以只要把7挂到5的右侧就可以了 改成拎起9之后的情况如下:

                |
                9
              /   \
             5     10
            / \
           3   7
   

   此时由于5-9之间依然是红链接, 没有改变颜色, 所以可以继续将5-9看做一个平衡点, 此时平衡点左侧有两个元素, 3和7, 右侧有一个元素, 10, 依然是2-1, 这也是左右元素数量不等的时候我们提起的最靠近中点, 而且也符合不允许有右侧红链接的操作了. 这里还有一些小细节, 比如最上边这根线的颜色, 很显然应该是黑色, 否则就是两个连续的红链接, 可以修改成黑链接, 相当于把中间的点给提起来(我把这个叫做换色操作, 换色还有一个特点就是要把新拎起来的点上边的链接换成红色, 这是因为换色相当于新插入了一层结点, 比如本来拎5或者9, 现在来了一个6, 既然要拎起来6, 相当于新插入了6, 打破了原来的平衡点组. 换色同时还将红链接向上传递, 得以继续处理, 很有意思.). 这就可以一层一层向上传导, 先平衡最下边的树, 再平衡上一层, 以此类推. 刚才完成的这个操作, 就是左旋, 所谓左旋, 就是把红链接从右边转到左边, 类似的也有右旋, 把红链接从左侧转到右侧, 根据我们的分析, 一个平衡点组里拎起谁都行, 那自然左旋和右旋不会影响平衡. 既然一棵树左旋和右旋不会影响平衡, 递归的话, 任何红链接左旋和右旋都不会影响平衡. 此外空链接, 也当成黑色.

插入操作原理

1. 像普通二叉树一样找到需要插入的位置
2. 插入新结点, 将新结点与父节点的链接设置为红链接
3. 从父节点开始往回一直到根节点, 对每个节点按照顺序执行下列步骤:
   1. 右红左黑, 左旋转(处理单独右侧红链接)
   2. 左红, 左子节点也是红色, 右旋(处理相邻红链接)
   3. 左右都红, 换色
   为什么按顺序执行这三种情况, 这是因为找到当前元素的插入点的时候, 由于整棵树不会存在连续的红节点和右红链接, 新节点X插入之后始终是红链接, 只会有如下几种情况:

               一       二       三      四      五
               |        |        |       |       |
               C        C        C       C       C
              / \      / \      / \     / \     / \
             X   D    X   D    A   X   A   X   A   X
   

   1. 情况一: 原来的节点都是黑链接, 左侧插进来X红链接, x指向null 是黑链接, 无需进行任何处理, 也不满足上边ABC三条判断的任何一个
   2. 情况二: 原本的C是红链接, 左侧插进来X红链接, 不满足ABC任何一条, 但是有相邻的红链接, 这个就会在递归到父节点的时候进行处理
   3. 情况三: 原来的节点都是黑链接, 右侧插入X红链接, 属于A情况, 右红左黑, 左旋之后, 成为情况1, 完成平衡
   4. 情况四: A红C黑, 插入完之后是两侧都红, 需要换色, 是情况C
   5. 情况五: A黑C红, 插入完之后右红左黑, 需要左旋, 左旋之后是情况二, 递归给父节点处理
   通过分析可以看到, 情况五->左旋->情况二, 情况三->左旋->情况一, 情况四->换色, 所以五种情况只有情况三四五需要处理, 而左旋之后必定没有红色右链接, 所以满足条件先左旋. 不左旋说明剩下右红左红, 右黑左黑, 右黑左红三种情况, 除了右黑左黑无需处理之外, 只有两种情况, 要么全红, 要么是子节点导致连续红链接, 再判断连续红链接需要右旋, 如果不需要左旋也不需要右旋, 那就只剩下两红要处理, 或者压根无需处理了.

Java实现 - 节点

public class RedBlackLiteBST<Key extends Comparable<Key>, Value> {
    private static final boolean RED   = true;
    private static final boolean BLACK = false;

    //特殊的根节点, 要单独指定
    private Node root;
    //存放总的元素数量
    private int n;


    private class Node {
        //每个结点存放一个键值对
        private Key key;
        private Value val;
        //左右链接
        private Node left, right;
        //保存父节点指到自己的链接颜色
        private boolean color;

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

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

Java实现 - 旋转与换色

//这个传入的h, 是指向红链接左端的指针, 方法返回一个指向旋转后的新节点的引用
private Node rotateLeft(Node h) {
    assert (h != null) && isRed(h.right);
    // x 等于红链接右侧的节点
    Node x = h.right;
    //然后将x的左连接挂到h的右连接上去
    h.right = x.left;
    //将h挂到x的左连接上
    x.left = h;
    //将x设置成h的颜色
    x.color = h.color;
    //将h设置成红色, 表示x->h是红链接
    h.color = RED;
    //返回对x的引用
    return x;
}

//右旋和左旋只要交换left和right就可以了
private Node rotateRight(Node h) {
    assert (h != null) && isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    return x;
}

private void flipColors(Node h) {
    //判断是否满足换色条件, 即左红右红
    assert !isRed(h) && isRed(h.left) && isRed(h.right);
    //强制改变自己的颜色为红色
    h.color = RED;
    //设置两个子节点为黑色
    h.left.color = BLACK;
    h.right.color = BLACK;
}

Java实现 - 插入

//对外暴露的API, 强制设置根节点为黑色, 然后会递归的返回整理过的红黑树的根节点
public void put(Key key, Value val) {
        root = insert(root, key, val);
        root.color = BLACK;
        assert check();
    }

private Node insert(Node h, Key key, Value val) {
    //直到找到空结点, 返回一个新的固定为红色的节点
    if (h == null) {
        n++;
        return new Node(key, val, RED);
    }

    //这是插入的代码, 不断递归寻找, 更新或者插入新节点
    int cmp = key.compareTo(h.key);
    if      (cmp < 0) h.left  = insert(h.left,  key, val);
    else if (cmp > 0) h.right = insert(h.right, key, val);
    else              h.val   = val;

    //成功插入的时候, 此时当前的h就是新节点的父节点, 然后一层一层开始处理, 逻辑就是之前插入原理的内容.
    //每次都返回处理过的节点引用
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
    return h;
}

Java实现 - 删除