ランダムバイナリツリー

コンピュータサイエンスと確率論において、ランダム バイナリ ツリーは、バイナリ ツリー上の何らかの確率分布からランダムに選択されたバイナリ ツリーです。さまざまな分布が使用されており、これによりこれらのツリーのプロパティが異なります。

ランダム二分木は、二分探索木に基づくデータ構造の平均的な複雑さを分析するために使用されてきました。このアプリケーションでは、ランダムな順列に従ってノードを1つずつ挿入することによって形成されたランダム木を使用するのが一般的です。^{[1]結果として得られる木は、対数的な深さと対数的な}シュトレーラ数を持つ可能性が非常に高くなります。treapおよび関連するバランス型二分探索木は、更新シーケンスがランダムでない場合でもこのランダムな構造を維持する更新操作を使用します。

ランダム二分木上のその他の分布には、すべての異なる木が等しく存在する可能性がある均一離散分布、繰り返し分割によって取得される特定の数のノード上の分布、ランダムデータの二分試行と基数木、分岐プロセスによって生成される可変サイズの木などがあります。

必ずしもバイナリではないランダム ツリーについては、「ランダム ツリー」を参照してください。

二分木は、各ノードが最大 2 つの子 (ツリー内でそのノードのすぐ下にあるノード) を持つことができるルート付きツリーであり、それらの子は左または右として指定されます。代わりに、各ノードが子を持たない外部ノード、または子が 2 つだけある内部ノードのいずれかである拡張二分木を検討すると便利な場合があります。拡張形式ではない二分木は、すべてのノードを内部として扱い、内部ノードの欠落した子ごとに外部ノードを追加することで、拡張二分木に変換できます。逆に、少なくとも 1 つの内部ノードを持つ拡張二分木は、すべての外部ノードを削除することで、非拡張二分木に戻すことができます。このように、数学的分析の目的では、これら 2 つの形式はほぼ完全に同等ですが、拡張形式では、非拡張形式のどの形式にも対応しない単一の外部ノードで構成されるツリーが許可されます。コンピューター データ構造の目的では、最初の形式の外部ノードはデータ構造内のオブジェクトとして明示的に表現できるため、2 つの形式は異なります。^[2]

二分探索木では、内部ノードはキーと呼ばれる数字やその他の順序付けられた値でラベル付けされ、木を順番に走査するとキーがソートされた順序でリストされるように配置されます。外部ノードはラベル付けされません。 ^[3]二分木は、すべてのノードにラベルが付いていない状態で、またはラベルがソートされた順序で与えられていない状態で研究されることもあります。たとえば、カルテシアン木データ構造は、必ずしも二分探索木ではないラベル付き二分木を使用します。^[4]

ランダム二分木は、二分木上の特定の確率分布から抽出されたランダムな木です。多くの場合、これらの確率分布は、与えられたキーのセットを使用して定義され、それらのキーを持つ二分探索木の確率を記述します。ただし、必ずしも二分探索木を生成せず、必ずしも固定数のノードを与えるわけではない他の分布も可能です。^[5]

異なる順序のキーのシーケンスについては、以前に挿入されたキーの構造を変更せずに、各キーをツリーの葉として順番に挿入するバイナリ検索ツリーを形成できます。各挿入の位置は、前のツリーでバイナリ検索を行うことで見つけることができます。ランダム順列モデルは、特定のキーセットに対して、セットの順列からシーケンスをランダムに選択することによって定義され、各順列は等しい確率を持ちます。^[6]

例えば、3つのキー1、3、2をその順序で二分探索木に挿入すると、数字1は木の根に位置し、数字3はその右の子として、数字2は数字3の左の子として配置されます。キー1、2、3には6つの異なる順列がありますが、それらから構築できる木は5つだけです。これは、順列2、1、3と2、3、1が同じ木を形成するためです。したがって、この木には生成される確率がありますが、他の4つの木にはそれぞれ生成される確率があります。^[5]${\displaystyle {\tfrac {2}{6}}={\tfrac {1}{3}}}$${\displaystyle {\tfrac {1}{6}}}$

