これは存在しなければならない気がしますが、思いつきません。並べ替えられた値のリストを保持し、すばやく検索でき (おそらく配列のように log(N) 時間)、log(N) または定数時間での要素の挿入と削除をサポートするデータ構造はありますか?
質問する
2532 次
1 に答える
3
これは、要素をソートされた順序で格納し、O(log n) 回の挿入、削除、およびルックアップを許可し、すべての要素の O(n) トラバーサルを許可するバランスのとれた二分探索ツリーの記述とほとんど同じです。
バランスの取れた BST を構築する方法はたくさんあります。赤/黒の木、AVL 木、スケープゴートの木、スプレイの木、AA 木、トレップ、(a, b)-木などがあります。これらのどれでも問題を解決できます。それらの中で、おそらくスプレイ ツリーが最もコーディングしやすく、AA ツリーと AVL ツリーがそれに続きます。
お役に立てれば！
于 2013-07-15T06:15:05.687 に答える