6

Haskellでさまざまな種類のツリーを使用することがありますが、それらが何と呼ばれているのか、それらを使用するアルゴリズムやそれらのクラスインスタンス、またはハッキングに関する既存のコードやライブラリについての詳細情報をどこで入手できるのかわかりません。

例：

ラベルが葉または枝にある二分木：

data BinTree1 a = Leaf | 
                  Branch {label :: a, leftChild :: BinTree1 a, rightChild :: BinTree1 a}

data BinTree2 a = Leaf {label :: a} | 
                  Branch {leftChild :: BinTree2 a, rightChild :: BinTree2 a}

同様に、各子ノードのラベルまたはすべての子の一般的なラベルが付いたツリー：

data Tree1 a = Branch {label :: a, children :: [Tree1 a]}

data Tree2 a = Branch {labelledChildren :: [(a, Tree2 a)]}

時々私は使い始めTree2、どういうわけかそれを開発する過程でリファクタリングされますTree1。これは扱いが簡単に思えますが、私はそれについてあまり考えたことはありませんでした。ここにある種の二重性はありますか？

また、他にも役立つと思われる種類の木を投稿できる場合は、投稿してください。

要約すると、それらの木について私に話すことができるすべてが役に立ちます！:)

ありがとう。

編集：

明確化：これは宿題ではありません。通常、これらのデータ型を使用してインスタンス（Functor、Monadなど）を作成することになります。名前を新しくすると、実装されたものとより理論的な情報が含まれるライブラリが見つかるかもしれません。

通常、Hackageのライブラリの名前にTreeが含まれている場合、BinTree2または葉のみにラベルが付いた非バイナリツリーのバージョンが実装されているため、Tree2とBinTree2には他の名前または識別子があるようです。

また、ある種の二重性や同型性、またはTree1を使用するコードをTree2を使用するコードに変換する方法があるかもしれないと感じています。ある？ただの印象かもしれません。

4

2 に答える 2

6

私が聞いた名前：

  • BinTree1二分木です
  • BinTree2名前はわかりませんが、このようなツリーを使用して、たとえばハフマンコーディングのようなプレフィックスのないコードを表すことができます。
  • Tree1バラの木です
  • Tree2[Tree1]（の森）と同形であるTree1か、それを表示する別の方法はTree1、ルートのラベルがないことです。
于 2012-08-19T23:08:25.467 に答える
5

BinTree2ツリー構造自体は葉のバイナリ位置以外の情報を提供しないため、通常、葉にラベル（）のみを持つ二分木がハッシュマップに使用されます。

したがって、次のハッシュコードを持つ4つの値がある場合：

...000001 A
...000010 B
...000011 C
...000010 D

...次のように、それらをバイナリツリー（暗黙のパトリシアトライ）に格納できます。

     +          <- Bit #1 (least significant bit) of hash code
    / \            0 = left, 1 = right
   /   \
[B, D]  +       <- Bit #2
       / \
      /   \
     [A]  [C]

とのハッシュコードは。BでD始まる0ため、左のルートの子に格納されていることがわかります。それらはまったく同じハッシュコードを持っているので、これ以上のフォークは必要ありません。AとのハッシュコードはC両方とも1で「開始」するため、別のフォークが必要です。Aはビット20なので、左に移動し、C1は右に移動します。

特定の要素が挿入されたときにハッシュを再計算する必要があるかもしれないので、このハッシュテーブルの実装はちょっと悪いですが、関係ありません。

BinTree1は単なる通常の二分木であり、高速順序ベースのセットに使用されます。本当に、それについてこれ以上言うことは何もありません。

との唯一の違いは、Tree1ルートノードラベルを設定できないことです。これは、プレフィックスツリーとして使用する場合、空の文字列を含めることができないことを意味します。使用は非常に限られており、実際にそのようなものを見たことがありません。ただし、私が言ったように、明らかに非バイナリプレフィックスツリーとしての用途があります。Tree2Tree2Tree1

于 2012-08-19T22:20:20.687 に答える