SetOCaml標準ライブラリには、非常に効率的な分割統治アルゴリズムを使用して2つのセットのを計算する素晴らしい実装がunionあります。あるセットからサブツリー全体（単一の要素だけでなく）を取得し、それらを別のセットに挿入して、必要に応じてバランスを取り直すと思います。
これには、OCamlが使用するAVLツリーに保持されている高さ情報が必要なのか、それとも赤黒木でも可能かどうか疑問に思っています。たとえば、最初のツリーの最後に要素を追加する2番目のツリーを単純に反復するよりも、赤黒木のペアをより効率的に連結することは可能ですか？
あなたが集合和集合または連結、あるいはその両方に興味があるのか、それともOCamlや一時的な構造で一般的な永続データ構造だけに興味があるのか、あなたの質問の言い回しからはわかりません。
指を使った赤黒木の実装は、HeatherD.Boothの論文の章で説明されています。指を使って、サイズnの赤黒木を償却O（lg（min（p、q）））時間でサイズpとqの2つの木に分割し、サイズpとqの2つの赤黒木を分割することができます。同じ境界で連結されます。さらに、要素は、償却されたO（1）時間でrbツリーのいずれかの端に追加または削除できます。これらの操作により、情報理論的に最適な、償却されたO（p lg（q / p））時間設定和集合（p <qの場合）を実現できます。おそらく、これらの境界を取得するための重要なアイデアは、左右のスパインの子ポインターを逆にすることです。
上記の範囲は、従来の意味で償却されます。OCamlのような関数型言語の場合、データ構造が永続的に使用されるときに適用される境界が必要になる場合があります。木が永続的に使用されている場合、ブースの説明がこれらの境界のすべてを達成するとは思いません。たとえば、指で挿入すると、ω（1）の色が変更されます。これは、Driscolletal。の「MakingDataStructuresPersistent」で説明されている怠惰な色の変更によって解決される可能性があります。
一方、ブースの分析では、永続的に使用した場合でも、連結がO（lg（max（p、q）））であることが示される可能性があると思います。和集合の限界については楽観的ではありません。
機能的な設定では、漸近的に最適な時間範囲でのセット操作が可能です。Hinze＆Patersonによって記述されたものは、償却された（しかし永続的な）意味で境界を達成し、Blandford＆Blellochによって記述されたtreapは、ランダム化された意味で境界を達成し、Kaplan＆Tarjanによって記述されたものは最悪の場合にそれらを達成します。後者はO（lg lg（min（p、q）））連結も提供しますが、Hinze＆Patersonはその主張に疑問を持っています。これらの木は、赤黒木に固有の質問に対する直接の答えではありませんが、可能性のあるフレーバーを提供することを願っています。H＆Pペーパーにはコードが含まれており、Coqを使用して正しいことが確認されています。 OCamlコード。
あなたが興味を持っているかもしれないもう2つのポインタ：Brodaletal。機能的な設定でも、O（lg n）の検索、挿入、削除、およびO（1）の連結を使用して検索ツリーを表示しました。さらに、Atallahetal。O（1）コンキャットを償却した赤黒木（おそらく一時的にのみ）を説明すると主張しますが、BuchsbaumとGoodrichはその構造にいくつかの欠陥があると主張しています。
赤黒木の有用性についての最後の注意：この質問に対する回答の1つに対するコメントの1つで、次のように述べています。
赤黒木の唯一の利点は、補助情報（赤または黒）がブランチごとに1ビットしかないことです。高さを追加すると、その利点が失われ、代わりに高さのバランスの取れたツリーを使用することもできます。
他にも利点があります。たとえば、計算幾何学で使用される一部のデータ構造は、二分探索木に基づいていますが、木の回転のコストが高くなります。赤黒木は、挿入と削除ごとに最大3回転でリバランスできますが、AVL木は、これらの操作でΩ（lg n）回転することができます。Ralf Hinzeが気付いたように、赤黒木に対するOkasakiのリバランススキーム（ ML、Haskell、Java、およびAdaで利用可能なコード）は同じ境界を提供せず、挿入時にΩ（lg n）回転を実行することになります。（岡崎は削除を提示しません。）
さらに、ノードごとに1ビットのバランス情報のみを使用するように、高さバランスのとれた検索ツリー（およびAVLツリー）を格納できます。片側の高さバランスの取れたツリーのように、各ノードで可能なバランス位置が2つしかないツリーもありますが、ブラウン以降で最初に説明されたように、ノードごとに最大4つの可能なバランス位置を持つツリーは、各子に1ビットのバランス情報を格納できます。Haeuplerらによって拡張されました。
編集：
質問の最後にある特定の質問に答えるために、2つの赤黒木を連結するためのアルゴリズムの説明を次に示します。O（lg（max（| L |、| R |）））時間がかかりますが、これは、上記で説明した漸近的に最適な結合時間を取得するには長すぎます。比較のために、OCamlのstdlibにあるAVLセットの「結合」実装を期待していますO（h1-h2）パフォーマンスを取得します。ここで、h1は背の高いツリーの高さですが、実際には2つのAVLツリーに結合し、それらの間に適合する要素が与えられます。以下のアルゴリズムでは、そのモルタル要素を見つけて、その1つから削除する必要があります。引数。B +ツリーのように、要素をリーフに格納するだけでそれを回避できますが、検索をガイドするために非リーフノードの要素へのポインタの束を保持する必要があるというスペースペナルティがあります。いずれにせよ、以下で説明するように、各ツリーの黒の高さを計算する必要があるため、OCaml stdlibのAVL結合コードのように、同じ高さのツリーの結合時間が一定になることはありません。
空でない赤黒木LとRが2つあるとすると、LとRを連結した新しい赤黒木が生成されます。これにはO（lg（max（| L |、| R |）に比例する時間がかかります。 ）））、ここで| L | Lのノード数を示します。
まず、Lから最大の要素を削除します。c。次に、LとRの黒の高さを見つけます。「黒の高さ」とは、ルートからリーフまでの任意のパス上の黒のノードの数を意味します。赤黒木の不変量により、これは任意のツリーのすべてのパスで一定です。Lの黒の高さpとRの黒の高さqを呼び出し、wlogp≤qと仮定します。
Rのルートから、高さpの黒いノードR'に到達するまで、左の子をたどります。ルート要素c、左の子L、右の子R'を使用して新しい赤いツリーCを作成します。Lはそれ自体が赤黒木であるため、その根は黒であり、C以下で色不変量に違反することはありません。さらに、Cの黒の高さはpです。
ただし、R'の代わりにCをRに単純に接続して戻すことはできません。まず、p = qの場合、R'はRですが、Cには赤いルートがあります。この場合、Cのルートを黒に変更するだけです。これは、新しい連結ツリーです。
次に、R'がルートでない場合は、親が赤である可能性があります。赤い親は赤い子供を持つことを許可されていないので、バランスを取り直す必要があります。ここでは、R'（現在はCに置き換えられています）とRのルートの間の背骨全体に岡崎のリバランススキームを適用します。
考えられるケースは2つあります。Cに祖父母がいない場合は、Cの親を黒に着色します。これでツリーが有効になります。
Cに祖父母がいる場合、Cの親は赤であるため、黒で高さp+1である必要があります。Cの祖父母を新しい赤い木に置き換えます。その根はCの親の根であり、左の子はCで、色が黒になり、右の子はCの兄弟であるCの祖父母の根で構成される黒い木です。 、Cの叔父、この順序で。これはCの祖父母の黒の高さを上げることはありませんが、色が赤に変わり、赤い親のルートまたは赤い子になる可能性があるため、再度バランスを取り直す必要があります。木
これらはいずれもO（lg | R | + lg | L |）= O（lg（max（| L |、| R |）））より大きくありません
これをO（lg（min（| L |、| R |）））にするには、最初にスパインポインタを逆にします。次に、大きな木の黒い高さは必要ありません。1本の木が背骨を使い果たすまで、黒い背骨ノードを数えるだけで済みます。次に、元の（岡崎のものではない）リバランススキームを使用して、O（1）ノードのみをリバランスするようにします。最後に、後で必要に応じて、怠惰な色の変更のためにリバランスする必要のない背骨の残りの部分にマークを付けます。
Concatenate +を最後に追加することについて話しているように見えるので、次の問題があるようです。
Given two red-black trees T1 and T2, such that keys of T1 <= keys of T2,
find union of the two.
これはツリーの結合操作と呼ばれ、この場合、O（log n）時間でツリーの結合を行うことができます。チェックアウト：http ：//www.cs.tau.ac.il/~ wein / publications / pdfs / rb_tree.pdf
http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm、問題14.2もチェックしてください。
各ノードの高さ情報でツリーを連結し、拡張しない場合は、O（log ^ 2（n））よりも優れています。2 * [log（n1）+ log（n2）]で連結できます。ここで、n1とn2は、連結するツリー内のノードの数を表します。O（log（n））で高さを計算した後、ツリーを下るときに各ノードのバランス情報を使用して、適切な連結ポイントを見つけてください。
オーバーラップの少ないツリーを組み合わせると何かを獲得できる可能性がありますが、通常はノードを再編成する必要があります。バランスをとると、1つのノードだけに触れた後に回転するルールがあるため、状況はさらに悪化します。