haskellfunctional-programmingsplay-tree# How can I implement a splay tree that performs the zig operation last, not first?

## Example

### My algorithm (zig as the first step)

### Wikipedia algorithm (zig as the last step)

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

In this example we search for the value 4, prompting us to splay it to the top of the tree.

1 1 4 \ \ / 2 zig 2 zig-zig 2 \ --> \ ------> / \ 3 4 1 3 \ / 4 3

1 1 4 \ \ / 2 zig-zig 4 zig 1 \ ------> / --> \ 3 3 3 \ / / 4 2 2

Both trees are valid, but they have different structures. I want to implement the second one in a functional language, preferably Haskell.

Solution

The key is to build a path to the value to be splayed, then rebuild the tree from the bottom, two levels at a time if possible (so that the zig-zip vs. zig-zag determination can be made):

```
data Tree a = Empty | Node a (Tree a) (Tree a)
deriving (Eq, Show)
data Direction = LH | RH
deriving (Eq, Show)
splay :: (Ord a) => a -> Tree a -> Tree a
splay a t = rebuild $ path a t [(undefined,t)]
where path a Empty ps = ps
path a n@(Node b l r) ps =
case compare a b of
EQ -> ps
LT -> path a l $ (LH, l) : ps
GT -> path a r $ (RH, r) : ps
rebuild :: (Ord a) => [(Direction,Tree a)] -> Tree a
rebuild ((_,n):[]) = n
rebuild ((LH,x):(_,p):[]) = zigL x p
rebuild ((RH,x):(_,p):[]) = zigR x p
rebuild ((LH,x):(LH,p):(z,g):ps) = rebuild $ (z, zigzigL x p g):ps
rebuild ((RH,x):(RH,p):(z,g):ps) = rebuild $ (z, zigzigR x p g):ps
rebuild ((RH,x):(LH,p):(z,g):ps) = rebuild $ (z, zigzagL x p g):ps
rebuild ((LH,x):(RH,p):(z,g):ps) = rebuild $ (z, zigzagR x p g):ps
zigL (Node x a b) (Node p _ c) = Node x a (Node p b c)
zigR (Node x a b) (Node p c _) = Node x (Node p c a) b
zigzigL (Node x a b) (Node p _ c) (Node g _ d) =
Node x a (Node p b (Node g c d))
zigzigR (Node x a b) (Node p c _) (Node g d _) =
Node x (Node p (Node g d c) a) b
zigzagL (Node x b c) (Node p a _) (Node g _ d) =
Node x (Node p a b) (Node g c d)
zigzagR (Node x b c) (Node p _ a) (Node g d _) =
Node x (Node g d b) (Node p c a)
```

You can find this code, along with runnable unit tests and quick checks in my repo.

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code