0

次の形式のカスタム ツリー データ型があるとします。

data BalTree a = Leaf | Node Integer (BalTree a) a (BalTree a) deriving (Eq, Show, Read)

サイズ 10 の新しいツリーを作成すると、次のようになります。

Node 10 (Node 5 (Node 2 (Node 1 Leaf 'Z' Leaf) 'Z' Leaf)
                 'Z'
                (Node 2 (Node 1 Leaf 'Z' Leaf) 'Z' Leaf))
'Z'
        (Node 4 (Node 2 (Node 1 Leaf 'Z' Leaf) 'Z' Leaf)
                 'Z'
                 (Node 1 Leaf 'Z' Leaf))

インデックスが与えられたときに要素をインオーダー トランスバーサルで取得するにはどうすればよいですか?

私の試み：

ind Leaf pos            = Nothing
ind tree@(Node n lt x rt) pos
    | pos < 0           = Nothing
    | pos > treeSize-1  = Nothing
    | pos < hTreeSize   = ind lt pos
    | pos == hTreeSize  = Just x
    | pos > hTreeSize   = ind rt (pos - hTreeSize)
    where treeSize = size tree
          hTreeSize = treeSize `div` 2

これが順序どおりの横断であり、正しい結果が返されないかどうかは正確にはわかりません。

4

1 に答える 1

2

二分木に格納された n 番目の値を順序付きウォークで取得したいと考えています。Integer各ノード ( のパラメータ) をルートとする各ツリーに格納されている値の数がわかりますNode。

data BalTree a = Leaf
               | Node Integer (BalTree a) a (BalTree a)

size :: BalTree a -> Integer
size Leaf              = 0
size (Node size _ _ _) = size

nthInOrder :: BalTree a -> Integer -> Maybe a
nthInOrder Leaf _ =
    Nothing
nthInOrder (Node _ left x right) n
    | leftSize == n - 1 = Just x
    | n <= leftSize     = nthInOrder left n
    | otherwise         = nthInOrder right (n - leftSize - 1)
  where
    leftSize  = size left

アイデアは次のとおりです。ノードにいて、 th 値Aが必要だとします。n

  A
 / \
B   C

Bが値を保持している場合n-1、n番目の値はの値ですA。B以上の値を保持する場合n、残りのツリーを無視して検索のみを行うことができBます。そのため、再帰するだけです。それ以外の場合は、 の値を探す必要があるため、C再帰します。この場合、 にいくつかの値があり、 に 1 つの値nがあることを反映するために も更新する必要があります。BA

最悪の場合、このアルゴリズムは まで進むLeafため、複雑さは になりO(depth of tree)ます。ツリーのバランスがとれている場合、複雑さはO(log2(size of tree))です。

于 2013-03-27T19:39:23.303 に答える