通过这个例子可以看出:任何一个节点经过访问,再经双层调整后,这个节点所在的路径长度就会减半。甚至可以说——这种效果具有某种意义上的智能:既然在一棵BST中非常忌讳访问很深的节点(这会导致复杂度急剧上升),那这种折叠效果自然就会具有对坏节点的修复作用,我们就不必担心了。犹如含羞草一旦感受到威胁,就会通过迅速收缩,将自己的弱点隐藏起来。因此在采用Tarjan所建议的这种新的策略之后,刚才所举的那种最坏情况就不至持续的发生,可以证明的是单次操作的时间上界是O(logN)。这也就是说!我们现在不仅足以应对此前涉及的最坏情况,而且也不会有任何其他的最坏情况,这是一个再好不过的消息了,简直让人开心到爆炸啊!
为了控制篇幅,也考虑到注意力的问题,具体的实现放在下一篇文章,因为那将会涉及到很多指针调整,需要集中精力,看到这里想必注意力消耗的差不多了,再看下去就容易跑神,具体的实现步骤相比上面的清谈要更耗费心力,因为我们要和细节打交道了。