数据结构与算法分析 8.9分
读书笔记 4.5 伸展树
knightley
伸展树(splay tree),它保证从空树开始任意M次对树的操作最多花费O(M logN)时间。虽然这种保证并不排除任意一次操作花费O(N)时间的可能,而且这样的界也不如每次操作最坏情形的界O(logN)那么短,但是实际效果是一样的:不存在坏的输入序列。一般说来,当M次操作的序列总的最坏情形运行时间为O(MF(N))时,我们就说它的摊还(amortized)运行时间为O(F(N))。因此,一棵伸展树每次操作的摊还代价是O(logN)。经过一系列的操作之后,有的可能花费时间多一些,有的可能要少一些。
伸展树基于这样的事实:对于二叉查找树来说,每次操作最坏情形时间O(N)并不坏,只要它相对不常发生就行。任何一次访问,即使花费O(N),仍然可能非常快。二叉查找树的问题在于,虽然一系列访问整体都有可能发生不良操作,但是很罕见。此时,累积的运行时间很重要。具有最坏情形运行时间O(N)但保证对任意M次连续操作最多花费O(M logN)运行时间的查找树数据结构确实可以满意了,因为不存在坏的操作序列。
如果任意特定操作可以有最坏时间界O(N),而我们仍然要求一个O(logN)的摊还时间界,那么很清楚,只要一个节点被访问,它就必须被移动。否则,一旦我们发现一个深层的节点,我们就有可能不断对它进行Find操作。如果这个节点不改变位置,而每次访问又花费O(N),那么M次访问将花费O(M*N)时间。
伸展树的基本想法是,当一个节点被访问后,它就要经过一系列AVL树的旋转被放到根上。注意,如果一个节点很深,那么在其路径上就存在许多的节点也相对较深,通过重新构造可以使对所有这些节点的进一步访问所花费的时间变少。因此,如果节点过深,那么我们还要求重新构造应具有平衡这棵树(到某种程序)的作用。除在理论上给出好的时间界外,这种访问还可能有实际的效用,因为在许多应用中当一个节点被访问时,它就很有可能不久再被访问到。研究表明,这种情况的发生比人们预料的要频繁得多。另外,伸展树还不要求保留高度或平衡信息,因此它在某种程度上节省空间并简化代码(特别是当实现例程经过审慎考虑而被写出的时候)。

伸展树的概念提出,以及伸展树的基本想法。注意伸展树属于二叉查找树,具有二叉查找树的性质。(性质是 对于树中的每个节点X,它的左子树中所有关键字值小于X的关键字值,而它的右子树中所有关键字值大于X的关键字值 )

4.5.2 展开
展开的思路类似于前面介绍的旋转的想法,不过在旋转如何实施上我们稍微有些选择的余地。我们仍然从底部向上沿着访问路径旋转。令X是在访问路径上的一个(非根)节点,我们将在这个路径上实施旋转操作。如果X的父节点是树根,那么我们只要旋转X和树根。这就是沿着访问路径上的最后的旋转。否则,X就有父亲(P)和祖父(G),存在两种情况以及对称的情形要考虑。第一种情况是之字形情形(见图4-44)……否则,出现另一种一字形情形。(参见P92)

……

我们可以通过访问要被删除的节点实行删除操作。这种操作将节点上推到根处。如果删除该节点,则得到两棵子树TL和TR(左子树和右子树)。如果我们找到TL中的最大的元素(这很容易),那么这个元素就被旋转到TL的根下,而此时TL将有一个没有右儿子的根。我们可以使TR为右儿子从而结束删除。

介绍在访问和删除伸展树的节点时,伸展树应该如何展开变化。

google查询了一些伸展树的实现方法,方法很多(不单单是树上介绍的这种展开方法),一般只要把访问到的节点旋转到根上就可以。

0
《数据结构与算法分析》的全部笔记 67篇
豆瓣
免费下载 iOS / Android 版客户端