与えられたキー セット内の任意のキーについて、ランダム バイナリ検索ツリーのルートから までのパスの長さの期待値は最大で です。ここで、「 」は自然対数関数を表し、 はビッグ O 表記を導入します。期待値の線形性により、 の祖先の期待数は、他のキー について、 がの祖先である確率の合計に等しくなります。が区間 から最初に挿入されるキーであるとき、キーはの祖先になります。 区間内の各キーが最初である可能性は等しいため、これは区間の長さに反比例する確率で発生します。したがって、ソートされたキーのシーケンスで に隣接するキーはの祖先である確率を持ち、1 ステップ離れたキーは の祖先である確率を持ちます。これらの確率の合計は、ソートされたシーケンスの両方の方向に から広がる調和級数の 2 つのコピーを形成し、上記の境界を与えます。この境界は、与えられたキーの 1 つである値に対する期待検索パスの長さにも当てはまります。^[7]${\displaystyle x}$${\displaystyle n}$${\displaystyle x}$${\displaystyle 2\log n+O(1)}$${\displaystyle \log}$${\displaystyle O}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle [x,y]}$${\displaystyle x}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle x}$${\displaystyle {\tfrac {1}{3}}}$${\displaystyle x}$${\displaystyle 2\log n+O(1)}$${\displaystyle x}$

ランダム二分探索木における最長のルートからリーフへの経路は、期待される経路長よりも長くなりますが、その長さは定数倍です。ノードを持つ木の場合、その長さは高い確率でおよそ ${\displaystyle n}$

${\displaystyle \displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,}$

は方程式を満たす 範囲内の唯一の数である${\displaystyle \beta }$${\displaystyle 0<\beta <1}$

${\displaystyle \displaystyle 2\beta e^{1-\beta }=1.}$^[8]

ランダム順列モデルでは、最小と最大のキーを除く各キーは、ツリーの葉になる確率を持っています。これは、2 つの隣接キーの後に挿入されたときに葉になるためです。これは、そのキーとその 2 つの隣接キーの 6 つの順列のうち 2 つで発生し、すべて同じ確率です。同様の理由により、最小と最大のキーは葉になる確率を持っています。したがって、期待される葉の数はこれらの確率の合計であり、 の場合はちょうど です。^[9]${\displaystyle {\tfrac {1}{3}}}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle n\geq 2}$${\displaystyle (n+1)/3}$

任意のツリーの頂点のストララー数は、それらの頂点の下にあるサブツリーの複雑さの尺度です。葉 (外部ノード) のストララー数は 1 です。その他のノードの場合、ストララー数はその子のストララー数から再帰的に定義されます。バイナリ ツリーでは、2 つの子が異なるストララー数を持つ場合、親のストララー数は 2 つの子の数のうち大きい方になります。ただし、2 つの子が同じストララー数を持つ場合、親の数は 1 だけ大きくなります。ツリー全体のストララー数は、ルート ノードの数です。ノードのランダム バイナリ サーチ ツリーの場合、シミュレーションでは期待されるストララー数は であることが示されています。より弱い上限が証明されています。^[10]${\displaystyle n}$${\displaystyle \log _{3}n+O(1)}$${\displaystyle \log _{3}n+o(\log n)}$

二分探索木データ構造の応用では、キーが削除されることなくランダムな順序で挿入されることはまれであり、ランダム二分木の直接的な応用は制限される。しかし、アルゴリズム設計者は、キーがランダムに挿入されたかのように、木の形状がランダムであるという特性を保持するために、任意の挿入と削除を可能にするデータ構造を考案した。^[11]

与えられたキーのセットに数値の優先順位（値とは無関係）が割り当てられている場合、これらの優先順位を使用して、キーを優先順位順に挿入することで得られる二分探索木である数値の直交木を構築できます。優先順位を単位間隔内の独立したランダムな実数に選択し、ノードの挿入または削除後にツリーの回転を使用して直交木構造を維持することにより、ランダム二分探索木のように動作するデータ構造を維持できます。このようなデータ構造は、トレップまたはランダム二分探索木として知られています。^[11]

zip ツリーや zip-zip ツリーなどの treap の変種では、ツリーの回転を、ツリーを分割および結合する「zip 化」操作に置き換え、キーと一緒に生成して保存する必要があるランダム ビットの数を制限します。これらの最適化の結果は、依然としてランダム構造を持つツリーですが、ランダム順列モデルと完全に一致するものではありません。^[12]

