n 個の任意の挿入を実行する最初は空の BST があるとします。この BST の平均の高さをどのように見つけますか? これの式/疑似コードは次のようになります (私が間違っていなければ):
H(T) = 1 + max(H(T.left), H(T.right))
これに対する再帰関係についての私の推測では ですがT(n) = 1 + 2*T(n/2)
、これが正しいかどうかはわかりません。
ここに私のジレンマがあります。再帰関係が正しい場合、平均身長アルゴリズムの平均複雑さをどのように計算すればよいでしょうか?