1

私はまだこれに対する解決策を見つけるのに苦労していますが、質問、私はおそらくもっと簡単な別のものを持っています。以下は、岡崎赤黒木実装の挿入機能です。私がやりたいことは、ツリーに挿入するときにデータをソートしないようにすることです。したがって、挿入するたびに、データは常に左端/下端の葉に移動します。x < y、x > y、または x == y を比較する必要はありません。これらのガードを削除するだけで、最初は非常に簡単に見えます: ins s@(T color ayb) = balance color (ins a) y b. 挙動は木のバランスが保たれているように見えますが、着色は少し乱れます。そして最終的にそれは将来の挿入に影響を与えます..これをどのように達成できるか考えていますか? これは、以前の質問への最初のステップになる可能性があると思います。Haskell を使い始めたばかりなので、簡単には理解できません。どうもありがとう。

insertSet x s = T B a y b
  where ins E = T R E x E
        ins s@(T color a y b) =
          if x < y then balance color (ins a) y b
          else if x > y then balance color a y (ins b)
          else s

['d','a','s','f']   s
                   /\
                  a  f
                 /
                d        (unsorted tree)
4

1 に答える 1

1

私の RBTree 実装を haskellDB で使用できます ( http://hackage.haskell.org/package/RBTree )。

関数を使用してinsert：

insert :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a

(\_ _ -> LT)関数をフィードすると、いつでも新しい要素を一番左の場所に配置できます。

于 2011-06-05T15:10:17.620 に答える