ノードを持つ二分木の数はカタラン数である。^[13]これらの木の数 は${\displaystyle n}$${\displaystyle n=1,2,3,\dots }$

したがって、これらのツリーの1つが一様にランダムに選択される場合、その確率はカタラン数の逆数になります。この分布のモデルから生成されたツリーは、ランダムバイナリカタランツリーと呼ばれることがあります。^[14]これらのツリーの期待される深さは、対数ではなく、の平方根に比例します。 ^[15]より正確には、このタイプのノードツリー でランダムに選択されたノードの期待される深さは、${\displaystyle n}$${\displaystyle n}$

${\displaystyle {\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)}$^[16 ]

一様ランダムなノード二分木の期待ストララー数は であり、ランダム二分探索木の期待ストララー数よりも低い。^[17]${\displaystyle n}$${\displaystyle \log _{4}n+O(1)}$

この等確率ランダムツリーのモデルは高さが大きいため、二分探索木にはあまり使用されません。ただし、次のような用途があります。

• コンパイラ設計における代数式の構文解析木のモデル化。^[18]ここで、木の内部ノードは式内の二項演算を表し、外部ノードは式が演算する変数または定数を表します。ストララー数の上限は、式を評価するために必要なレジスタの数に変換されます。 ^[19]
• 河川ネットワークのモデリング。これは、シュトララー数が開発された元々の用途である。^[20]
• 一定数の種に対する可能な進化樹のモデル化。このアプリケーションでは、種を外部ノードとする拡張バイナリツリーが使用されます。^[21]

Jean-Luc Rémy のアルゴリズムは、次のプロセスによって、指定されたサイズの一様ランダムな二分木を、サイズに比例した時間で生成します。1 つの外部ノードからなる木から開始します。次に、現在の木が目標サイズに達していない間に、そのノード (内部または外部) の 1 つを一様ランダムに繰り返し選択します。選択したノードを新しい内部ノードに置き換え、選択したノードを子ノードの 1 つ (左または右のどちらにするかは均等に) とし、新しい外部ノードをもう 1 つの子ノードとします。目標サイズに達したら停止します。^[22]

ゴルトン・ワトソン過程は、各ノードの子の数が他のノードとは無関係にランダムに選択されるツリー上の分布のファミリーを表します。二分木の場合、ゴルトン・ワトソン過程の 2 つのバージョンが使用されています。違いは、外部ルート ノードである 1 つのノードのみを持つ拡張二分木が許可されるかどうかだけです。

• ルート ノードが外部になる可能性があるバージョンでは、指定された確率で内部になるか、確率で外部になるように選択されます。ルート ノードが内部の場合、その 2 つの子は同じプロセスによって再帰的に生成されたツリーです。${\displaystyle p}$${\displaystyle 1-p}$
• ルート ノードが内部でなければならないバージョンでは、その左と右の子ノードは、互いに独立して、確率 で内部であるか、確率 で外部であるかが決定されます。内部である場合、それらは同じプロセスによって再帰的に生成されるツリーのルートです。${\displaystyle p}$${\displaystyle 1-p}$

このようにして生成された木はバイナリ・ゴルトン・ワトソン木と呼ばれている。特別な場合には臨界バイナリ・ゴルトン・ワトソン木と呼ばれる。^[23]${\displaystyle p={\tfrac {1}{2}}}$

確率は、2元ゴルトン・ワトソン過程の相転移を示す。 の場合、結果として得られる木はほぼ確実に有限であるが、 の場合、正の確率で無限となる。より正確には、任意のの場合、木が有限のままである確率は ${\displaystyle p={\tfrac {1}{2}}}$${\displaystyle p\leq {\tfrac {1}{2}}}$${\displaystyle p>{\tfrac {1}{2}}}$${\displaystyle p}$

${\displaystyle \displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}}$^[24 ]

同じ木を生成する別の方法は、表の確率と裏の確率でコインを投げるシーケンスを作成し、裏の数が表の数を超える（外部ルートが許可されているモデルの場合）か、表の数に1を加えた数を超える（ルートが内部でなければならない場合）最初のコイン投げを実行し、次にこのコイン投げのシーケンスを使用して、再帰的生成プロセスによって行われた選択を深さ優先順に決定することです。^[25]${\displaystyle p}$${\displaystyle 1-p}$

