算法第四版 第三章 平衡查找树

作者 柚爸

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

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

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

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

  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