Come posso implementare un albero splay che esegue l'operazione zig ultima, e non prima?

Question

Per la mia classe di Algoritmi e Strutture Dati, mi è stato affidato il compito di attuare un albero strombatura in Haskell. Il mio algoritmo per l'operazione splay è il seguente:

1. Se il nodo da strombato è la radice, viene restituito l'albero inalterato.
2. Se il nodo da strombato è un livello dalla radice, un'operazione zig viene eseguita e l'albero risultante viene restituito.
3. Se il nodo da strombato è due o più livelli dalla radice, a zig-zig o il funzionamento zig-zag viene eseguita sul risultato del dispiegamento sottostruttura partire da quel nodo, e l'albero risultante viene restituito.

Questo è valido secondo il mio maestro. Tuttavia, la descrizione Wikipedia di un albero strombatura dice il passo a zig "sarà fatto solo come ultima passo in un'operazione splay", mentre nel mio algoritmo è il primo passo di un'operazione splay.

Voglio realizzare un albero strombatura che esegue l'operazione zig ultima invece di prima, ma non sono sicuro di come sarebbe essere fatto meglio. Mi sembra che un tale algoritmo sarebbe diventato più complesso, visto che si ha bisogno per trovare il nodo da strombato prima di poter stabilire se un'operazione di zig deve essere eseguita o meno.

Come faccio a implementare questo in Haskell (o qualche altro linguaggio funzionale)?

Esempio

In questo esempio si cerca per il valore 4, spingendoci ad splay alla cima dell'albero.

Il mio algoritmo (zig come il primo passo)

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

Wikipedia algoritmo (zig come ultimo passaggio)

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

Entrambi gli alberi sono valide, ma hanno strutture diverse. Voglio realizzare il secondo in un linguaggio funzionale, preferibilmente Haskell.

Answer 1

La chiave è quello di costruire un percorso per il valore da strombato, quindi rigenerare l'albero dal basso, due livelli alla volta, se possibile (in modo che lo zig-zip vs. zig-zag determinazione può essere fatta):

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)

È possibile trovare questo codice, insieme al test di unità eseguibili e controlli rapidi nel mio repo .

Answer 2

Sei sicuro che stai leggendo la descrizione Wikipedia correttamente? Ci sono tre tipi di operazioni: "zig", "zig-zig", e "zig-zag". Il passo "zig" è definito di essere qualcosa che accade solo quando x è un figlio della radice. Nonostante i nomi, il "zig-zig" e "zig-zag" passaggi non hanno "zig" passi come un primo componente.

Sembra a me come l'implementazione segue la descrizione di Wikipedia in questo senso.

Answer 3

È possibile ref questo corso, che ha un molto buona nota conferenza con il codice in OCaml per Splay albero.