多くの高速優先度キュー（フィボナッチヒープやペアリングヒープなど）は、優先度キューにすでに格納されている要素を取得してその優先度を効率的に下げるキー減少操作をサポートしています。フィボナッチとペアリングヒープの場合、優先キューから要素を削除して後で再挿入するよりも、減少キーを実行する方が高速です。
順序付けられた辞書構造（二分探索木、スキップリストなど）で同様の操作をサポートできるかどうか疑問に思っています。具体的には、順序付けられた辞書があり、あるキーと値のペアのキーを別のキーに変更したいとします。順序付けられた辞書の標準表現で、時間O（1）またはO（log log n）でこれを行うことは可能ですか？バランスの取れたBSTを使用すると、要素を削除して再挿入することでO（log n）時間でこれを実行できるため、興味がありますが、これを実行するより高速な方法があるようです。
ありがとう！
次のシナリオを想像してください。
N 要素を開始します。今、
順序付き辞書のほとんどの実装では、ステップ 1 と 3 の両方に O(N) 時間がかかります。キーの減少に O(1) または O(log log N) の時間がかかる場合、ステップ 2 には O(N) または O(N log log N) の時間がかかります。つまり、O(N) または O(N log log N) 時間で並べ替えることができます。
比較ベースの並べ替えの O(N log N) 下限により、これは、O(1) または O(N log log N) 時間でキーの減少を実行できないことを意味します。
ソートされた配列またはソートされたリンクリストはO(1)、キーの減少または増加をサポートします（重複がない/最小限であると仮定します。第4段落を参照してください）。これは、考えてみると、キーの減少または増加操作のために最大 2 つの要素を交換する必要があるためです。
実際には最良のデータ構造ではありませんが (その場所はありますが)、それでも答えはあります。
唯一の制約は、最初にノードへのポインターが必要なことです。これは、ノードを見つけるだけでO(log n)、それぞれが必要になるためです。O(n)
重複がある場合、移動は両方に対して最悪のケースになる可能性がO(n)あり (ほとんどの値が同じ場合)、これはかなり悪いことです。ただし、リンクリストの場合、リンクリストのリンクリストのようなものを持つことで取得できるはずですO(1)。大きなリンクリストの各ノードは特定の値を表し、そこからの各リンクリストはすべてのノードを表しますその値に等しくなります。
(無駄になるのはもったいないので削除しませんでした)
私が知る限り、少なくとも re-insert と同じくらい効率的ですが、BBSTまたはスキップリストでは、単一の要素で移動するよりも少ない最悪のケースO(log n)は不可能です。平均的なケースは 未満である可能性があります。O(log n)
私たちはそれを探しています -移動したい要素の位置を見つけるためのルックアップはO(log n)、明らかにそれを行う必要があります.
なんらかの奇妙な理由ですでにポジションを持っている場合:
O(log n)最悪の場合の移動がBSTよりも小さくならない理由:ルートを移動しようとしていて、次の要素がツリーの高さにある場合を考慮してください (たとえば、右の子には、左の子を持つ左の子を持つ左の子があります。左の子...木の高さまで）。あなたはO(log n)それを見つける必要があります。
O(log n)最悪の場合の移動がスキップ リストよりも小さくならない理由O(log n): リストに存在するアイテムの後に、それらのリストに存在するアイテムが続く場合を考えてみましょう(これが可能である場合、図O(log n)からそう思われます。私の理解では、スキップリストはやや基本的なものです）。リスト内の該当するアイテムを交換する必要があることは明らかです。O(log n)
すでにその地位にある場合、それが可能な効率的な順序付けられた構造が存在する可能性がありますが、おそらくツリーベースの構造については存在しません (上記の議論のため)。構造。