查找树的相关知识 这些查找树的设计目标都是减少最坏情况下单次操作时间，但是查找树的典型应用经常需要执行一系列的查找操作，此时更关心的性能指标是所有这些操作总共需要多少时间。对于此类应用，更好的目标就是降低操作的摊平时间，此处的摊平时间是指在一系列最坏情况的操作序列中单次操作的平均时间。获得摊平效率的一种方法 就是使用“自调整”的数据结构。 和平衡的或是其它对结构有明确限制的数据结构比起来，自调整数据结构有以下几个优点： 2、由于无需存储平衡或者其它的限制信息，它们所需的空间更小。 3、它们的查找和更新算法概念简单，易于实现。 2、一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。 已知重构方法与伸展树的重构方法 splay tree的重构方法和搬移至树根的方法相似，它也会沿着查找路径做自底向上的旋转，将被查找条目移至树根。但不同的是，它的旋转是成对进行的，顺序取决于查找路径的结构。为了在节点x处对树进行splay操作，我们需要重复下面的步骤，直至x成为树根为止： 1、第一种情况：如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。（这种情况是最后一步） 2、第二种情况：如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(x)的边。 3、第三种情况：如果
Read full article from POJ 3481 Double Queue - botaowudi - 博客园
No comments:
Post a Comment