最初にではなく、Zig操作を最後に実行するスプレーツリーを実装するにはどうすればよいですか？

Question

アルゴリズムとデータ構造のクラスでは、HaskellにSplayツリーを実装することを任されています。スプレー操作の私のアルゴリズムは次のとおりです。

1. スプレイされるノードがルートである場合、変更されていないツリーが返されます。
2. スプレイされるノードがルートから1レベルである場合、zig操作が実行され、結果のツリーが返されます。
3. スプレイされるノードがルートから2つ以上のレベルである場合、そのノードから始まるサブツリーが散布された結果、zig-zigまたはzig-zagの操作が実行され、結果のツリーが返されます。

これは私の先生によると有効です。でも、 スプレーツリーのウィキペディアの説明 私のアルゴリズムでは、スプレー操作の最初のステップであるのに対し、Zigステップは「スプレイ操作の最後のステップとしてのみ行われる」と述べています。

最初ではなく最後にZig操作を実行するスプレーツリーを実装したいのですが、どのように行うのが最善かわかりません。そのようなアルゴリズムは、ZIG操作を実行する必要があるかどうかを判断する前に、ノードを散布する必要があると考えて、そのようなアルゴリズムがより複雑になるように思えます。

Haskell（または他の機能的言語）にこれを実装するにはどうすればよいですか？

例

この例では、値4を検索し、ツリーの上部に広がるように促します。

私のアルゴリズム（最初のステップとしてのzig）

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

ウィキペディアアルゴリズム（最後のステップとしてのzig）

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

両方の木は有効ですが、異なる構造を持っています。機能的な言語、できればHaskellで2番目のものを実装したいと思います。

Answer 1

重要なのは、スプレイされる値へのパスを構築してから、可能であれば（Zig-Zip vs. Zig-Zagの決定を下すことができるように）、一度に2つのレベルを下から再構築することです。

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)

このコードは、実行可能なユニットテストと私のクイックチェックとともに見つけることができます レポ.

Answer 2

ウィキペディアの説明を正しく読んでいると確信していますか？ 「Zig」、「Zig-Zig」、「Zig-Zag」の3種類のステップがあります。 「zig」ステップはです 定義されています ときだけ起こる何かになること x ルートの子です。名前にもかかわらず、「Zig-Zig」と「Zig-Zag」の手順には、最初のコンポーネントとして「Zig」ステップがありません。

この点で、あなたの実装がウィキペディアの説明に従っているように聞こえます。

Answer 3

参照できます このコース, 、Splay TreeのOCAMLのコードを使用した非常に良い講義ノートがあります。