Haskell で自己均衡ツリーを設計しています。練習として、そして後ろ手に持っているといいからです。
以前は C と Python で、単純なバランス ルールのため、Treaps と Splay Trees を好みました。R/B ツリーは、価値がある以上に手間がかかるように思えたので、私はいつも嫌いでした。
現在、Haskell の機能的な性質により、状況が変わったように見えます。R/B 挿入関数を 10 行のコードで記述できます。一方、Treaps は乱数ジェネレーターを格納するためにラップする必要があり、Splay Trees はトップダウンで実行するのが面倒です。
他の種類の木の経験はありますか？関数型言語のパターン マッチングとトップダウンの性質を利用するのに優れているのはどれですか?
わかりました、この質問に答えるための参照や研究はあまりなかったと思います. 代わりに、時間をかけてあなたのさまざまなアイデアやツリーを試してみました. RB ツリーよりもはるかに優れたものは見つかりませんでしたが、おそらくそれは単なる検索バイアスです。
RB ツリーは、Chris Okasaki が示すように、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 に類似した AA ツリーの標準的ではない実装がうまく機能する可能性があります。
ツリーの静的構造ではなく、単一のノードに集中する必要があるため、スプレー ツリーは困難です。insert と splayをマージすることで実行できます。
また、グローバル ランダム ジェネレーターがなく、すべてのノードにインスタンスを保持する必要があるため、機能的な環境で Treap を実行するのは簡単ではありません。これは、優先順位の生成をクライアントに任せることで解決できますが、それでもパターン マッチングを使用した優先順位の比較はできません。
おっしゃる通り、赤黒木はさほど使いづらいものではありません。フィンガーツリーを見てもらいましたか？ジッパーのようなもので基本データ構造を拡張することに興味があるかもしれません。 もう 1 つの興味深いツリーは、Red Black Trees を単純化したAA ツリーです。
すでに実装されているものです。
Haskell には、Data.Map や Data.Set などのバランス ツリーの優れた実装があります。彼らはあなたのニーズを満たしていませんか？再実装せず、再利用してください。
mapOCaml 標準ライブラリは、ファンクターに AVL ツリーを使用します。操作を含めると、RBツリーよりも実装が簡単に思えますremove。