Splay Tree——动机和宏观策略 (3)

Splay Tree——动机和宏观策略

 

通过这个例子可以看出:任何一个节点经过访问,再经双层调整后,这个节点所在的路径长度就会减半。甚至可以说——这种效果具有某种意义上的智能:既然在一棵BST中非常忌讳访问很深的节点(这会导致复杂度急剧上升),那这种折叠效果自然就会具有对坏节点的修复作用,我们就不必担心了。犹如含羞草一旦感受到威胁,就会通过迅速收缩,将自己的弱点隐藏起来。因此在采用Tarjan所建议的这种新的策略之后,刚才所举的那种最坏情况就不至持续的发生,可以证明的是单次操作的时间上界是O(logN)。这也就是说我们现在不仅足以应对此前涉及的最坏情况而且也不会有任何其他的最坏情况这是一个再好不过的消息了,简直让人开心到爆炸啊!

 

为了控制篇幅,也考虑到注意力的问题,具体的实现放在下一篇文章,因为那将会涉及到很多指针调整,需要集中精力,看到这里想必注意力消耗的差不多了,再看下去就容易跑神,具体的实现步骤相比上面的清谈要更耗费心力,因为我们要和细节打交道了。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyzfjs.html