How can I implement a splay tree that performs the zig operation last, not first?
- by Jakob
For my Algorithms & Data Structures class, I've been tasked with implementing a splay tree in Haskell. My algorithm for the splay operation is as follows:
If the node to be splayed is the root, the unaltered tree is returned.
If the node to be splayed is one level from the root, a zig operation is performed and the resulting tree is returned.
If the node to be splayed is two or more levels from the root, a zig-zig or zig-zag operation is performed on the result of splaying the subtree starting at that node, and the resulting tree is returned.
This is valid according to my teacher. However, the Wikipedia description of a splay tree says the zig step "will be done only as the last step in a splay operation" whereas in my algorithm it is the first step in a splay operation.
I want to implement a splay tree that performs the zig operation last instead of first, but I'm not sure how it would best be done. It seems to me that such an algorithm would become more complex, seeing as how one needs to find the node to be splayed before it can be determined whether a zig operation should be performed or not.
How can I implement this in Haskell (or some other functional language)?
