数据结构-搜索(二) 2-3树-左偏红黑树

发表于 2019-03-29 分类于数据结构阅读次数： Disqus：本文字数： 8.7k 阅读时长 ≈ 8 分钟

数据结构-搜索(二) 2-3树证明；左偏红黑树证明
源码: https://github.com/Jasper-1024/python/tree/master/data_structure/search

更新

1
2
3

19.03.29 初始
19.04.03 添加左偏红黑树.
19.04.05 补全图片和遗漏内容

参考资料
https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000
https://sakurawood.github.io/2017/06/25/红黑树
https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
维基百科
算法第四版,算法导论.

导语

算法中所描述的红黑树实际上是 LLRB(Left-leaning red–black tree) 左偏红黑树/左倾红黑树,与传统上认知的红黑树(5条定义)多了两条规则.实际上简化了相当的代码量,也更容易实现.
LLRB实际上对应的的算法中的2-3树,原始版本的红黑树实际对应 2-3-4树.
故这里将 LLRB 与 2-3树合为一篇, RBT 与 2-3-4树合为一篇,试图将整个的来龙去脉搞清楚.
与红黑树时间复杂度的证明在下一篇.
ps : 代码开源在 Gitbub ,之后博文里不会再有大段的代码了.
强烈建议去看看 princeton 大学的 RedBlack.pdf 非常详细.本篇大量摘自这里.

基础库

/libs
- BtNode 适配红黑树,增加颜色属性,移动到了/libs.
- 把到处都是的 randoms 类,重新整理移动到了/libs.
- 二叉树可视化的 prtree 也放到了/libs.
  - 修正了prtree传入none时的一个bug.
  - 添加了生成 gif 的方法,但因为将 Graphviz 画出图的大小固定的设置还没搞定,生成的gif没法看..
/ST
- 搜索的基类重命名为 STclass
- 在 __init__.py 中引用 /libs 下模块.
  - 因为 vscode python 调试,相对路径引用有问题,这里只能用绝对路径引用.
这样调整后,基本没有什么重复代码了,层次也明确了很多,还是得遵循随时重构,要不然随时都是自己挖的坑…

2-3树

2-3树这里仅提及查找/插入/删除的过程和证明,不涉及代码.
这里提到的 2-3树均指代完美平衡的 2-3查找树.
在二叉搜索树一节,我们知道了对二叉搜索树而言,各种操作的时间复杂度基本与树高h成正比,但二叉搜索树对树高的控制非常糟糕,这里的2-3树是对这个问题的第一步改进.
对二叉搜索树树高影响最大的是插入和删除两个操作,而 2-3树通过对二叉树节点的变形,使得插入及删除操作变成了局部变换,不会单方面影响树的高度(除根节点外,根节点的操作会使树高+1,但不影响平衡性)
定义,2-3树中存在两类节点.
- 2- 节点,与普通二叉搜索树的节点定义相同.左子树均小于根节点值,右子树均大于根节点值.
- 3- 节点,含有两个键-值对,与3条子树链接.左链接指向的子树都小于2-3数中两个键值,右链接指向子树都大于2-3数的两个键值,而中链接执行的子树键值在2-3数的两个键值之间.

查找

整个过程与二叉搜索树的查找相差不大,不再赘述
时间复杂度
- 假设树高为 h .2-3 树的查找操作与树高成正比,时间复杂度为 $O(h)$
- 这里的 2-3 树均是完美平衡,因此 N 个节点的 2-3 树高度应该在 $\lg N$ (节点均为2-节点),和 $\log_3 N$ (节点均为3-)之间,所以可以证明含有N个节点的 2-3 树,其高度不超过 $O(\lg N)$.
- 因此含有 N 个节点 2-3 树的查找的时间复杂度为 $O(\lg N)$

插入

