c - 伸展树(Splay Tree)中自下而上和自上而下的方法有什么区别？

Question

我读过有关 Splay 树的资料，发现有两种构建 splay 树的方法。他们是

1. 自下而上
2. 自上而下

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

Answer 1

自上而下的拉伸(stretch)树:在初始访问路径上执行旋转。因此，自上而下的伸展树(Splay Tree)节点不需要父链接。展开操作在搜索完成后立即完成。这意味着自上而下的伸展树(Splay Tree)的操作开销相对较小。

自下而上的伸展树(Splay Tree):需要从根向下遍历树，然后自下而上遍历来实现展开步骤，因此自下而上的伸展树(Splay Tree)实现类似于一棵 AVL 树。此外，它还需要父链接或堆栈来存储搜索路径。

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