内部ノードの数は、このコイン投げシーケンスの表の数に等しいため、指定された数のノードを持つすべてのツリーは、同じ長さの（一意の）コイン投げシーケンスから生成され、 に関係なく、同じ確率で生成されます。つまり、 の選択は、このプロセスによって生成されるツリーのサイズの変動に影響しますが、指定されたサイズでは、ツリーは一様にランダムに生成されます。^[26]の値が臨界確率より小さい場合、の値が小さいほど、期待されるサイズが小さいツリーが生成され、 の値が大きいほど、期待されるサイズが大きいツリーが生成されます。臨界確率 では、このプロセスによって生成されるツリーの期待されるサイズに有限の境界はありません。より正確には、任意のに対して、ツリーの深さ でのノードの期待数は であり、ツリーの期待されるサイズは、各深さでのノードの期待数を合計することで得られます。 に対して、これは等比級数を与えます。${\displaystyle n}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p={\tfrac {1}{2}}}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p={\tfrac {1}{2}}}$${\displaystyle p}$${\displaystyle i}$${\displaystyle (2p)^{i}}$${\displaystyle p<{\tfrac {1}{2}}}$

${\displaystyle \displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}}$、

期待される木のサイズに対しては1 + 1 + 1 + 1 + ⋯となり、発散する級数となる。^[27]${\displaystyle p={\tfrac {1}{2}}}$

の場合、${\displaystyle p={\tfrac {1}{2}}}$内部ノードを持つ特定の木は確率で生成され、ランダムな木がこのサイズになる確率は、この確率にカタラン数を掛けた値になります。 ${\displaystyle n}$${\displaystyle 1/2^{2n+1}}$

${\displaystyle {\frac {C_{n}}{2^{2n+1}}}={\frac {1}{2n+1}}{\binom {2n+1}{n}}{\frac {1}{2^{2n+1}}}\approx {\frac {1}{{\sqrt {4\pi }}\,n^{3/2}}}\displaystyle }$^[28 ]

ゴルトン・ワトソン過程は、もともと人間の姓の広がりと消滅を研究するために開発されたもので、より一般的には人間や動物の個体群のダイナミクスに広く適用されてきた。これらの過程は、ツリーの特定のレベル（個体群ダイナミクスの応用では世代）で内部ノードまたは外部ノードになる確率が固定ではなく、前のレベルのノードの数に依存するモデルに一般化されている。^[29]臨界確率${\displaystyle {\tfrac {1}{2}}}$を伴うこの過程のバージョンは、種分化のモデルとして研究されており、臨界分岐過程として知られている。この過程では、それぞれの種は指数分布の寿命を持ち、その生涯を通じて、寿命に等しい割合で子種を生み出す。子が生まれると、親は進化ツリーの左の枝として存続し、子は右の枝になる。^[30]

臨界ゴルトン・ワトソン木（ルートが内部にある必要があるバージョン）の別の応用は、再帰的な辺の縮小プロセスを使用してグラフの最小カットを見つけるためのカーガー・スタインアルゴリズムで発生します。このアルゴリズムは自分自身を2回再帰的に呼び出し、各呼び出しで正しい解の値を保持する確率が少なくともあります。ランダムツリーは、正しい再帰呼び出しのサブツリーをモデル化します。アルゴリズムは、正しい再帰呼び出しのこのランダムツリーに少なくとも深さの枝がある場合に、頂点のグラフで成功し、再帰の基本ケースに到達します。成功確率はであり、アルゴリズムの実行時に対数係数の1つを生成します。^[31]${\displaystyle {\tfrac {1}{2}}}$${\displaystyle n}$${\displaystyle 2\log _{2}n}$${\displaystyle \Omega (1/\log n)}$${\displaystyle O(n^{2}\log ^{3}n)}$