这里需要分情况讨论,2-节点与3-节点及他们的父节点都有不同.
ps: 图仅为示例,有些节点并非完全平衡2-3树
情况1: 待插入位置为 2- 节点,那非常简单,将 2- 节点转换为 3- 节点即可,整个过程没有影响树高.如图所示(待插入键值16):
情况2: 带插入位置只含一个3-节点,可以临时将这个3-节点抓换为4-节点,再向上生长,树高+1,但不影响树的平衡性.如图所示:
- 这种情况只有在根节点才会发生.也说明了2-3树如何生长.
情况3: 待插入位置为3-节点(叶节点),且有父节点存在.这里情况比较有意思,举例来说:
- 我们要插入元素兼职为 12 ,待插入位置为 11-13 的 3- 节点.
- 与情况2的做法相同,这里短暂将3-节点转换为4-节点.
- 然后将4-节点向上分解,在4-节点所在的深度分解为两个2-节点,向上一层的父节点位置插入一个2-节点(这里为3-节点).
  - 如果父节点为 2-节点(情况1),直接转化为 3-节点
  - 如果父节点为 3-节点(情况2) ,继续递归的向上分解,直到遇到根节点或者 2-节点为止,遇到根节点为3-节点则 2-3树树高整体+1为止.
上面应该是2-3树插入节点时的全部情况,从3种情况分析来看,与二叉搜索树不同,这里的3种插入节点的情况都没有影响树的平衡性.所有的插入动作都是局部变换,没有影响到树的高度(根节点处除外).
时间复杂度
- 假设2-3树的树高为 h .
- 前半部分均为查找动作,时间复杂度为 $O(h)$ ,插入动作分情况讨论.
  - 情况1: 2- 节点变为 3- 节点,时间复杂度为 1.
  - 情况2: 只有根节点时出现,时间复杂度依旧为 1.
  - 情况3: 略有不同,需要考虑向上分解的过程,向上分解最多经过 $O(h)$ 次,因此时间复杂度为 $O(h)$
- 整体的时间复杂度为 $O(h)$ + $O(h)$ = $O(h)$
- 因此含有 N 个节点的 2-3 树的插入操作的时间复杂度为 $O(\lg N)$

删除

同样需要分情况讨论,且删除节点必须保证2-3树的平衡性.
叶子节点
- 3-节点: 这种情况最为简单,将这个3-节点删除对应键值,转换为2-节点即可.不涉及树的平衡性问题.
- 2-节点: 我们无法像二叉搜索树一样直接删除 2-节点,直接删除会破坏树的平衡性.我们需要沿着查找待删除节点路径上对经过的所有节点进行处理,使最后待删除的 2-节点转化为 3-/4-(节点)节点.再进行删除操作,并且删除操作后要沿原路径返回分解所有临时4-节点.由根节点往下,整个过程分为以下几种情况:
  - 根节点为2-节点时情况比较特殊,单独讨论:
    - 左右子节点均为2-节点.
    - 查找方向为 2-节点,另一方向为 3-节点.需要由3-节点借一个键值对.
    - 查找方向节点为3节点不做变换.
  - 当前节点为3-/4-节点,且查找方向也为3-节点时,不做变换,继续递归.
  - 当前节点为3-/4-节点,查找方向节点为2-节点时,分2种情况.
    - 查找方向为边缘子节点(左右子节点)
      - 临近兄弟子节点为3-节点,兄弟子节点借一个键值对.
      - 临近兄弟子节点为2-节点,直接合并兄弟子节点和父节点的对应中间键(如图是 15 ) 为一个4-节点(临时).
    - 查找方向为中间子节点
      - 临近兄弟子节点有3-节点(多个3-节点,随机取一个),借取3-节点和父节点,将中间节点转化成 3-节点.(这里假设左子节点为3-节点)
      - 临近兄弟子节点均为2-节点,将中间节点与兄弟子节点(随机取一个) 和对应父节点的中间键(如图为 10) 合并为 4- 节点(临时)
  - 直到最后查找到待删除的键值所在的节点,删除键值.
非叶节点
- 中间节点的删除与二叉搜索树中间节点的删除类似.都是使用后继节点替换的方式.
- 开始需要查找到待删除键值的位置.A.
- 继续查找后继的位置,左子树的最右,(右子树的最左).
- 交换后继键值到待删除位置.
- 对以A的左(右)子树递归删除最大(小)值.
  - 这里注意: 2-3树是平衡查找树,左右子树后继键值所在的节点深度一定相同,且为2-3树最底部.因此删除左右子树的后继键值,并不影响2-3树的平衡性.
