【CPP】各种各样的树（7）——自顶而下的伸展树

上次说了自底向上用栈实现的伸展树，但是那样实现的伸展树一是需要遍历两次树才能展开，另一缺点是需要占用较大的多余空间（额外的一个足够深的栈），但使用另一种方法，利用两个辅助指针和一个新的头节点，我们使用左右两个子树来完成自顶而下的伸展树展开。

展开的方法稍有变化，我们把旋转分为单旋转和一字形旋转，从目前结点向下访问两个结点，若形成一字形则先把目前结点单旋转，然后接到对应方向的子树上（向右访问则接到左边，反之亦是），然后将目前结点下移，若其他情况则不用双旋转，其他照常。找到目标结点后把目标结点下的子树接到对应临时子树上，然后替换头结点展开就完成了。若找不到目标结点就直接把最后路径的最后一个结点替换到头，这样就不会浪费一次查找的展开效果。下面是图解和代码。

理解了伸展的操作后，插入与删除也就不难了，这次有了一点点改进，插入的时候也要进行展开，让刚插入的值排在头，删除与之前差不多，利用这次改进的空展开来获取空指针域来拼接树。

然后我们从32到1插入一棵树并试着展开一下。

可以看到树正常运作了。在这里顺便要说一下，自顶而下的伸展与上次的伸展其实是不一样的，只是都能保证较小的时间复杂度和都有降低高度作用，所以实际上尝试后会发现对于同一棵树两种展开得到的结果并不会一定相同，但是高度降低都显而易见。

这份伸展树的其他部分与之前没什么区别，旋转也是AVL的旋转，Display也是之前的代码，等之后一并放出吧。看完伸展树下次来看个比较轻松的树，是关于二叉树的一种实际应用，一种压缩数据的算法——赫夫曼树。