855学习记录数据结构树(7)伸展树与$B$-树——炎泽汐$de$ Blog

文章目录[隐藏]

伸展树
$B$ 树

伸展树

引入

伸展树（ $s p l a y$ $t r e e$ ）也是平衡二叉搜索树的一种形式。相对于 $A V L$ 树，伸展树的实现更为简捷。伸展树无需时刻都严格地保持全树的平衡，但却能够在任何足够长的真实操作序列中，保持分摊意义上的高效率。伸展树也不需要对基本的二叉树节点结构，做任何附加的要求或改动，更不需要记录平衡因子或高度之类的额外信息，故适用范围更广。

信息处理的典型模式是，将所有数据项视作一个集合，并将其组织为某种适宜的数据结构，进而借助操作接口高效访问。现实中，通常在任意数据结构的生命期内，不仅执行不同操作的概率往往极不均衡，而且各操作之间具有极强的相关性，并在整体上多呈现出极强的规律性。其中最为典型的，就是所谓的“数据局部性”，这包括两个方面的含义：

1）刚刚被访问过的元素，极有可能在不久之后再次被访问到；

2）将被访问的下一元素，极有可能就处于不久之前被访问过的某个元素的附近；

充分利用好此类特性，即可进一步地提高数据结构和算法的效率。就二叉搜索树而言，数据局部性具体表现为：

1）刚刚被访问过的节点，极有可能在不久之后再次被访问到；

2）将被访问的下一节点，极有可能就处于不久之前被访问过的某个节点的附近；

因此，只需将刚被访问的节点，及时地“转移”至树根（附近），即可加速后续的操作。当然，转移前后的搜索树必须相互等价。

逐层伸展

一种直接方式是：每访问过一个节点之后，随即反复地以它的父节点为轴，经适当的旋转将其提升一层，直至最终成为树根。

随着节点 $E$ 的逐层上升，两侧子树的结构也不断地调整，故这一过程也称作伸展，而采用这一调整策略的二叉搜索树也因此得名。不过，为实现真正意义上的伸展树，还须对以上策略做点微妙而本质的改进。之所以必须改进，是因为目前的策略仍存在致命的缺陷，对于很多访问序列，单次访问的分摊时间复杂度在极端情况下可能高达 $Ω (n)$ 。

双层伸展

为克服上述伸展调整策略的缺陷，一种简便且有效的方法就是：将逐层伸展改为双层伸展。具体地，每次都从当前节点 $v$ 向上追溯两层（而不是仅一层），并根据其父亲 $p$ 以及祖父 $g$ 的相对位置，进行相应的旋转。以下分三类情况，分别介绍具体的处理方法。

第一种情况是 LL 右双旋或 RR 左双旋，先祖父后父节点，两者对称：

第二种情况是 RL 右左双旋或 RR 左右双旋，先父节点后祖父，两者对称：

前两者为将节点上推两层，接下来第三种情况则是往上一层，此时树高为 2，调整后成为根：

Tarjan 等人采用势能分析法已证明，在改用“双层伸展”策略之后，伸展树的单次操作均可在分摊的 $O (l o g n)$ 时间内完成。

查找、插入与删除

在伸展树中查找任一关键码 $e$ 的过程：首先，调用二叉搜索树的通用算法尝试查找具有关键码 $e$ 的节点。无论查找是否成功，都继而调用 $s p l a y ()$ 算法，将查找终止位置处的节点伸展到树根。

为将关键码 $e$ 插至伸展树 $T$ 中，首先调用伸展树查找接口，查找该关键码，将最后被访问的节点 $t$ 通过伸展被提升为树根，其左、右子树分别记作 $T_{L}$ 和 $T_{R}$ 。接下来，根据 $e$ 与 $t$ 的大小关系（不妨排除二者相等的情况），以 $t$ 为界将 $T$ 分裂为两棵子树。比如，不失一般性地设 $e$ 大于 $t$ 。于是，可切断 $t$ 与其右孩子之间的联系，再将以 $e$ 为关键码的新节点 $v$ 作为树根，并以 $t$ 作为其左孩子，以 $T_{R}$ 作为其右子树：

为从伸展树 $T$ 中删除关键码为 $e$ 的节点，首先亦调用接口查找该关键码，且不妨设命中节点为 $v$ 。于是， $v$ 将随即通过伸展被提升为树根，其左、右子树分别记作 $T_{L}$ 和 $T_{R}$ 。接下来，将 $v$ 摘除。然后，在 $T_{R}$ 中再次查找关键码 $e$ 。尽管这一查找注定失败，却可以将 $T_{R}$ 中的最小节点 $m$ ，伸展提升为该子树的根。

得益于二叉搜索树的顺序性，此时节点 $m$ 的左子树必然为空；同时， $T_{L}$ 中所有节点都应小于 $m$ 。于是，只需将 $T_{L}$ 作为左子树与 $m$ 相互联接，即可得到一棵完整的二叉搜索树。如此不仅删除了 $v$ ，而且既然新树根 $m$ 在原树中是 $v$ 的直接后继，故数据局部性也得到了利用。

$B$ 树

$B$ 树

其中，所有外部节点均深度相等。同时，每个内部节点都存有不超过 $m$ - $1$ 个关键码，以及用以指示对应分支的不超过 $m$ 个引用。树高满足条件： $\log_{m} (n + 1) \leq h \leq \log_{⌈ m / 2 ⌉} (\frac{n + 1}{2} + 1)$ ，除根以外的所有内部节点，都应满足： $n + 1 \geq ⌈ m / 2 ⌉$ ；在非空的 $B$ -树中，根节点应满足： $n + 1 \geq 2$ 。含有 $n$ 个非叶节点的 $m$ 阶 $B$ 树至少包含 $(n - 1) (⌈ m / 2 ⌉ - 1) + 1$ 个关键字。