Home DS复习 Part 5
Post
Cancel

DS复习 Part 5

BST & AVL

二分 (折半) 查找:

  • 仅适用于顺序查找 (因为需要随机访问), 仅适用于有序表.
  • 平均查找长度 ASL 根据判定树可以很容易地计算出来. 二分查找判定树是一个平衡二叉树. 因为, 二分查找的默认计算方式是 mid=(left+right)/2, 即向下取整. 因此用 mid 分隔当前序列后, mid 左边的元素个数一定小于等于右边的元素个数, 相差为 0 或 1.
  • 查找成功的 ASL 计算: $ASL=\dfrac{1}{n}(1\times 2^0+2\times 2^1+\dots h\times 2^{h-1})=\dfrac{1}{n}((h-1)\times 2^h+1)$. 这是因为, 第一层只有根结点, 长度是 1, 第 2 层有 2 个结点, 长度是 2, 按照满二叉树来考虑, 第 h 层就是 $2^{h-1}$ 个结点, 长度是 h. 假设原序列共有 n 个元素, 那么判定树中的成功查找结点共有 n 个, 树的高度就是 $h=\lceil\log_2{(n+1)}\rceil=\lfloor\log_2{(n+1)}\rfloor+1$. 为简便考虑, 我们假设 $h=log_2{(n+1)}$, 则 $2^h=n+1$. 因此: \(\begin{eqnarray} \label{eq} ASL&=&\dfrac{1}{n}((log_2{(n+1)}-1)\times(n+1)+1) \nonumber \\ ~&=&\dfrac{1}{n}((n+1)\log_2{(n+1)}-n) \nonumber \\ ~&=&\dfrac{n+1}{n}\log_2{(n+1)}-1\approx\log_2{(n+1)}-1 \nonumber \\ \end{eqnarray}\)
  • 所以二分查找的时间复杂度是 $O(\log_2{n})$.

二分查找的判定树是平衡二叉树, 是唯一的 (想一想平衡二叉树是怎么旋转出来的); 而二叉排序树会由于插入顺序的不同而生成不同的形态. 例如, 插入 24 和 12, 则 24 是根结点, 12 是其左孩子; 而插入 12 和 24, 则 12 是根结点, 24 是其右孩子.

既然二叉排序树有点鸡肋, 为什么还要用呢? 很简单, 如果二叉排序树没有成为一棵倾斜的单支树 (这种情况是 O(n)!), 那么它还是可以在不做任何旋转的情况下快速完成查找的. 毕竟左旋右旋 (相当于移动结点) 就挺麻烦的.

平衡二叉树 (Balanced Binary Tree, 但是我们熟知的 AVL 是发明者 Adelson-Velskii 以及 Landis 名字的缩写) 的出现: 为避免树的高度增长过快从而降低二叉排序树的性能, 就规定了任意结点的左右子树的高度差绝对值不超过 1. 这个高度差就称为此结点的“平衡因子”.

含有 n 个结点的平衡二叉树的最大深度为 $O(\log_2{n})$, 因此平衡二叉树的平均查找长度和时间复杂度也是 $O(\log_2{n})$.

红黑树

为了保持 AVL 树的平衡性, 需要频繁地调整, 于是就在平衡标准上放宽条件, 有了红黑树.

红黑树的性质:

  1. 每个结点要么是红的, 要么是黑的.
  2. 根结点是黑的.
  3. 每个叶结点 (NIL) 是黑的.
  4. 如果一个结点是红的, 那么它的两个孩子都是黑的 (这也说明它的父亲不可能是红的, 否则它的父亲就违背了“孩子是黑的”这条规则).
  5. 对于每个结点, 从该结点到其所有后代叶结点的简单路径上, 均包含相同数目的黑结点.

黑高 bh: 从某结点 (不含该结点) 到一个叶结点的简单路径上的黑结点的数目.

叶结点称为外部结点, 其余的结点就是内部结点. 因为叶结点的存在本来就是为了保证内部结点的左右孩子非空.

结论 1: 从根结点到叶结点的最长路径不大于最短路径的 2 倍.

证明: 因为从根结点到任意一个叶结点的路径上的黑结点的数目都相同, 设为 n, 那么最长路径就应该有 n-1 个红结点 (红黑相间, 且两端必是黑结点, 因为根结点和叶结点必须为黑结点), 因此最长路径的长度为 2n-1, 最短路径的长度为 n, 于是最长路径不大于最短路径的 2 倍.

结论 2: 有 n 个内部结点的红黑树的高度 $h\leq O(\log_2{(n+1)})$.

证明:

设 bh(x) 表示结点 x 的黑高, 那么根结点 t 的黑高就是 bh(t).