时间复杂度
- 假设 2-3树高度为 h .
- 删除
  - 叶子节点,查找待删除节点位置,时间复杂度为 $O(h)$
    - 3-节点,时间复杂度 $O(1)$
    - 2-节点,包括由根节点到叶子节点的变换,删除,再回溯分解 4-节点(临时),时间复杂度 $O(h) + O(1) + O(h) = O(h)$
    - 整体时间复杂度为 $O(h)$
  - 非叶子节点
    - 假设待删除位置深度为 $s (s < h)$
    - 查找过程的时间复杂度为 $O(s)$ 交换后继节点 $O(1)$ 删除子树的键值 $O(h-s)$
    - 整体的时间复杂度为 $O(h)$
- 所以含有 N 个节点的2-3数,删除的时间复杂度为 $O(\lg N)$

性能分析

通过上面的分析可以看出,在二叉搜索树影响树高的插入/删除操作,在2-3树中得到了解决.
但在实际应用中,2-3树使用甚少,从上面的分析就可以看出,2-3树简单操作的各种节点类型转换,树形的变化相当频繁.不仅仅是上面涉及到的插入/删除,其他操作的成本都要比二叉搜索树高不少.

LLRB

2-3树的繁琐,在红黑树的到了解决,红黑树其实还是另一种意义上的 2-3树,不过是将3-,4-节点变形.
- 将3-节点转化为了节点A + 红链接 + 节点B
- 将4-节点转换成了节点A + 红链接 + 节点B + 红链接 + 节点C
对链接颜色定义并不方便,这里增加节点的颜色属性,表示其到父节点的链接颜色.除此之外,红黑树节点与BST的节点定义一致.因此查询类方法完全与 BST 一致.
红黑树完整定义(摘自维基百科):
1. 节点是红色或黑色.
2. 根是黑色.
3. 所有叶子都是黑色.
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
第五条也可以说,树是完美的黑色平衡,即任意空链接到根节点的路径上,黑色链接数量相等.
实际上上述定义的 RBT 对应 2-3-4树在下一篇会详细分析.
LLRB 在普通红黑树上增加了两个条件.(这里实际上限制了没有4-节点,红色左链接完美对应3-节点)
1. 任意红链接为左链接
2. 没有一个节点与两条红链接相连
LLRB 完全对应于 2-3树,其插入/删除操作只是在 2-3树的插入/删除操作上,增加了翻转和颜色变化,以保持定义第5条,即完美的黑色平衡.
LLRB 的图片大都来自 RedBlack.pdf

旋转/反转

LLRB对应 2-3树,在2-3树插入/删除有大量的节点转换,以保证2-3树的平衡性,而在 LLRB 对应的操作就是树的旋转和反转(颜色转换).

左旋转

将红色右链接转换为左链接,旋转前后,黑色平衡不改变.对应 2-3树的3-节点的内部转换.
示例(节点9可黑可红)

代码

# 左旋转
def rotateLeft(self, node):
    r_node = node.rchild
    node.rchild = r_node.lchild
    r_node.lchild = node
    # 原node的颜色
    r_node.color = node.color
    node.color = 'red'
    # 更新节点计数器
    r_node.N = node.N
    node.N = self.size(node.lchild) + 1 + self.size(node.rchild)
    return r_node

右旋转

将红色左链接转换为右链接.与左链接相反.
示例(配图吗,两个反过来..):

代码:

# 右旋转
def rotateRight(self, node):
    l_node = node.lchild
    node.lchild = l_node.rchild
    l_node.rchild = node
    # 原node的颜色#
    l_node.color = node.color
    node.color = 'red'
    # 更新节点计数器
    l_node.N = node.N
    node.N = self.size(node.lchild) + 1 + self.size(node.rchild)
    return l_node

反转(颜色转换)

当两个红链接链接到同一个黑色节点时,需要反转两个字节点颜色,将父节点设置为红色,等同于将红色链接向上传递.
实际等价于一个4-节点分解.
示例
等价于
因为在删除操作中有可能需要,将父节点为红,子节点为黑,反向将红链接向下传递,代码中写成了,根据颜色反转.

代码

# 一个节点两条红链接/黑链接(删除用),反转
def flipColors(self, node):
    def nor(node):
        if not (node is None):
            if node.color == red:
                node.color = black
            else:
                node.color = red

    # 反转
    nor(node)
    nor(node.lchild)
    nor(node.rchild)
    return node

插入

插入操作是 LLRB 比较复杂的操作,需要一点耐心,分情况讨论.
LLRB 插入操作流程.
- 寻找插入节点位置,插入节点.
- 通过反转/旋转等由插入位置向上回溯至根节点,修复 LLRB 的平衡性.
寻找插入位置
- LLRB 的节点定义与 bst 相差无几,查找操作相同.
- 插入新节点时,可以为黑色或红色,但 LLRB 为完美黑色平衡,新节点为黑色时,所需要的再平衡代价远远大于新节点为红色(具体分析略..)
修复平衡性
- 无论怎样,修复至根节点后,根节点需要手动至为黑色.(红黑树定义)
- 情况的分类与 2-3树插入基本对应.接下来是分情况讨论.
情况1(2-3树情况1)
- 待插入位置的父节点为黑色,无论父节点是否为根节点.
- 因为插入的新节点默认为红色,当父节点为黑色时,并不影响平衡性,直接插入即可.
- 在 LLRB 中,如果红色节点在右,需要多一次,左旋转.
情况2(2-3树情况2)
- 需要插入的父节点为红,爷爷节点为黑且为根节点.(相当于一个独立的3-节点)
- 这里比 2-3 数要复杂一点,需要考虑插入的位置实际在左中右.
情况3(2-3树情况3)
- 需要在树底的连续红黑节点插入.(有父节点的3-节点)
- 与2-3树情况3相同,首先插入节点,形成一个等价 4-(临时)节点,再通过旋转/反转等向上修复.这里需要考虑 3-节点的父节点及 3-节点与父节点链接的位置.
  - 父节点为2-节点
    - 3-在左
    - 3-在右
  - 父节点为3-节点
    - 3-在左
    - 3-在中
    - 3-在右
  - 接下来对不符合 LLRB 的红色右链接和节点链接两个红链接,进行修复(递归),直到根节点为止.
  - 如果根节点为红,为符合红黑树定义,重置为黑色.

代码

# 插入
def insert(self, key, value):
  self.root = self.put(key, value, self.root)
  self.root.color = black

def put(self, key, value, node=None):
  # 空位置,插入新的红色节点
  if node is None:
      return BtNode(key, value, color=red, N=1)
  cmp = self.key_compare(key, node.key)
  # 插入/递归
  if cmp < 0:
      node.lchild = self.put(key, value, node.lchild)
  elif cmp > 0:
      node.rchild = self.put(key, value, node.rchild)
  else:
      node.value = value
  # 右链接为红,左链接为黑,左旋转
  if self.isred(node.rchild) and (not self.isr(node.lchild)):
      node = self.rotateLeft(node)
  # 左链接为红,左左链接为红,右旋转
  if self.isred(node.lchild) and self.isr(node.lchild.lchild):
      node = self.rotateRight(node)
  # 左链接为红,右链接为红,反转
  if self.isred(node.rchild) and self.isr(node.lchild):
      self.flipColors(node)
  # 节点计数器
  node.N = self.size(node.lchild) + 1 + self.si(node.rchild)
  return node

删除

通过梳理 2-3树的删除,我们知道删除比插入流程简单,但变化/反转更为复杂, 因此先从删除最大/最小值入手.
删除最小键
- 最小节点为红色节点,直接删除即可,不影响黑色平衡性.
- 最小节点为黑色节点,我们需要对 LLRB 进行一些变化才能确保不影响黑色平衡性.
  - 这里引入红色节点向上传递的逆变换,为了方便就和颜色变化写在一起了.
  - 向下删除是一个递归的过程,向下递归终止的条件是左子树为空(变换到最左边了),如果没到最小值,应该会有判断是否需要对 LLRB 进行变换,如果需要进入,变换的调用, 判断不需要变换或变换返回后,继续向左子树递归.
  - 每一轮进入左子树递归时,我们需要保证此时左子树为红色.因此由根节点向下变换时,如果根节点的两个子节点均为黑色,为了反转产生红色节点,需要首先将根节点置为红色. 其他情况下由变换函数保证.
  - 变换条件.
    - 如果左子节点本身为红色节点,不需要进行变化.
    - 左子节点的左子节点为红色,同样不需要进行变化
    - 考虑右子树的影响,因为不存在红色的右链接, 所以右子树的颜色变换时不用考虑,对变换有影响的就是 node右子节点的左子节点).分两种情况.
      - node.rchild.lchild = black
      - node.rchild.lchild = red
  - 变换函数(moveRedLeft).
    - node.rchild.lchild = black
      - 这种情况非常简单,将node的红色链接,向下反转即可.
    - node.rchild.lchild = red
      - 这里就不能简单将node反转了,node反转后,如果直接进入左子树递归,那么 node.rchild 与 node.rchild.lchild 这个不符合红黑树定义的连续红链接,即使回溯至此时,也无法修复.
      - 整个过程就稍微麻烦了.
        node 反转
        node.rchild.lchild 左旋转
        node 右旋转(注意此时 node不再是开始时传入的node节点)
      - 示例是将修复过程也包含进去了,这里我们放在修复的函数中了.
  - 递归到左子树为空,即删除.
  - 修复函数
    - 向上修复的过程其实和插入操作的向上修复有部分相同的过程.
    - 右链接为红,左旋转
    - 左链接为红,左左链接为红,右旋转
    - 左链接为红,右链接为红,反转
  - 返回修复后的 node 节点.
