c - 展开树中自下而上和自上而下的方法有什么区别？

Question

我已经阅读了有关 Splay 树的信息，发现有两种构建 Splay 树的方法。他们是

1. 自下而上
2. 自顶向下

所以我需要知道这两种方法及其工作有什么区别？

Answer 1

这些方法定义了搜索时如何使用展开：

自下而上：搜索树并在同一迭代中旋转

自上而下：您首先搜索，然后在另一次迭代中旋转

你可以阅读张开树

这个想法也适用于创建，当使用自顶向下时，您插入密钥，就好像它是二叉树一样，而不是在另一个迭代中将它移动到头部。

Answer 2

自上而下的展开树：在初始访问路径上执行旋转。因此，自上而下的展开树节点不需要父链接。搜索完成后，展开操作就完成了。这意味着自顶向下展开树的操作开销相对较小。

自底向上展开树：需要从根向下遍历树，然后自底向上遍历来实现展开步骤，因此自底向上展开树的实现看起来类似于 AVL 树的实现。此外，它需要一个父链接或一个堆栈来存储搜索路径。

自顶向下展开树的实现可以在Weiss 编写的数据结构书（第 12 章）中找到。