3. 伸展树¶

与 AVL 树类似，伸展树实际上并不是一种独立的数据结构，而是重新实现了 BST 的插入、删除和查找方法，以提升 BST 的性能。这些修订方法的目标是为一系列操作所需的时间提供保证，从而避免标准 BST 操作的最坏情况线性时间行为。伸展树中的单次操作并不能保证高效。相反，伸展树的访问规则保证，对于包含 \(n\) 个节点的树，只要 \(m \geq n\) ，执行 \(m\) 次操作将花费 \(O(m log n)\) 时间。因此，单次插入或查找操作可能需要 \(O(n)\) 时间。然而， \(m\) 次这样的操作保证总共需要 \(O(m \log n)\) 时间，即每次访问操作的平均成本为 \(O(\log n)\) 。这对于任何搜索树结构来说都是一个理想的性能保证。

与 AVL 树不同，伸展树并不保证高度平衡。 所保证的是整个访问系列的总代价是低廉的。 归根结底，重要的是这一系列操作的总代价， 而不是这棵树是否平衡。 维持平衡实际上只是为了实现这一时间效率目标。

伸展树的访问函数运作起来让人联想起 移至表头 用于 自组织线性表 的规则， 以及用于管理一系列 并查集 操作的路径压缩技术。 这些访问函数倾向于使树更加平衡，但单次访问并不必然会得到 更加平衡的树。

每当访问节点 \(S\) （例如，当插入、删除 \(S\) 或将其作为搜索目标时），伸展树会执行一个称为 伸展 的过程。伸展操作将 \(S\) 移动到 BST 的根节点。当删除 \(S\) 时，伸展操作会将 \(S\) 的父节点移动到根节点。与 AVL 树类似，对节点 \(S\) 的伸展由一系列 rotations 组成。旋转通过调整节点与其父节点和祖父节点的相对位置，使 \(S\) 在树中向上移动。旋转的一个副作用是使树趋于平衡。旋转有三种类型。

只有当 \(S\) 是根结点的子结点时，才执行 单旋转。 单旋转如图 26.3.1 所示。 它基本上以一种保持 BST 性质的方式交换 \(S\) 与其父结点。 虽然图 26.3.1 与 图 26.2.2 略有不同，但事实上伸展树的单旋转 与 AVL 树的单旋转完全相同。

与 AVL 树不同，伸展树需要两种 双旋转。 双旋转涉及 \(S\)、它的父结点（称之为 \(P\)）， 以及 \(S\) 的祖父结点（称之为 \(G\)）。 双旋转的效果是把 \(S\) 在树中提升两级。

第一种双旋转称为 \(zigzag rotation\) （之字形旋转）。 当下列两种情况之一满足时发生：

1. \(S\) 是 \(P\) 的左子结点，且 \(P\) 是 \(G\) 的右子结点。

2. \(S\) 是 \(P\) 的右子结点，且 \(P\) 是 \(G\) 的左子结点。

换句话说，当 \(G\)、\(P\) 和 \(S\) 形成之字形（zigzag） 时，就使用之字形旋转。 之字形旋转如图 26.3.2 所示。

另一种双旋转称为 一字形旋转。 当下列两种情况之一满足时，发生一字形旋转：

1. \(S\) 是 \(P\) 的左孩子，而

   \(G\) 的左子节点。

2. \(S\) 是 \(P\) 的右孩子，而

   \(G\) 的右子节点。

因此，在那些不适用之字形旋转的情况下，就发生一字形旋转。 一字形旋转如图 26.3.3 所示。 虽然图 26.3.3 看起来与图 26.2.3 有些不同，但事实上一字形旋转与 AVL 树的双旋转完全相同。

注意，之字形旋转倾向于使树更加平衡， 因为它们把子树 \(B\) 和 \(C\) 提升一级， 同时把子树 \(D\) 下移一级。 结果往往是树的高度减少一。 一字形提升和单旋转通常不会降低树的高度；它们只是把新访问的记录 带向根。

伸展结点 \(S\) 涉及一系列双旋转，直到 \(S\) 到达根或根的子结点。 然后，如有必要，一次单旋转使 \(S\) 成为根。 这一过程往往使树重新平衡。 无论平衡与否，伸展都会使频繁访问的结点 留在树的上方附近，从而降低访问代价。 关于伸展树满足 \(O(m \log n)\) 保证的证明 超出了我们研究的范围。