algorithm - ソートされた数値のストリームからバランスのとれた二分探索木を生成する最適な方法

Question

昇順の整数の入力ストリームがあります。私のタスクは、そのストリームからバランス二分探索木をその場で作成することです。リンク: BBST from a stream of integersを調べて、赤黒木を利用できることを理解しました。問題は、入力データから「ソートされた情報」を使用する、より最適なソリューションを探していることです。

Answer 1

赤黒木を使用しているが、常にルートではなく挿入された最後のノードから挿入を開始し、ボトムアップ挿入アルゴリズムを使用する場合、挿入は O(1) 償却されます。これは、ツリーの構築に Ω(n log n) ではなく O(n) のコストがかかることを意味します。