我读过有关 Splay 树的资料,发现有两种构建 splay 树的方法。他们是
- 自下而上
- 自上而下
所以我需要知道这两种方法及其工作方式有什么区别?
最佳答案
自上而下的拉伸(stretch)树:在初始访问路径上执行旋转。因此,自上而下的伸展树(Splay Tree)节点不需要父链接。展开操作在搜索完成后立即完成。这意味着自上而下的伸展树(Splay Tree)的操作开销相对较小。
自下而上的伸展树(Splay Tree):需要从根向下遍历树,然后自下而上遍历来实现展开步骤,因此自下而上的伸展树(Splay Tree)实现类似于一棵 AVL 树。此外,它还需要父链接或堆栈来存储搜索路径。
可以在数据结构book 中找到自顶向下伸展树(Splay Tree)的实现。 (第 12 章)由 Weiss 撰写。
关于c - 伸展树(Splay Tree)中自下而上和自上而下的方法有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27793779/