algorithm - 二分探索木への一連の n 個の挿入の償却コストはいくらですか?

Question

二分探索木でn 個の挿入のシーケンスの償却コストを計算するにはどうすればよいですか? 入力シーケンスはランダムで、挿入ごとに 1 つのノードが追加されます。

Answer 1

単一の操作の時間を分析し、一連の操作で平均化できるようにしたいと考えています。償却分析の手法に従うことができます。

定義 1

特定の操作をサポートするデータ構造があるとします。このデータ構造に対してこのようなT (n)一連の操作を実行する最悪のケースの時間を とします。n次に、操作ごとの償却時間は次のように定義されますT(n)/n.( source )

二分探索木があるため、これは最悪の場合、連結リスト (左側のすべての要素または右側のすべての要素) を持つことを意味します。

n挿入手術をした場合T(n) = 1+2+...n = (n * (n-1)) / 2 = (n^2 - n) / 2.

定義 1 操作あたりの償却時間 = (n - 1) / 2.O(n)

私の解釈が間違っているかもしれませんので、そう思われる方はコメントをお願いします。

Answer 2

一般に、挿入のランダムなシーケンスに対して大まかにバランスの取れたバイナリ ツリーを生成することが期待できます。これは、ノードの平均高さが log(n) に比例することを意味します (説明については、ウィキペディアを参照してください)。償却時間 = 合計時間 / 操作数。合計時間は、平均高さ * 要素数、または O(n * log(n)) に等しくなります。合計時間は O(n * log(n)) なので、償却時間は O(log(n)) です。