陈启峰 WC2007论文 数据结构 Size Balanced Tree 方法来证明，对于任意整数n*，P(n*)都是成立的。
6.4.1 证明
这里我只给出大概的证明。
假设结点t已经被Maintain(t,false)检查过，则有
第8页
s[left[t]]?1?s[right[t]]?2
2s[t]?1s[left[t]]?3因此如果一个结点到根的路径上的所有结点都已经被Maintain检查过，那么这个结点的深度就是O(logn)。 （1）对于n*=1，很明显P(n*)是真的；
（2）假设对于P(n*)在n* 一棵树。对于树中的每一个叶子，由它指向的子树不会在Maintain中被改变[7]。所以子树中结点的深度不会比O(logn*)+O(logn*)=O(logn*)大。 （3）因此，当n*=1,2,3…时，P(n*)是正确的。 这种方法证明出来的Maintain平摊时间依旧是O(1)。 6.5 分析更快更简单的Maintain 这里讨论有关为什么Maintain(left[t],true)和Maintain(right[t],false)被省略。 在情况1的图3.1[8]中，我们有 s[L]?2s[R]?1?2s[L]?14s[R]?1s[B]???332s[B]?18s[R]?3 s[E],s[F]???39?8s[R]?3?s[E],s[F]???s[R]?9??因此Maintain(right[t],false)相当于图3.1中的Maintain(T,false)，能够被省略。同样的，Maintain(left[t],true)明显的也不需要。 在情况2的图3.2中，我们有 ?s[A]?s[E] ??s[F]?s[R]这些不平衡也意味着E的子树大小要比s[A]小，F的子树大小要比s[R]小。因而Maintain(right[t],false)和Maintain(left[t],true)可以被省略。 7 优点 7.1 SBT跑得快 7.1.2 典型问题 写一个执行n个由输入给定的操作，他们分别是： 1） 在有序集合中插入一个给定的数字； 2） 从有序集合中删除一个给定的数字； 3） 返回一个给定的数字是否在有序集合中； 4） 返回一个给定的数字在有序集合中的排名； 5） 返回有序集合中第k大的数字； 6） 返回有序集合中一个给定数字前面的数字； 7） 返回有序集合中一个给定数字后面的数字。 7.1.2 统计 陈启峰 WC2007论文 数据结构 Size Balanced Tree 插入200万个随机值结点 16 14 12 第9页 单位：秒10 8 6 4 2 0 AVL 8.34 Treap 11.36 Random BST 13.61 SBT 7.13 16 14 12 200万个操作，66%为插入，33%为删除，全部随机 单位：秒 10 8 6 4 2 0 SBT 5．59 AVL 7．42 Treap 8．86 Random BST 10．47 200万个操作，20%为插入，10%为删除，60%查询，全部随机 8 7 6 单位：秒 5 4 3 2 1 0 SBT 3．39 AVL 4．42 Treap 5．67 Random BST 6．21 陈启峰 WC2007论文 数据结构 Size Balanced Tree 第10页 在现实中，Size Balanced Tree运行优秀，从上面的图表就能看出，同样都在随机数据的情况下，SBT比其它平衡BST要快得多。此外，如果是有序数据，SBT将会是意想不到的快速。它仅仅花费2s就将200万个有序数据结点插入到SBT中。 7.2 SBT运行高效 当Maintain运行的时候平均深度一点也不会增加，因为SBT总是趋近于一个完美的BST。 插入200万个随机值结点 类型 平均深度 高度 旋转次数 SBT 19.2415 24 1568017 AVL 19.3285 24 1395900 Treap 26.5062 50 3993887 随机BST 25.5303 53 3997477 Splay 37.1953 78 25151532 完美的BST 18.9514 20 ? 插入200万个有序值结点 类型 平均深度 高度 旋转次数 SBT 18.9514 20 1999979 AVL 18.9514 20 1999979 Treap 25.6528 51 1999985 随机BST 26.2860 53 1999991 Splay 999999.5 1999999 0 完美的BST 18.9514 20 ? 7.3 SBT调试简单 首先我们可以输入一个简单的BST来保证不会出错，然后我们在插入过程中加入Maintain，并调试。如果发生错误也只需要调试和修改Maintain。此外，SBT不是基于随机性的数据结构，所以它要比Treap，跳跃表（Skip List），随机BST等更稳定。 7.4 SBT书写简单 SBT几乎是和BST同样简单。仅仅在插入过程中有一个附加的Maintain，它也仅仅比BST先旋转[9]。而且Maintain也是同样的相当容易。 7.5 SBT小巧玲珑 许许多多的平衡二叉搜索树，例如SBT，AVL，Treap，红黑树等等都需要额外的域去保持平衡。但是他们中的很多都有着毫无用处的域，像高度（height），随机因子（random factor）和颜色（color）。而相反的是SBT包含一个十分有用的额外域，大小（size）域。通过它我们可以让BST支持选择（Select）操作和排名（Rank）操作。 7.5 SBT用途广泛 现在SBT的高度是O(logn)，即便在最坏情况下我们也可以在O(logn)时间内完成Select过程。但是这一点伸展树（Splay）却不能很好的支持。因为它的高度很容易退化成O(n)。上面的图表已经显示出这一点[10]。 感谢 作者感谢他的英语老师Fiona热情的帮助。 参考 [1] G.M.Adelson-Velskii and E.M.Landis, “An algorithm for the Organization of Information”, Soviet.Mat.Doklady (1962) [2] L.J.Guibas and R.Sedgewick, “A dichromatic Framework for Balanced Trees”, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science (1978) [3] D. D. Sleator and R. E. Tarjan, ?Self-adjusting binary search trees?, JACM, 32, 652–686 (1985). [4] S.W.Bent and J.R.Driscoll, Randomly balanced searchtrees. Manuscript (1991). [5] Raimund Seidel and Cecilia R. Aragony, Randomized Search Trees.(1996). [6] M.A.Weiss, ??Data Structures and Algorithm Analysis in C++??, Third Edition, Addison Wesley, 2006. [7] R.E. Tarjan, ??Sequential access in splay trees takes linear time??, Combinatorica 5(4), 1985, pp. 367-378. [8] J. Nievergelt and E. M. Reingold, ?Binary search trees of bounded balance?, SIAM J. Computing, 2, 33–43 (1973). [9] K.Mehlhorn, and A.Tsakalidis, “Data Structures,” in Handbook of Theoretical Computer Science, Chapter 6, Vol.A,
相关推荐：
loading