機能プログラミングで最も簡単な自己バランスの木は何ですか？

Question

Haskellで自己バランスのとれた木を設計しています。エクササイズとして、そしてあなたの後ろの手に持っているのはいいことだからです。

以前はCとPythonでは、単純なバランスルールのために、TREAPとSplayの木を好みました。彼らは価値があるよりも多くの仕事のように思えたので、私はいつもR/Bの木を嫌いました。

さて、Haskellの機能的な性質により、状況は変わったようです。 10行のコードにr/b挿入関数を書き込むことができます。一方、TREAPは乱数ジェネレーターを保存するためにラッピングを必要とし、スプレーツリーはトップダウンするのに苦痛です。

それで、私はあなたが他の種類の木の経験があるかどうか尋ねていますか？機能的言語のパターンマッチングとトップダウンの性質を利用する方が良いものはどれですか？

Answer 1

わかりました、この質問に答えるための参照や研究はあまりなかったと思います。代わりに、私はあなたのさまざまなアイデアや木を試すのに時間をかけました。 RBツリーよりもこれ以上良いものは見つかりませんでしたが、おそらくそれは単なる検索バイアスです。

RBツリーは（挿入）4つの簡単なルールとバランスをとることができます。 クリス岡崎が示す:

balance T (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 T (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 T 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 T 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 T a x b = T B a x b

AVLツリーは、同様のパターンマッチング方法でバランスをとることができます。ただし、ルールも圧縮されません。

balance T (T (T a x b   dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d  0) 0
balance T a x (T b y (T c z d   dz)   1 )   2  = T (T a x b  0) y (T c z d dz) 0
balance T (T a x (T b y c   1 )   1 ) z d (-2) = T (T a x b -1) y (T c z d  0) 0
balance T (T a x (T b y c (-1))   1 ) z d (-2) = T (T a x b  0) y (T c z d  1) 0
balance T (T a x (T b y c   _ )   1 ) z d (-2) = T (T a x b  0) y (T c z d  0) 0
balance T a x (T (T b y c   1 ) z d (-1))   2  = T (T a x b -1) y (T c z d  0) 0
balance T a x (T (T b y c (-1)) z d (-1))   2  = T (T a x b  0) y (T c z d  1) 0
balance T a x (T (T b y c   _ ) z d (-1))   2  = T (T a x b  0) y (T c z d  0) 0
balance t = t

AVLツリーは一般にRBツリーより劣ると見なされるため、おそらく余分な手間の価値がないでしょう。

AAツリーは、理論的には良好で簡単にバランスが取れている可能性があります。

balance T n (T n a x b) y c = T n a x (T n b y c) -- skew
balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split
balance T n a x b = T n a x b

しかし、残念ながら、Haskellは過負荷が好きではありません n. 。ランクを使用するのではなく、RとBに類似したものがうまく機能する可能性があります。

ツリーの静的構造ではなく、単一のノードに焦点を合わせる必要があるため、広がった木は困難です。それはによって行うことができます 挿入とスプレーのマージ.

Globalランダムジェネレーターを持っていないが、すべてのノードにインスタンスを保持する必要があるため、TREAPは機能的な環境でも不安です。これに取り組むことができます クライアントの優先順位を生成するタスクを残します, 、それでも、パターンマッチングを使用して優先比較を行うことはできません。

Answer 2

あなたが言うように、赤い黒い木はそれほど使いにくいです。あなたは与えましたか 指の木？あなたはあなたのベースデータ構造を次のようなもので増強することに興味があるかもしれません ジッパー。 あなたが面白いと思うかもしれない別の木はです AAツリー それは赤い黒の木の単純化です。

Answer 3

それはすでに実装されているものです。

data.mapやdata.setなど、バランスの取れた木のHaskellには素晴らしい実装があります。彼らはあなたのニーズを満たしていませんか？再実装、再利用しないでください。

Answer 4

OCAML標準ライブラリは、AVLツリーを使用しています map ファンクタ。あなたが含めると、RBツリーよりも実装が簡単であるように思われます remove 手術。