只要是一棵树, 就得看看如何生长, 如果树不平衡, 在进行查找操作的时候, 就可能出现性能低下. 什么是平衡呢, 在排序的时候已经简单的用图表示过, 可以加权或者将小树附加到大树上.

平衡二叉树的思路也是如此. 那么什么是平衡呢, 所谓平衡, 就是指所有空节点到根节点的距离应该是相同的.

看了一晚上终于明白了红黑树的道理, 其实算法这一节没有叫红黑树的原因我也明白了, 红其实就是一个标记, 只要被标记了红, 这个链接的两端就起到平衡的作用, 相当于一个天平的两端, 实时平衡其两头挂载的内容.

不过这博客可真难写, 还是用自己的语言来描述一下吧.

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

2-3树

为了引出红黑树, 算法先介绍了2-3树, 还有3结点和4结点, 我觉得, 这里的核心其实引入了平衡的概念, 就是如何将节点拆分成二叉树以保持平衡.

这本书之前提到过二叉树在数组上的投影, 但是这里没有提, 我觉得用这个来理解最方便.

什么是平衡, 所谓平衡, 就是各个底部的数字到最上边根节点的距离相等. 换种我的理解方式, 也就是树的两侧的元素的数量几乎相等.

假如现在数组里放着456三个数字, 想象成一个尺子上刻着159三个数字, 要把这个尺子拿起来保持两端平衡, 肯定是用手提住中点的位置, 此时就是这样的:

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

现在想象尺子是柔软的, 将5往上提, 就变成了一个下挂两个4和6节点的5节点, 也就是一棵二叉树.

现在如果再放入一个4,会发生什么情况呢, 按照原来二叉树的放法, 4小于5, 去找左侧, 4大于1, 找右侧,右侧没有, 就放到1的右侧, 此时的投影是:

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

这个时候如果还是拿起这根软尺子要保持平衡, 要拿哪个地方呢? 很显然, 如果不指定一定要拿到哪个元素的话, 手需要拿在4和5中间的位置, 才能保证两侧的元素数量相等, 也就是平衡了.

问题是我们的手必须要提着一个结点, 每个数字就是一个节点, 按照就近原则的话, 其实提4或者5都是可以的, 如果提起来4(也就是把4当做根节点), 按照二叉树的排布, 应该是这样的:

    |
    4
   / \
  1   5
       \
        9

如果提着5, 那么二叉树是这样的:

    |
    5
   / \
  4   9
 /
1

可以看到, 无论提起4和5, 整体的平衡性是一样的, 都是非常靠近中点的. 那么我们可以把4-5叫做一个平衡点组(我自己起的名字, 也就是说4和5共同构成了一个树的平衡点), 无论用手拎起4还是5, 都没有问题.

那么如何标识这个平衡点组呢, 就用一根红线将二者连起来, 这就是红链接. 算法书上定义了被红链接指向的节点颜色设置为红, 但其实对于红链接两端被链接的点来说, 其实二者共同构成了一个平衡点.

在有了平衡点组的时候, 实际上就可以重新取得平衡:

    |
  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, 打破了原来的平衡点组. 换色同时还将红链接向上传递, 得以继续处理, 很有意思.).
    这就可以一层一层向上传导, 先平衡最下边的树, 再平衡上一层, 以此类推.

    刚才完成的这个操作, 就是左旋, 所谓左旋, 就是把红链接从右边转到左边, 类似的也有右旋, 把红链接从左侧转到右侧, 根据我们的分析, 一个平衡点组里拎起谁都行, 那自然左旋和右旋不会影响平衡.
    既然一棵树左旋和右旋不会影响平衡, 递归的话, 任何红链接左旋和右旋都不会影响平衡.
    此外空链接, 也当成黑色.

插入操作原理

将红链接考虑为一个平衡点组之后, 可以发现旋转和换色, 都是针对红链接的操作, 与黑链接完全没有关系. 而针对红链接的操作, 无论是旋转还是换色, 都不影响新的拎起来的点的平衡性.

既然如此, 插入操作的核心就是, 不管插入到哪里, 始终把插入的元素和父节点之间当成一条红链接, 插入完进行处理就可以了, 如果需要旋转就旋转, 需要拎起来连续红链接(换色操作), 就拎. 反正处理完, 依然不影响平衡性,
这就是插入操作的本质.

这个时候再去看算法书上的向根节点插入新键, 向3-节点中插入新键, 就完全能够理解了, 都是处理红链接而已, 而处理手段不过是旋转和换色, 只要处理完成, 就依然不会影响平衡性.

树在这个过程所谓生长, 其实只是因为人为的认为红链接不计算入元素的长度位置. 但其本质还是二叉树, 红链接只是标记出来了可以进行平衡的位置, 进而执行平衡操作.

根节点始终是黑色, 这个要注意, 否则就会出问题, 所以在每次操作之后都要将其设置成为黑色.

最后这个就变成了一个递归的情况, 过程如下:

  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实现 – 节点

首先是结点的, 依然采用内部类 Node. 然后用布尔值true代表红色, false代表黑色, 并且在结点中存放父节点指向其的链接的颜色:

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

有了旋转方法之后, 只要获取一个节点, 然后让节点 = rotateLeft(Node 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实现 – 删除

红黑树的删除, 用一句话说, 道理我都懂, 但是代码写不出来.

虽然标题是实现, 但是我现在还实现不了, 看着也有点晕, 二叉树先总结到这里, 平衡性的插入还是很有意思的.

找了篇文章先留着, 哪天脑子清楚了再来看: https://www.cnblogs.com/nullllun/p/8214599.html#autoid-3-2-0