0

我必须使用java实现splay树结构。给定一个名为 Node 的类，它具有：

  1. 左，右孩子
  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))}

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

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

4

1 回答 1

0

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

您可以使用另一种策略来实现展开，称为自上而下展开，它通过在从根遍历到目标节点时重塑树来实现展开。您可以通过将树分成两棵树（称为左树和右树）来实现展开操作，然后通过智能地将这些树组合在一起来完成展开操作。这不需要使用递归，也不需要父指针。您可以在Sleator 和 Tarjan 的关于伸展树的原始论文的第 4 节中找到有关如何执行此操作的详细信息. 那里的伪代码不能一对一地翻译成 Java（例如，他们有一个名为“null”的显式节点，他们假设您可以调整其左右子节点），但基本想法一次还不错你已经检查了他们的数据并处理了这些案例。

于 2019-06-22T01:22:50.243 回答