algorithm - 二分探索木の更新

Question

二分探索木に値を格納する必要があるアプリケーションを開発しています。これは、各行を何らかのキーを持つ値として保存することによってテキストパッドを実装するアプリケーションに似ています。行が削除されると、それ以降の行のキーは O(n) で更新されます。行番号 (例) に似たパラメーターをキーと見なすことで、アプリケーションで O(n) 時間を達成できます。

他のキーを選択して O(log n) 時間を達成する方法はありますか?

Answer 1

バイナリ ツリーから保証されたパフォーマンスが必要な場合は、 Splay TreeやRed black treeO(logN)などのセルフバランス バージョンを使用する必要があります。

Answer 2

要件が挿入/更新、削除、および検索である場合はHash Table、適切なハッシュ関数を試してください。unordered_map多くの言語では、C++、dictpython、 javascript でハッシュ テーブルの実装が提供され{}ています。ところで、自分で作成できます。

O(log(n))また、赤黒木、avl 木、2 ～ 3 本の木などのバランスの取れた bst を試すこともできます。