java - 自动调整伸展树(Splay Tree)的旋转策略

Question

我必须使用java实现伸展树(Splay Tree)结构。给定一个名为 Node 的类，它具有:

1. 左、右 child
2. 信息(整数)
3. 节点的高度

我的作业包括创建“插入”方法。

我已经尝试了一些策略，但到目前为止还没有奏效，我试图通过获取代码而不是获取一些可以帮助我的想法来获得一些帮助。

所以我首先的策略是实现递归方法，像二叉搜索树一样插入信息，然后展开(使用伪代码):

    Node splay(Node a, int x):
      if a.height >=3:{
         if (there is a node from "a" with the structure of zigzig or zigzag with x info){
         return a(do the rotation)}
}
      else:{
         return Node(splay(a.left,x),a.info,splay(a.right,x))}

我不完全确定这个想法是否适用于锯齿形和锯齿形。

另一方面，我没有节点父节点的信息，所以我在如何进行之字形和锯齿形旋转方面遇到了麻烦，我尝试使用 a.height==1，但这会遇到麻烦

Answer 1

您在此处描述的策略称为自下而上展开，并且是查看所描述的展开的最常见方式。您执行正常的查找来查找所需的节点，然后应用 playbook 中的规则(zig、zig-zag 或 zig-zig)将该节点拉到树的根部。

还有另一种策略可以用来实现展开，称为自上而下展开，它通过在从根节点遍历到目标节点时 reshape 树的形状来实现展开。您可以通过将树分成两棵树(称为左树和右树)来实现展开操作，然后通过智能地将这些树组合在一起来完成展开。这不需要使用递归，并且不需要父指针。您可以在 section 4 of Sleator and Tarjan's original paper on splay trees 中找到有关如何执行此操作的详细信息。 。那里的伪代码不能一对一地翻译成 Java(例如，他们有一个名为“null”的显式节点，他们假设您可以调整其左右子节点)，但基本思想一次也不错您已经查看了他们的数据并完成了案例。