Wie kann ich einen gespreizten Baum, dass führt die Zick Operation zuletzt, nicht zuerst implementieren?

Question

Für meine Algorithmen und Datenstrukturen Klasse, ich habe mit der Implementierung eines gespreizten Baum in Haskell beauftragt. Mein Algorithmus für die Spreizung Operation ist wie folgt:

1. Wenn der Knoten gespreizt werden, um die Wurzel, die unverändert Baum zurückgeführt wird.
2. Wenn der Knoten gespreizt wird, ist eine Ebene von der Wurzel, eine Zick Operation ausgeführt wird und der resultierende Baum zurückgeführt wird.
3. Wenn der Knoten gespreizt werden soll, zwei oder mehr Ebenen aus der Wurzel, einem Zick-Zick-oder Zick-Zack-Operation an dem Ergebnis durchgeführt, die Unterstruktur der abspreizende an diesem Knoten beginnt und der resultierende Baum zurückgeführt wird.

Dies gilt nach meinem Lehrer. Allerdings der Wikipedia Beschreibung eines gespreizten Baum Zick Schritt sagt „wird nur als letztes getan werden Schritt in einem gespreizten Betrieb“, während in meinem Algorithmus ist es der erste Schritt in einem gespreizten Betrieb.

Ich möchte ein Spreizfuß Baum implementieren, dass führt die Zick-Operation letzte statt erste, aber ich bin nicht sicher, wie es am besten getan werden würde. Es scheint mir, dass ein solcher Algorithmus komplexer geworden wäre, da, wie man Bedürfnisse der Knoten zu finden gespreizt werden, bevor sie, ob ein Zick-Operation bestimmt werden kann, soll oder nicht durchgeführt werden.

Wie kann ich dies in Haskell implementieren (oder eine andere funktionale Sprache)?

Beispiel

In diesem Beispiel für den Wert suchen 4 ab, sodass wir es spreizen an die Spitze des Baumes.

My Algorithmus (Zick als erster Schritt)

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

Wikipedia-Algorithmus (Zick als letzter Schritt)

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

Beide Bäume sind gültig, aber sie haben unterschiedliche Strukturen. Ich möchte die zweite in einer funktionalen Sprache implementieren, vorzugsweise Haskell.

Answer 1

Der Schlüssel ist, einen Pfad zu dem Wert zu bauen gespreizt werden, erstellen Sie dann den Baum aus dem Boden, zwei Ebene zu einer Zeit, wenn möglich (so dass die Zick-zip gegen Zick-Zack-Bestimmung kann gemacht werden):

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)

Sie können diesen Code finden, zusammen mit runnable Unit-Tests und schnellen Kontrolle in meinem Repo .

Answer 2

Sind Sie sicher, dass Sie zur Wikipedia Beschreibung lesen richtig? Es gibt drei Arten von Schritten: „Zick“, „Zick-Zick“ und „Zick-Zack“. Der „Zick“ Schritt ist definiert etwas sein, das geschieht nur, wenn x ein Kind der Wurzel ist. Trotz der Namen, die „Zick-Zick“ und „Zick-Zack“ Schritte haben keine „Zick“ Schritte als erste Komponente.

Es klingt für mich wie Ihre Implementierung der Wikipedia Beschreibung in dieser Hinsicht folgt.

Answer 3

Sie können ref dieser Kurs , unt sehr gut Skriptum mit Code in OCaml für Splay Baum.