左倾红黑树

名字很危险。

从 2-3-4 树开始

令 BST 的节点可以有多个 key,就得到了 2-3-4 树。

2-3-4 树的节点可以有 1, 2 或 3 个 key,相应的有 2, 3 或 4 个儿子,被称为 2-node, 3-node 和 4-node。将每个节点的 key 值从小到大排列,这些 key 分割开几个区间。 2-3-4 树是自平衡的 ,在后面会解释。

一个 2-3-4 树例子

查询操作

类似于 BST,但向下走时不再是简单的二分,因为父节点的 key 可能划分出了更多的区间。

插入操作

向下不断查找,如果叶子是 2-node 或 3-node,那么直接加一个 key 就 OK 了。

2-node or 3-node

但如果终点是一个 4-node,key 个数已经最大,不能直接加 key。可以想到要进行 split 操作:令 3 个 key 的那个中间值移到父节点,将剩下的部分分到两边。

split

但这种方法对于父节点也是 4-node 并不适用。可以不断对 4-node 的父节点再做 split (bottom-up) ,这种方法最终得到的其实是一棵 2-3 树。也可以每次向下走时只要遇到 4-node 就 split (top-down),这样可以保证 4-node 的父节点肯定不是 4-node,访问到的叶子也肯定不是 4-node,但这样做可能会在上面遗留 4-node,得到的是 2-3-4 树。

删除操作

先考虑叶子。如果要删的值的 key 在 3-node 或 4-node 里,那么直接删掉就 OK 了。但如果这个 key 在 2-node,直接删掉它会破坏平衡。解决这一问题的方法是借 key,把 2-node 变成 3-node 或 4-node。主要两种:

  • 向父亲借。如果兄弟也是 2-node,借一个 key 与两兄弟合并,变成 4-node,然后删掉 key。

    2-node or 3-node
  • 向兄弟借。如果兄弟不是 2-node,就借一个 key 过来把要删的节点变成 3-node,然后再删掉 key。

    2-node or 3-node

然后考虑非叶节点,类似于 BST,主要思想是用右子树的最小值替换掉要删除的节点,然后删掉右子树的最小值节点。

2-3-4 树是自平衡的

会改变树结构的操作有 insert, split 和 delete,分开看。

insert 操作是建立在待插入节点一定不是 4-node 的前提之上的,所以只需要在节点加 key,一定不会破坏平衡。

split 操作一定会把 3 个 key 均匀分开,中间的 key 被提上去,仍然保持平衡。如果根节点 split 会使树的高度 +1 。

split

delete 操作一定只删 key 不删节点,也不会破坏平衡。

然后到 LLRB

可以发现 2-3-4 树适合口胡,但显然实现起来很复杂。于是把它转化为 BST:用黑边连接不同的节点,对于 3-node 和 4-node,用红边在内部连接节点的不同 key,形成红黑树。这里的红黑是边的颜色,可以把边的颜色下放到点的颜色。但这样 3-node 可以乱摆,无法做到一一对应,于是我们钦定硬点红边必须左倾,这意味着实际上我们使用的是 2-3 树。

性质

  • 红边必须是左倾的。
  • 从一个节点到其子树中每个叶子的路径都包含相同数量的黑边。(perfect black balance)
    • 可通过与 2-3 树的对应得出。
  • 不会出现连续的两个红边。
    • 等价于红黑树的性质“每个红色结点必须有两个黑色的子结点”。
  • 每个节点最多只会连一条红边。

旋转操作

旋转操作是调整树形态的基本手段。

插入操作

先像普通 BST 一样 insert 一个节点,然后把与父节点连接的边设为红边,此步相当于在 2-3 树的叶子加 key。

然后调整使得树符合 LLRB 性质:

  • 如果得到右倾的红边,进行一次左旋使其左倾。
  • 如果得到连续的左倾红边,进行一次右旋得到一个 4-node。
  • 如果有 4-node,split 掉。split 操作在 LLRB 中对应的是 color flip 操作:把父节点相连的所有边反色。

删除操作

将 2-3 树的删除操作对应到 LLRB 中,我们要删掉的一定是红点。我们先来考虑删掉最小值,因为它是删除非叶节点所必须的。

删掉最小值

我们要令最小值叶子最终一定是红点,就需要持续向下传递红边。因此设当前走到的节点为 h,在向下走的过程中我们需要保证 h 为红点或 h 的左儿子为红点,否则红边就无法传递。这也就是删除过程中的隐含条件。

如果 h 的左儿子 和 h 的左儿子的左儿子(左孙子?)都是黑点,那么红边就传不下去了,就需要向 h 去借 key 以维持红边的传递,就是一次 color flip。

需要注意的是如果 h 的右儿子的左儿子是红点,color flip 后会产生连续红边,这个错误发生在右子树,在删完往上走的时候是修正不到的,必须现在通过多次旋转修正。

不断传递,直到访问到最小值叶子,将它删去,然后返回。在往上走的过程中要维护可能被破坏的 LLRB 结构。

删掉任意值

如果我想随便删个节点,那么就会在树上不知左右的游走,但不变的是要确保能持续向下传递红边。因此我们需要保证 h 为红点或要走的那个方向的儿子为红点。

如果是删叶子,那么剩下的就和删掉最小值一样。

如果是删非叶节点,那么就找到该节点的右子树的最小值换掉它,然后把子树里原来那个最小值删掉。

如果没有右子树:不可能只有左黑儿子,因此肯定左儿子是红点,右旋一次把目标节点染红后去右子树删除即可。