ランダムバイナリーツリー

任意のキーに対して${\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}$1ステップ離れた鍵には確率がある$\displaystyle {\tfrac {1}{3}}}$など。これらの確率の合計は、から離れて伸びる調和級数の2つのコピーを形成します。${\displaystyle x}$ソートされたシーケンスの両方向で、${\displaystyle 2\log n+O(1)}$上記の上限値。この上限値は、値に対する期待される検索パスの長さにも適用されます。${\displaystyle x}$それは与えられた鍵の1つです。^{[ 7 ]}

ランダム二分探索木における最長の根から葉へのパスは、期待されるパスの長さよりも長いが、定数倍だけ長い。${\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 ]}

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

任意の木における頂点のシュトララー数は、それらの頂点の下にある部分木の複雑さの尺度です。葉（外部ノード）のシュトララー数は 1 です。その他のノードについては、シュトララー数はその子のシュトララー数から再帰的に定義されます。二分木では、2 つの子のシュトララー数が異なる場合、親のシュトララー数は 2 つの子の数のうち大きい方になります。しかし、2 つの子のシュトララー数が等しい場合、親の数は 1 大きい方になります。木全体のシュトララー数は、ルートノードの数です。${\displaystyle n}$-ノードランダム二分探索木では、シミュレーションによると期待されるシュトララー数は${\displaystyle \log _{3}n+O(1)}$より弱い上限${\displaystyle \log _{3}n+o(\log n)}$証明されている。^{[ 10 ]}

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

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

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

確率${\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 ]​}

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

内部ノードの数がこのコイン投げの表の数に等しいので、与えられた数を持つすべての木は${\displaystyle n}$ノードは、同じ長さの（一意の）コイン投げシーケンスから生成され、${\displaystyle p}$つまり、${\displaystyle p}$このプロセスによって生成される木のサイズのばらつきに影響しますが、特定のサイズの場合、木は均一にランダムに生成されます。^{[ 26 ]}の値の場合${\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}}}$、

予想される木のサイズに対して、しかし${\displaystyle p={\tfrac {1}{2}}}$これにより、1 + 1 + 1 + 1 + ⋯という発散級数が得られます。^{[ 27 ]}

のために${\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回再帰的に呼び出し、各呼び出しの確率は少なくとも$\displaystyle {\tfrac {1}{2}}}$正しい解の値を保持する。ランダムツリーは、正しい再帰呼び出しのサブツリーをモデル化する。アルゴリズムは、グラフ上で成功する。${\displaystyle n}$正しい再帰呼び出しのランダムツリーに少なくとも深さの枝がある場合、頂点${\displaystyle 2\log _{2}n}$再帰の基本ケースに到達します。成功確率は${\displaystyle \Omega (1/\log n)}$アルゴリズムの対数因子の1つを生成する${\displaystyle O(n^{2}\log ^{3}n)}$実行時。^{[ 31 ]}

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