5

私はHaskellでRBツリーの実装をいじっていますが、バイナリリーフツリーのようにデータがリーフにのみ配置されるように少し変更するのに苦労しています。

    /+\
   /   \
 /+\    \
/   \    c
a   b

内部ノードは、ノードの色に加えて、ツリーのサイズなどの他の情報を保持します（通常のRBツリーのように、データは葉に保持されます）。また、挿入されるデータを並べ替える必要もありません。データを挿入するときにバランスの取れたツリーを取得するためにのみRBを使用しますが、データが挿入される順序を維持したいと思います。

元のコードは（岡崎の本から）：

data Color = R | B
data Tree a = E | T Color (Tree a ) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x s = makeBlack (ins s)
    where ins E = T R E x E
        ins (T color a y b) 
            | x < y = balance color (ins a) y b
            | x == y = T color a y b
            | x > y = balance color a y (ins b)
        makeBlack (T _ a y b) = T B a y b

私はそれを次のように変更しました:(例外：関数insの非網羅的なパターンの原因）

data Color = R | B deriving Show
data Tree a = E | Leaf a | T Color Int (Tree a) (Tree a)

insert :: Ord a => a -> Set a -> Set a
insert x s = makeBlack (ins s)
    where 
        ins E = T R 1 (Leaf x) E
        ins (T _ 1 a E) = T R 2 (Leaf x) a
        ins (T color y a b)
            | 0 < y = balance color y (ins a) b
            | 0 == y = T color y a b
            | 0 > y = balance color y a (ins b)
        makeBlack (T _ y a b) = T B y a b

元のバランス関数は次のとおりです。

balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance color a x b = T color a x b

上記のコードから明らかなように、これを少し変更しました。

助けてくれてありがとう:)

編集：私が探している種類の表現については、Chris Okasakiが、彼の本で説明されているように、バイナリランダムアクセスリストを使用することを提案しました。別の方法は、ウェイトバランスの取れたツリーとして実装されているData.Setのコードを単純に適応させることです。

4

1 に答える 1

1

あなたがを意味していると仮定するとinsert :: a -> Tree a -> Tree a、あなたのエラーはおそらく。の句がないことに起因しますins (Leaf a)。

于 2011-06-09T20:23:47.903 に答える