根据红黑树的性质可知红色节点不可相邻, 但是并没有对黑色节点进行要求. 因此所有的黑色节点可以挨在一起, 一棵红黑树可以全部都是黑色节点. 那么我们就假设一棵只有黑色节点的红黑树, 其树高就是 bh(t). 这一定是一棵高为 bh(t) 的满二叉树, 因为从根结点到任意叶结点都有路径, 路径上的黑结点数都相等, 而且路径上还全都是黑结点. 注意, 原本的 bh(t) 是不包含根结点、但是包含叶结点的, 而叶结点是外部结点, 我们要求的却是内部结点. 这其实是等价的, 相当于整体向上挪了一个结点, 毕竟根结点和叶结点都是黑色的. 于是, 总的内部结点数就是 $n=2^{bh(t)}-1$.

刚才考虑的是全都是黑结点的特殊情况. 如果还要插入红结点, 那么内部结点数一定大于刚才的值. 因此, 总的内部结点数应该满足 $n\geq 2^{bh(t)}-1$.

现在回到一般情况. 设 h 是树高, 那么一定有 $bh(t)\geq\dfrac{h}{2}$. 于是, 有 $n\geq 2^{bh(t)}-1\geq 2^{\frac{h}{2}}-1$.

插入和删除

叶结点只是起到辅助作用, 属于查找不成功的「失败结点」, 而所有插入的结点都属于内部结点, 是查找成功的「成功结点」, 因此如果不加上叶结点的话, 内部结点构成的叶结点也可以是红色的.

B 树

不等式:

  • n 是关键字个数, m 是阶数, 则 $\lceil\dfrac{m}{2}\rceil-1\leq n\leq m-1$.
  • h 是 B 树高度, 则 h 满足不等式: $\log_m{(n+1)}\leq h\leq\log_{\lceil m/2\rceil}{(\dfrac{n+1}{2}+1)}$.

插入

新元素一定是插入到底层的终端结点中, 因为这样能够保证到最后所有的失败结点都在最底层. 如果插入后导致某些结点的关键字个数超过了 m-1, 那么就要进行分裂.

分裂的方法是: 从中间位置 $\lceil\dfrac{m}{2}\rceil$ 处将结点的关键字分裂成左中右三个部分 (中间部分就只有一个关键字, 即 $\lceil\dfrac{m}{2}\rceil$ 处的元素). 中间的关键字上升到父结点中. 如果父结点已经满了, 那么也要继续分裂, 直到根结点. 如果根结点也满了, 就新建一个根结点, 再将原根结点分裂成两部分.

删除

  • 如果要删除的关键字在终端结点, 则直接删除, 如果删除后导致结点内关键字个数小于 $\lceil\dfrac{m}{2}\rceil-1$, 就要进行合并或者借位.
  • 如果要删除的关键字在非终端结点, 那么就要先找到它的直接前驱 (左子树最右下) 或直接后继 (右子树最左下), 用它替换要删除的关键字, 这样就转换成了删除终端结点的情况.

因此, 下面着重探讨终端结点的删除.

当删除后导致结点内关键字个数小于 $\lceil\dfrac{m}{2}\rceil-1$ 时:

  • 能够找兄弟借:
    • 当右兄弟够借时 (意思是说, 取出右兄弟的最小关键字后, 右兄弟内关键字个数没有低于 $\lceil\dfrac{m}{2}\rceil-1$), 就用当前结点的后继、后继的后继填补空缺. 其中, 当前结点的后继就是当前结点的父结点中刚好大于它的那个关键字, 当前结点的后继的后继就是右兄弟的最小关键字.
    • 如果右兄弟不够但左兄弟够, 就借前驱、前驱的前驱.
  • 兄弟都不够借, 则合并.

    正因为不够借, 所以其兄弟结点一定刚好有 $\lceil\dfrac{m}{2}\rceil-1$ 个关键字, 而当前结点的关键字个数 $n_{cur}\le\lceil\dfrac{m}{2}\rceil-1\leq\lceil\dfrac{m}{2}\rceil-2$. 再参照下面的合并方法可知, 合并后结点内关键字个数应该 $\leq(\lceil\dfrac{m}{2}\rceil-2)+1+(\lceil\dfrac{m}{2}\rceil-1)\leq m-1$. 这就证明了合并的结点是满足条件的.

    • 例如, 可以合并当前结点和其右兄弟. 合并方法是: 将当前结点的后继从父结点中移下来, 然后把右兄弟的所有关键字接在后面, 三者共同构成一个结点.
    • 但是这样可能会让父结点关键字个数小于 $\lceil\dfrac{m}{2}\rceil-1$, 所以还要继续合并 (兄弟不够借的情况下) 或借位 (兄弟够借). 如果最后合并到根结点关键字个数为 0 了 (这也说明, 根结点原来只有 1 个关键字, 而合并操作是合并了根结点仅有的两个子结点), 就删除根结点, 让合并后的结点 (原根结点的左子结点+根结点唯一的关键字+原根结点的右子结点) 成为新的根结点.
This post is licensed under CC BY 4.0 by the author.