删除最大键
- 最大节点为红色节点,直接删除即可,不影响黑色平衡性.
- 最大节点为黑色节点,我们需要对 LLRB 进行一些变化才能确保不影响黑色平衡性.
  - 向下删除是一个递归的过程,向下递归终止的条件是右子树为空(变换到最左边了),如果没到最大值,应该会有判断是否需要对 LLRB 进行变换,如果需要进入,变换的调用, 判断不需要变换或变换返回后,继续向右子树递归.
  - 每一轮进入右子树递归时,我们需要保证此时右子树为红色.因此由根节点向下变换时,如果根节点的两个子节点均为黑色,为了反转产生红色节点,需要首先将根节点置为红色. 其他情况下由变换函数保证.
  - 变换条件(与向左递归不同).
    - 如果右子节点本身为红色节点,不需要进行变化(不存在的).
    - 考虑左子树的其他影响,如果左子节点为红,右子节点为空,需要进行旋转(只在根节点出现).
    - 左链接为黑色,node左子节点的左子节点决定了两种情况.
      - node.lchild.lchild = black
      - node.lchild.lchild = red
      - node反转后…画图到炸..将就一下..
  - 变换函数(moveRedRight).
    - node.lchild = red && node.rchild = None
      - 直接右旋转即可,只在node为根节点时出现.
    - node.lchild = black && node.lchild.lchild = black
      - 非常简单,将 node 反转即可.
    - node.lchild = black && node.lchild.lchild = red
      - 这个时候必须考虑反转node 导致的左子树两个连续红节点.
      - 实际修复过程也只是稍微麻烦.
        node 反转
        node.lchild 右旋转,将连续红节点转移到右子树
        再次反转 node,修复完成
  - 递归到左子树为黑且右子树为空,即删除.
  - 修复函数与上相同
  - 返回修复后的 node 节点.
接下来是基本对应 2-3树的完整删除过程.
删除叶子节点:
- 待删除节点为红色节点(对于3-节点),这种情况下无所谓,删除红色的叶子节点不影响黑色的平衡性.
- 待删除节点为黑色节点,直接删除会影响红黑树的黑色平衡性
  - 在2-3树哪里,我们采用的是由根节点向下变换,直到将待删除节点转换为 3-节点,删除后再回溯至根节点,修复2-3树
  - 这里采用相同的方法,由根节点向下变换,直到最后将待删除节点转换为红色节点,再回溯到根节点修复 LLRB.
  - 这里的向下变换与向上修复函数与删除最大/最小值相同.当搜索被删除的键值在左子树时,调用 moveRedLeft ,被搜索键值在右子树时,调用 moveRedRight.
删除非叶子节点
- 与2-3树 bst 类似,都需要寻找到中序遍历的后继/前趋节点替换待删除节点,在进行修复.
- 与2-3树一致,首先还是由根节点递归向下变形的过程,规则与删除叶子节点一致.
- 找到待删除的节点位置后,寻找到左(右)子树最大(小)值.
- 递归在左(右)子树删除最大(小)值.
- 替换待删除节点,向上修复,最后将根节点置为黑色.
代码:
代码较多,不再追加.文件在这里: LLRB