n 個の任意の挿入を実行する最初は空の BST があるとします。この BST の平均の高さをどのように見つけますか? これの式/疑似コードは次のようになります (私が間違っていなければ):
H(T) = 1 + max(H(T.left), H(T.right))
これに対する再帰関係についての私の推測では ですがT(n) = 1 + 2*T(n/2)、これが正しいかどうかはわかりません。
ここに私のジレンマがあります。再帰関係が正しい場合、平均身長アルゴリズムの平均複雑さをどのように計算すればよいでしょうか?
一般に、平均的なケース分析はより複雑であり、通常のワーストケースの証明で使用するのと同じbig-O手法を実際に使用することはできません。高さの定義は正しいですが、それを再発に変換することは、おそらくそれよりも複雑になります。最初に、あなたはおそらくT(n) = 1 + T(n/2)（あなたのバージョンがO（n）を与える間、これはO（log n）の高さを与えるでしょう）、そして次に、値が右と左の間で50-50に均等に分割されることを保証するものは何もありません。
少し検索すると、BSTの平均の高さにたくさんの素材があることがわかります。たとえば、私が得た結果の1つは、BSTの予想される高さはnが大きくなるにつれて4.3 *（log n）になる傾向があるが、そこに到達するために多くの複雑な計算を行うと述べました。
T(n/2)+c ここで、c は定数で、配列を 2 つの部分に分割しますが、検索には 1 つの部分のみを使用します。out ans が の中間値よりも大きい場合は、(mid+1 .....j) であり、中間値よりも小さい場合は (i.....mid) のみを検索するため、一度に単一のサブ配列のみを操作します。