Comment puis-je mettre en œuvre un arbre évasement qui effectue l'opération en zig dernière, pas d'abord?

Question

Pour ma classe Structures et algorithmes de données, j'ai été chargé de mettre en œuvre un arbre évasement en Haskell. Mon algorithme pour l'opération d'évasement est la suivante:

1. Si le nœud à évasé est la racine, l'arbre non modifié est retourné.
2. Si le nœud à évasé est un niveau de la racine, une opération de zig est réalisée et l'arbre résultant est retourné.
3. Si le noeud à évasé est deux ou plusieurs niveaux à partir de la racine, une opération en zig-zig, ou en zig-zag est effectuée sur le résultat de l'évasement de la sous-arborescence à partir de ce noeud, et l'arbre résultant est renvoyé.

Ceci est valable selon mon professeur. Cependant, la description Wikipédia d'un arbre évasement dit l'étape de zig « se fera qu'en dernier étape dans une opération de évasement » alors que dans mon algorithme est la première étape d'une opération d'évasement.

Je veux mettre en œuvre un arbre évasement qui exécute l'opération de zig dernière au lieu de la première, mais je ne sais pas comment il serait mieux fait. Il me semble qu'un tel algorithme deviendrait plus complexe, car la façon dont on a besoin de trouver le nœud à évasé avant de pouvoir déterminer si une opération de zig doit être effectuée ou non.

Comment puis-je implémenter dans Haskell (ou une autre langue fonctionnelle)?

Exemple

Dans cet exemple, nous cherchons la valeur 4, nous invitant à évaser au sommet de l'arbre.

Ma algorithme (zig comme la première étape)

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

Wikipedia algorithme (zig comme la dernière étape)

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

Les deux arbres sont valables, mais ils ont des structures différentes. Je veux mettre en œuvre le second dans un langage fonctionnel, de préférence Haskell.

Answer 1

La clé est de construire un chemin de la valeur à évasé, puis reconstruire l'arbre à partir du bas, deux niveaux à la fois si possible (de sorte que le zig-zip vs. zigzag détermination peut être effectuée):

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)

Vous pouvez trouver ce code, ainsi que des tests unitaires et des contrôles rapides exécutables dans mon repo .

Answer 2

Etes-vous sûr que vous lisez correctement la description Wikipédia? Il existe trois types de mesures: "zig", "zig-zig" et "zig-zag". Le « zig » étape est défini pour quelque chose qui ne se produit que lorsque x est un enfant de la racine. Malgré les noms, le « zig-zig » et « zig-zag » étapes ne sont pas des mesures « zig » en tant que premier composant.

Il me semble que votre implémentation suit la description de Wikipédia à cet égard.

Answer 3

Vous pouvez ref ce cours , qui a très bonne note de lecture avec le code en OCaml pour arbre Splay.