Devroye と Robson は、関連する連続時間ランダム プロセスを検討します。このプロセスでは、各外部ノードは、外部ノードとして最初に出現してから指数分布の時間に、最終的に 2 つの外部子を持つ内部ノードに置き換えられます。任意の時点でのツリー内の外部ノードの数は、集団のメンバーが一定の割合で出産する単純な出産プロセスまたはユール プロセスによってモデル化されます。ユール プロセスで 1 人の子供を出産することは、Devroye と Robson のモデルで 2 人の子供に置き換えられることに対応します。このプロセスが任意の固定時間に停止されると、結果はランダム サイズ (停止時間によって異なります) のバイナリ ツリーになり、そのサイズのランダム順列モデルに従って分散されます。Devroye と Robson は、このモデルをアルゴリズムの一部として使用して、正確な構造ではなく各深さのノードの数で記述される、ランダム順列モデルのツリーをすばやく生成します。^[32]このプロセスの離散的な変形は、単一の外部ノードからなるツリーから始まり、ランダムに選択された外部ノードを2つの外部子を持つ内部ノードに繰り返し置き換えます。これも、固定時間（固定サイズ）で停止すると、結果のツリーはそのサイズのランダム順列モデルに従って分散されます。^[1]

バイナリ ツリーの別の形式であるバイナリトライまたはデジタル検索ツリーには、外部ノードの一部にラベルを付けるバイナリ数値のコレクションがあります。ツリーの内部ノードは、 2 つ以上の数値で共有されるバイナリ表現のプレフィックスを表します。内部ノードの左側と右側の子は、対応するプレフィックスをそれぞれ 1 ビット、つまり 0 または 1 ビット拡張することによって取得されます。この拡張が指定された数値のいずれにも一致しないか、そのうちの 1 つにのみ一致する場合、結果は外部ノードになります。それ以外の場合は、別の内部ノードになります。ランダム バイナリ トライは、たとえば単位区間で独立して生成されたランダムな実数のセットについて研究されています。これらのツリーには空の外部ノードがいくつかある可能性がありますが、ランダム バイナリ検索ツリーよりもバランスが取れている傾向があります。単位区間内の一様ランダムな実数の場合、またはより一般的には単位区間上の任意の二乗積分可能な確率分布の場合、ノードの平均深さは漸近的に になり、ツリー全体の平均高さは漸近的に になります。これらの木の解析は、トライベースのソートアルゴリズムの計算複雑性に適用できる。^[33]${\displaystyle n}$${\displaystyle \log _{2}n}$${\displaystyle 2\log _{2}n}$

トライの変形である基数木または圧縮トライは、空の外部ノードとその親の内部ノードを削除します。残りの内部ノードは、0または1ビットによる両方の可能な拡張が、ランダムに選択された数の少なくとも1つによって使用されるプレフィックスに対応します。均一に分布した2進数の基数木の場合、最短のリーフルートパスの長さは で 、最長のリーフルートパスの長さは の 両方が である確率が高くなります。^[34]${\displaystyle n}$$${\displaystyle \log _{2}n-\log _{2}\log n+o(\log \log n)}$$$${\displaystyle \log _{2}n+{\sqrt {2\log _{2}n}}+o({\sqrt {\log n}}),}$$

Luc DevroyeとPaul Kruszewski は、ノードを持つランダムな二分木を構築するための再帰的プロセスについて説明しています。このプロセスでは、単位区間 で実数値のランダム変数を生成し、最初のノード (ノードの整数値に切り捨て) を左のサブツリーに、次のノードをルートに、残りのノードを右のサブツリーに割り当てます。次に、同じプロセスを左と右のサブツリーで再帰的に使用します。 が区間 で一様ランダムに選択される場合、結果はノードのランダムな順列によって生成されるランダム二分探索木と同じになります。これは、どのノードもルートとして選択される可能性が等しいためです。ただし、この定式化により、代わりに他の分布を使用することもできます。たとえば、一様ランダム二分木モデルでは、ルートが固定されると、その 2 つのサブツリーもそれぞれ一様ランダムになる必要があるため、一様ランダム モデルは、 に対して ( に応じて)異なる分布を選択して生成することもできます。彼らが示すように、ベータ分布を選択し、適切な形状を選択して各枝を描くことで、このプロセスによって生成された数学的な木を使用して、現実的な植物の樹木を作成できます。^[35]${\displaystyle n}$${\displaystyle x}$${\displaystyle (0,1)}$${\displaystyle xn}$${\displaystyle x}$${\displaystyle n}$${\displaystyle x}$${\displaystyle x}$