Splay树中自底向上和自顶向下方法有什么区别？

Question

我了解了伸展树（Splay tree），发现构建伸展树有两种方法。

1. 自下而上（Bottom-up）
2. 自上而下（Top-down）

那么，这两种方法之间有什么区别以及它们的工作原理是什么？

- Bhuvanesh

Answer 1

一个自顶向下伸展树：在初始访问路径上执行旋转操作。因此，自顶向下伸展树节点不需要父链接。伸展操作在搜索完成后立即结束。这意味着自顶向下伸展树的操作开销相对较小。 自底向上伸展树：需要从根节点向下遍历树，然后进行自底向上遍历以实现伸展步骤，因此自底向上伸展树的实现类似于AVL树。此外，它需要一个父链接或堆栈来存储搜索路径。

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

- Yossarian42

Answer 2

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

自底向上：您在搜索树的同时进行旋转

自顶向下：您首先进行搜索，然后在另一个迭代中进行旋转

您可以阅读伸展树。

当使用自顶向下时，这些想法也适用于创建。您将键插入二叉搜索树中，然后在另一个迭代中将其移动到头部。

- antonpuz

---

我认为自底向上是两个步骤（首先将树作为二叉搜索树遍历，然后向后旋转一个节点直到它成为根），而自顶向下则只需要一次旋转（在遍历树的同时进行原地旋转）。 - hlide