algorithm - 我可以使用递归算法来实现 Splay 树吗？

Question

我一直在研究 Splay 树，因为我想实现一个。目前，我对红黑树、AVL 树、跳过列表和其他更简单的数据结构有一些“自学”经验。我想实现我的第一个展开树，但如果可能的话，我想要一个递归实现（我喜欢递归）。

但是，我认为这很困难，因为您必须在树下查看两个级别才能观察所有可能的情况（zig-zag、zig-zig、zar），并且没有其他字段就无法标记目标。我是否应该使用另一个字段（例如红黑树）来标记访问的节点并展开目标节点？

Answer 1

使用递归算法很容易，而且看起来相当干净。不需要标记。请记住，展开操作（用于查找、插入和删除）将目标节点带到树的顶部；换句话说，它返回目标节点位于顶部的（展开的）树。

本质上，您需要从给定节点决定接下来的两次移动将是什么（左右移动或其他任何移动）。当您向同一方向移动两次时会发生旋转。

在 Chris Okasaki 的Purely Functional Data Structures中有一个很好的函数式语言实现，恕我直言，这是现存最好的 CS 短文之一。

Answer 2

在 wikipedia 上，您可以找到一篇关于展开树的非常好的文章。你不应该喜欢递归，因为递归很容易失控，最好使用迭代。