Auto adjusting rotations strategy in splay trees

Question

I have to implement the splay tree structure using java. Given a class called Node that has :

1. the left, right child
2. info (an int)
3. the height of a node

my homework consist to create the "insert" method.

I've tried some strategies but it hasnt work so far, im trying to get some help not by getting the code but some ideas that can help me.

So my strategy at first, was to implement a recursive method, inserting the info just like a binary search tree and then splay (using pseudocode):

    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))}

Im not completly sure that this idea work for the zigzig and zagzag.

On the other hand i do not have the info of the parent of a Node, so im having trouble on how to do the zig and zag rotations, i tried using a.height==1, but this will have trouble

Answer 1

The strategy that you're describing here is called bottom-up splaying and is the most common way to see splaying described. You do a normal lookup to find the node that you want, then apply rules from the playbook (zig, zig-zag, or zig-zig) to pull that node up to the root of the tree.

There's another strategy you can use to implement splaying called top-down splaying that implements splaying by reshaping the tree as you traverse from the root to the target node. You can implement the splay operation by splitting the tree apart into two trees called a left tree and right tree, then finalizing the splay by combining those trees together intelligently. This doesn't require the use of recursion and eliminates the need for parent pointers. You can find details about how to do this in section 4 of Sleator and Tarjan's original paper on splay trees. The pseudocode there is not one-to-one translatable into Java (for example, they have an explicit node called "null" that they assume you can adjust the left and right children of), but the basic idea isn't too bad once you've checked out their figures and worked through the cases.