【11.6】索引--红黑树

BST的平衡问题:

  • 理想状况:插入、删除、查找时间代价为O(logn )
  • 输入9,4,2,6,7,15,12,21
  • 输入2,4, 6,7, 9, 12,15, 21

一、红黑树定义:red-black tree, 简称RB-tree

红黑树:平衡的 扩充 二叉搜索树

  • 颜色特征:结点是“红色” 或“黑色”;
  • 根特征 :根结点永远是“黑色”的;
  • 外部特征:扩充外部叶结点都是空的“黑色” 结点;
  • 内部特征:“红色”结点的两个子结点都是 “黑色”的,丌允许两个连续的红色结点;
  • 深度特征:任何结点到其子孙外部结点的每条 简单路径都包含相同数目的“黑色”结点

红黑树的阶

  • 结点X的阶(rank,也称“黑色高度”)
  • 从该结点到外部结点的黑色结点数量
  • 不包括 X 结点本身,包括叶结点
  • 外部结点的阶是零
  • 根的阶称为该树的阶

二、 红黑树相关性质

  1. 红黑树是满二叉树 ,空叶结点也看作结点
  2. 阶为 k 的红黑树路径长度:最短是 k,最长是 2k。从根到叶的简单路径长度: 阶为 k 的红黑树树高最小是 k+1,最高是 2k+1
  3. 阶为k的红黑树的内部结点 最少是一棵完全满二叉树,内部结点数最少是 2^k-1
  4. n 个内部结点的红黑树树高 最大是 $ 2 log_{2} (n+1)+1 $

证明:

  • 设红黑树的阶为 k,设红黑树的树高是 h。
  • 由性质(2) 得 h <= 2k+1,则 k >= (h-1) / 2
  • 由性质(3)得 n>=2^k–1,即n>=2(h-1)/2 –1
  • 可得出 h <= $ 2 log_{2} (n+1)+1 $

三、结点插入算法

  • 先调用 BST 的插入算法
  • 把新记录着色为红色
  • 若父结点是黑色,则算法结束
  • 否则,双红调整

3.1 插入算法调整 1:重构

情况1:新增结点 X 的叔父结点是黑色

每个结点的阶都保持原值,调整完成

4 种形式的结构调整

原则:保持 BST 的中序性质

3.2 插入算法调整 2:换色

情况 2:新增结点 X 的叔父结点也是红色

需要继续检查平衡

插入 4

  • 情况 2 红红冲突 。 父和叔父也是红
  • 父祖换色

情况 1 红红冲突。 叔父是黑 。 重构

四、结点删除算法

  • 先调用 BST 的删除算法

  • 待删除的结点有一个以上的外部空指针,则直接删除

  • 否则在右子树中找到其后继结点进行值交换(着色不变)删除

  • v 是被删除的内结点, w 是被删外结点, X 是 w 的兄弟

  • 如果v或者 X 是红色, 则把X标记为黑色即可 *否则, X 需要标记为双黑, 根据其兄弟结点 C 进行重构调整

4.1 根据双黑 X 的兄弟 C 进行调整

假设X是左子结点(若X为右孩子,则对称)

  • 情况 1: C 是黑色,且子结点有红色

  • 重构,完成操作

  • 情况 2: C 是黑色, 且有两个黑子结点

  • 换色

  • 父结点 B 原为黑色,可能需要从 B 继续向上调整

  • 情况3: C是红色

  • 转换状态

  • C 转为父结点,调整为情况 1 或 2 继续处理

4.1.1 情况 1(a) 重构:侄子红结点八字

  • 将兄弟结点 C 提上去
  • C 继承原父结点的颜色
  • 然后把B着为黑色,D 着为黑色,其他颜色不变即可

4.1.2 情况 1(b) 重构:侄子红结点同边顺

  • 将 D 结点旋转为 C 结点的父结点,D 继承原 子根 B 的颜色,B 着为黑色

4.1.3 情况 2:兄弟是黑色, 且有两个黑子结点

  • 把 C 着红色, B 着黑色
  • 如果 B 原为红色,则算法结束
  • 否则,对 B 继续作“双黑”调整

4.1.4 情况 3: 兄弟 C 是红色

  • 旋转
  • X 结点仍是“双黑”结点,转化为前面2种情况

4.1.5 例子

删除 90
  • 当前结点变为 80 的右黑叶结点
  • C 是黑色, 且有两个黑色子结点:情况 2

情况 2 换色

删除 70

红结点,不要调整

删除 80
  • 当前结点 X 变为 65 的右黑叶结点 * C 是红色:情况 3 状态转换

删除 80(调整)

  • C 是黑色,且左黑、右红:情况 1(b) 重构

完成调整

4.2 删除操作时间代价

  • 其平均和最差检索 O(log2 n)
  • 自底向根的方向调整
  • 红黑树构造
  • (数据,左指针,右指针,颜色,父指针)
  • 自顶向下的递归插入/删除调整方
  • (数据,左指针,右指针,颜色)
  • 若非递归,则记录回溯路径

4.3 从 Red-Black-Tree 到 2-3-4 树

  • 假设将一棵红黑树的每个红结点“吸收”到他的黑色父 结点中,来让红结点的子女变为黑色父结点的子女(忽 略关键字的变化)

  • 当一个黑结点的所有红色子女都被吸收后, 其可能的度是多少?

  • 2、3、4 即成为一棵 2-3-4 树(阶为 4 的 B 树)

  • 此结果树的叶子深度怎样? 叶结点等高

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

药企,独角兽,苏州。团队长期招人,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn