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

Question

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

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

Answer 1

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

本质上，您需要根据给定节点决定接下来的两个移动(左-左、右-右或其他任何移动)。当您向同一方向移动两次时，就会发生旋转。

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