首页
学习
活动
专区
圈层
工具
发布
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

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

    上次说了自底向上用栈实现的伸展树,但是那样实现的伸展树一是需要遍历两次树才能展开,另一缺点是需要占用较大的多余空间(额外的一个足够深的栈),但使用另一种方法,利用两个辅助指针和一个新的头节点,我们使用左右两个子树来完成自顶而下的伸展树展开...找到目标结点后把目标结点下的子树接到对应临时子树上,然后替换头结点展开就完成了。若找不到目标结点就直接把最后路径的最后一个结点替换到头,这样就不会浪费一次查找的展开效果。下面是图解和代码。 ?...然后我们从32到1插入一棵树并试着展开一下。 ? ? ? ? ? 可以看到树正常运作了。...在这里顺便要说一下,自顶而下的伸展与上次的伸展其实是不一样的,只是都能保证较小的时间复杂度和都有降低高度作用,所以实际上尝试后会发现对于同一棵树两种展开得到的结果并不会一定相同,但是高度降低都显而易见。

    39120
    领券