6

アルゴリズムとデータ構造のクラスでは、Haskell でスプレイ ツリーを実装するタスクを課されました。スプレー操作の私のアルゴリズムは次のとおりです。

  1. 表示するノードがルートの場合、変更されていないツリーが返されます。
  2. 表示されるノードがルートから 1 レベルの場合、ジグ操作が実行され、結果のツリーが返されます。
  3. 展開するノードがルートから 2 レベル以上の場合、そのノードから始まるサブツリーを展開した結果に対してジグジグまたはジグザグ操作が実行され、結果のツリーが返されます。

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

ジグ操作を最初ではなく最後に実行するスプレイ ツリーを実装したいのですが、どのように実行するのが最適かわかりません。ジグ操作を実行する必要があるかどうかを判断する前に、展開するノードをどのように見つける必要があるかを考えると、そのようなアルゴリズムはより複雑になると思われます。

Haskell (または他の関数型言語) でこれを実装するにはどうすればよいですか?

例

この例では、値 4 を検索し、それをツリーの一番上に表示するように求めています。

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

1 1 4
 \ \ /
  2 ジグ 2 ジグジグ 2
   \ --> \ ------> / \
    3 4 1 3
     \ /
      4 3

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

1 1 4
 \ \ /
  2 ジグジグ 4 ジグ 1
   \ ------> / --> \
    3 3 3
     \ / /
      4 2 2

どちらのツリーも有効ですが、構造が異なります。2 つ目は関数型言語、できれば Haskell で実装したいと考えています。

4

3 に答える 3

3

重要なのは、展開する値へのパスを構築し、可能であれば一度に 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)

このコードは、実行可能な単体テストとクイック チェックと共に、私のレポにあります。

于 2010-05-21T07:36:30.403 に答える
0

このコースを参照することができます。このコースには、スプレーツリー用のOCamlのコードを含む非常に優れた講義ノートがあります。

于 2010-05-19T04:42:34.830 に答える
0

ウィキペディアの説明を正しく読んでいますか? ステップには「ジグ」「ジグジグ」「ジグザグ」の3種類があります。「ジグ」ステップは、がルートの子である場合にのみ発生するものとして定義されています。x名前にもかかわらず、「ジグジグ」および「ジグザグ」ステップには、最初のコンポーネントとして「ジグ」ステップがありません。

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

于 2010-05-19T01:22:21.530 に答える