《国家集训队2004论文集 杨思雨》由会员分享，可在线阅读，更多相关《国家集训队2004论文集 杨思雨（9页珍藏版）》请在金锄头文库上搜索。
1、IOI2004 国家集训队论文 杨思雨 伸展树的基本操作与应用伸展树的基本操作与应用 安徽省芜湖一中 杨思雨 目录 【关键字】.2 【摘要】.2 【引言】.2 【伸展树的基本操作】.2 伸展操作 Splay(x,S).3 伸展树的基本操作.4 时间复杂度分析.5 【伸展树的应用】.7 【总结】.8 【参考书目】 .9 【附录】.9 IOI2004 国家集训队论文 杨思雨 第 2 页 共 9 页 2【关键字】【关键字】 伸展树 基本操作 应用 【摘要】【摘要】 本文主要介绍了伸展树的基本操作以及其在解题中的应用。全文可以分为以 下四个部分。 第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要
2、地位，并且指 出二叉查找树在某些情况下时间复杂度较高， 进而引出了在时间复杂度上更为优 秀的伸展树。 第二部分介绍了伸展树的基本操作。 并给出了对伸展树时间复杂度的分析和 证明，指出伸展树的各种基本操作的平摊复杂度均为 O(log n)，说明伸展树是一 种较平衡的二叉查找树。 第三部分通过一个例子介绍了伸展树在解题中的应用， 并将它与其它树状数 据结构进行了对比。 第四部分指出了伸展树的优点，总结全文。 【引言】【引言】 二叉查找树（Binary Search Tree）能够支持多种动态集合操作。因此，在信 息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建 立索引或优先队
3、列等。 作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含 n 各节点的完全二叉树，这些操作的最坏情况运行时间为 O(log n)。但如果树是含 n 个节点的线性链，则这些操作的最坏情况运行时间为 O(n)。而有些二叉查找树 的变形，其基本操作在最坏情况下性能依然很好，比如红黑树、AVL 树等等。 本文将要介绍的伸展树（Splay Tree） ，也是对二叉查找树的一种改进，虽然 它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明 其每一步操作的平摊复杂度都是 O(log n)。所以从某种意义上说，伸展树也是一 种平衡的二叉查找树。而在各种树状数据结构中，伸展树
4、的空间要求与编程复杂 度也都是很优秀的。 【伸展树的基本操作】【伸展树的基本操作】 伸展树是二叉查找树的一种改进， 与二叉查找树一样， 伸展树也具有有序性。 即伸展树中的每一个节点 x 都满足：该节点左子树中的每一个元素都小于 x，而 其右子树中的每一个元素都大于 x。与普通二叉查找树不同的是，伸展树可以自 我调整，这就要依靠伸展操作 Splay(x,S)。 IOI2004 国家集训队论文 杨思雨 第 3 页 共 9 页 3伸展操作伸展操作 Splay(x,S) 伸展操作 Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸 展树 S 中的元素 x 调整至树的根部。 在调整的过
5、程中， 要分以下三种情况分别处 理： 情况一：节点 x 的父节点 y 是根节点。这时，如果 x 是 y 的左孩子，我们进 行一次 Zig（右旋）操作；如果 x 是 y 的右孩子，则我们进行一次 Zag（左旋） 操作。经过旋转，x 成为二叉查找树 S 的根节点，调整结束。如图 1 所示 图 1 情况二：节点 x 的父节点 y 不是根节点，y 的父节点为 z，且 x 与 y 同时是 各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次 Zig- Zig 操作或者 Zag- Zag 操作。如图 2 所示 图 2 情况三：节点 x 的父节点 y 不是根节点，y 的父节点为 z，x 与 y
6、 中一个是其 父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次 Zig- Zag 操 作或者 Zag- Zig 操作。如图 3 所示 图 3 如图 4 所示，执行 Splay(1,S)，我们将元素 1 调整到了伸展树 S 的根部。再 执行 Splay(2,S)，如图 5 所示，我们从直观上可以看出在经过调整后，伸展树比 原来“平衡”了许多。而伸展操作的过程并不复杂，只需要根据情况进行旋转就IOI2004 国家集训队论文 杨思雨 第 4 页 共 9 页 4可以了，而三种旋转都是由基本得左旋和右旋组成的，实现较为简单。 图 4 Splay(1,S) 图 5 Splay(2,S) 伸展树
7、的基本操作伸展树的基本操作 利用 Splay 操作，我们可以在伸展树 S 上进行如下运算： (1)Find(x,S)：判断元素 x 是否在伸展树 S 表示的有序集中。 首先，与在二叉查找树中的查找操作一样，在伸展树中查找元素 x。如果 x 在树中，则再执行 Splay(x,S)调整伸展树。 (2)Insert(x,S)：将元素 x 插入伸展树 S 表示的有序集中。 首先，也与处理普通的二叉查找树一样，将 x 插入到伸展树 S 中的相应位置 上，再执行 Splay(x,S)。 (3)Delete(x,S)：将元素 x 从伸展树 S 所表示的有序集中删除。 首先，用在二叉查找树中查找元素的方法找到
8、 x 的位置。如果 x 没有孩子或 只有一个孩子，那么直接将 x 删去，并通过 Splay 操作，将 x 节点的父节点调整 到伸展树的根节点处。否则，则向下查找 x 的后继 y，用 y 替代 x 的位置，最后 执行 Splay(y,S)，将 y 调整为伸展树的根。 (4)Join(S1,S2)：将两个伸展树 S1 与 S2 合并成为一个伸展树。其中 S1 的所 有元素都小于 S2 的所有元素。 首先，我们找到伸展树 S1 中最大的一个元素 x，再通过 Splay(x,S1)将 x 调 整到伸展树 S1 的根。然后再将 S2 作为 x 节点的右子树。这样，就得到了新的 伸展树 S。如图 6 所示
9、 IOI2004 国家集训队论文 杨思雨 第 5 页 共 9 页 5图 6 (5)Split(x,S)：以 x 为界，将伸展树 S 分离为两棵伸展树 S1 和 S2，其中 S1 中所有元素都小于 x，S2 中的所有元素都大于 x。 首先执行 Find(x,S)，将元素 x 调整为伸展树的根节点，则 x 的左子树就是 S1，而右子树为 S2。如图 7 所示 图 7 除了上面介绍的五种基本操作， 伸展树还支持求最大值、 求最小值、 求前趋、 求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的。 时间复杂度分析时间复杂度分析 由以上这些操作的实现过程可以看出，它们的时间效率完全取决于 Sp
10、lay 操 作的时间复杂度。下面，我们就用会计方法来分析 Splay 操作的平摊复杂度。 首先，我们定义一些符号：S(x)表示以节点 x 为根的子树。|S|表示伸展树 S 的节点个数。令(S) = log|S| ，(x)=(S(x)。如图 8 所示 图 8 IOI2004 国家集训队论文 杨思雨 第 6 页 共 9 页 6我们用 1 元钱表示单位代价（这里我们将对于某个点访问和旋转看作一个单 位时间的代价） 。定义伸展树不变量伸展树不变量：在任意时刻，伸展树中的任意节点 x 都至 少有(x)元的存款。 在 Splay 调整过程中，费用将会用在以下两个方面： (1)为使用的时间付费。也就是每一次
11、单位时间的操作，我们要支付 1 元钱。 (2)当伸展树的形状调整时， 我们需要加入一些钱或者重新分配原来树中每个 节点的存款，以保持不变量继续成立。 下面我们给出关于 Splay 操作花费的定理： 定理：在每一次在每一次 Splay(x,S)操作中，调整树的结构与保持伸展树不变量的总操作中，调整树的结构与保持伸展树不变量的总 花费不超过花费不超过3(S)+1。 证明：用(x)和(x)分别表示在进行一次 Zig、Zig- Zig 或 Zig- Zag 操作前后 节点 x 处的存款。 下面我们分三种情况分析旋转操作的花费： 情况一情况一：如图 9 所示 图 9 我们进行 Zig 或者 Zag 操作
12、时，为了保持伸展树不变量继续成立，我们需要 花费： (x) +(y) - (x) - (y) = (y) - (x) (x) - (x) 3(x) - (x) = 3(S) - (x) 此外我们花费另外 1 元钱用来支付访问、旋转的基本操作。因此，一次 Zig 或 Zag 操作的花费至多为3(S) - (x)。 情况二情况二：如图 10 所示 图 10 我们进行 Zig- Zig 操作时，为了保持伸展树不变量，我们需要花费： (x) +(y) +(z) - (x) - (y) - (z) = (y) +(z) - (x) - (y) = (y) - (x) + (z) - (y) IOI200
13、4 国家集训队论文 杨思雨 第 7 页 共 9 页 7 (x) - (x) + (x) - (x) = 2 (x) - (x) 与上种情况一样，我们也需要花费另外的 1 元钱来支付单位时间的操作。 当(x) (x) +(y) +(z)。 联系图 9，我们有(x) =(x) =(z)。那么，显然(x) =(y) =(z)。于是，可 以得出(x) =(z) =(z)。令 a = 1 + |A| + |B|，b = 1 + |C| + |D|，那么就有 log a = log b = log (a+b+1)。 我们不妨设ba，则有 log (a+b+1) log (2a) = 1+log a log a
