注文内の他の2つの要素を「間に」挿入できる効率的な注文を維持しますか？
https://cs.stackexchange.com/questions/14708
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私がそうするような多くの要素に注文していると想像してください：
矢印$ x leftarrow y $は$ x <y $を意味します。また、Transitive：$ left（x <y right） wedge left（y <z 右） left（x <z right）$を暗示します。
$ a stackrel {？} {<} d $などのクエリに効率的に回答するために、何らかのラベルまたはデータ構造が必要です。たとえば、ノードに左から右に番号を付けることができます。したがって、整数比較を実行してクエリに答えることができます。それは次のようになります：
数字は順序であり、文字は単なる名前です。
しかし、「間にある」他の2つの要素を注文に挿入する必要がある場合はどうなりますか。
どうすればそのような注文を維持できますか？シンプルな番号を使用すると、「$ 2,3 $の間に整数がない」という問題に遭遇します。
解決
これは次のように知られています 「注文メンテナンス」の問題. 。クエリとインサートの両方に$ o（1）$償却時間を使用した比較的単純なソリューションがあります。さて、「比較的単純」とは、いくつかのビルディングブロックを理解する必要があることを意味しますが、それらを手に入れると、残りは難しくありません。
http://courses.csail.mit.edu/6.851/spring12/lectures/l08.html
基本的なアイデアは、2レベルのデータ構造です。トップレベルは、Realz SlawによるAVLツリーソリューションのようなものですが、
ノードには、長さ$ o（ lg n）$のビット文字列で直接ラベルが付けられており、ツリー内の注文に一致する注文があります。したがって、比較には一定の時間がかかります
AVLツリーよりも回転が少ないツリーは、スケープゴートツリーや重量バランスの木のように使用されているため、relabellingsはあまり頻繁に発生しません。
一番下のレベルは木の葉です。そのレベルは、同じ長さのラベル、$ o（ lg n）$を使用しますが、各葉の$ o（ lg n）$ $のみを単純なリンクリストに保持します。これにより、積極的にリラベルするのに十分な余分なビットが得られます。
葉が大きくなりすぎたり小さすぎたりする$ o（ lg n）$挿入物で、トップレベルの変化を引き起こします。 ）。償却すると、これは$ o（1）$です。
$ o（1）$最悪の時間で更新を実行するために、はるかに複雑な構造が存在します。
他のヒント
単純な番号の代わりに、整数の最小値やCPU整数の最大値など、大きな（一定サイズの）範囲に数値を広めることができます。次に、周囲の2つの数字を平均することで、「間に」数字を入れ続けることができます。数字が混雑しすぎた場合（たとえば、2つの隣接する整数で終わり、その間に数値がありません）、注文全体の1回限りの変更を行うことができ、範囲全体で数値を再配布できます。
もちろん、大きな定数の範囲内のすべての数値が使用されるという制限に遭遇することができます。第一に、これは通常問題ではありません。マシン上の整数サイズは十分に大きいため、より多くの要素があればとにかくメモリに収まらない可能性が高いためです。しかし、それが問題の場合は、より大きな整数範囲でそれらを変更するだけです。
入力順序が病理学的でない場合、この方法は変更を償却する可能性があります。
クエリに答える
単純な整数比較では、クエリ$ left（x stackrel {？} {<} y right）$に答えることができます。
クエリ時間は非常に迅速です（$ mathcal {o} left（1 右）$）。これは、単純な整数の比較であるため、マシン整数を使用する場合。より大きな範囲を使用するには、より大きな整数が必要であり、比較には$ mathcal {o} left（ log {| integer |} right）$が必要です。
挿入
まず、質問で示されている順序付けのリンクリストを維持します。ここに挿入すると、その間に新しい要素を配置するノードを考えると、$ mathcal {o} left（1 右）$になります。
新しい要素のラベル付けは、通常、周囲の数値を平均することで新しいnumeberを簡単に計算するため、通常、$ mathcal {o} left（1 右）$をクイックにします。時々、「中間」という数字がなくなって、$ mathcal {o} left（n right）$の時間変更手順をトリガーします。
変更を避ける
整数の代わりにフロートを使用できます。そのため、2つの「隣接する」整数を取得すると、 できる 平均化されます。したがって、2つの整数フロートに直面した場合、名前を変更することを避けることができます。それらを半分に分割するだけです。ただし、最終的にはフローティングポイントタイプは精度がなくなり、2つの「順応性のある」フロートは平均化できません（周囲の数値の平均は、おそらく周囲の数字の1つに等しくなります）。
同様に、「小数」整数を使用できます。この整数では、要素のために2つの整数を維持できます。 1つは数字、1つは小数です。このようにして、変更を避けることができます。ただし、小数整数は最終的にオーバーフローします。
各ラベルに整数またはビットのリストを使用すると、変更を完全に回避できます。これは基本的に、無制限の長さの小数点以下の数値を使用することと同等です。比較は辞書的に行われ、比較時間は関係するリストの長さに増加します。ただし、これはラベル付けのバランスを崩す可能性があります。一部のラベルには1つの整数（小数なし）のみが必要な場合もあれば、長さの長さ（長い小数）のリストがある場合もあります。これは問題であり、数字（ここで数字のリスト）を選択した範囲で均等に再配布することにより、ここでの変更が役立つ可能性があります（ここでは、おそらくリストの長さを意味します）。 。
この方法は実際には実際に使用されています このアルゴリズム (実装,関連するデータ構造）;アルゴリズムの過程で、任意の順序を保持する必要があり、著者は整数を使用してこれを達成するために変更を変更します。
数字に固執しようとすると、キースペースがやや制限されます。代わりに、変数の長さの文字列を使用して、比較ロジック「a」<"ab" <"b"を使用できます。まだ2つの問題が解決されていないままですA.キーは任意に長くなる可能性がありますB.長いキーの比較は費用がかかる可能性があります
キーレスAVLツリーなどを維持できます。
次のように機能します。ツリーは、AVLツリーが通常行うようにノードの順序を維持しますが、ノードがどこにあるべきかを決定するキーの代わりに、キーはありません。 「2つのノードの間にある別のノード（または言い換えれば」）。ここで、「後」とは、ツリーの順序的なトラバーサルでその後に来ることを意味します。したがって、ツリーは自然にあなたの順序を維持し、AVLの組み込みの回転により、バランスを取ります。これにより、すべてが自動的に均等に分散されたままになります。
挿入
質問に示されているように、リストへの定期的な挿入に加えて、別のAVLツリーを維持します。リスト自体への挿入は、$ mathcal {o} left（1 right）$で、「前」と「後」ノードがあります。
ツリーへの挿入時間は、$ mathcal {o} left（ log {n} 右）$で、AVLツリーへの挿入と同じです。挿入には、後に挿入するノードへの参照が含まれ、右の子の左端ノードの左側に新しいノードを挿入するだけです。この場所は、ツリーの順序で「次」です（次の次のトラバーサルの次は）。次に、典型的なAVL回転を行い、ツリーを再調整します。 「挿入前」についても同様の操作を行うことができます。これは、リストの先頭に何かを挿入する必要がある場合に役立ち、ノードの前にノードがありません。
クエリに答える
$ left（x stackrel {？} {<} y right）$のクエリに答えるために、ツリー内の$ x $と$ y $のすべての祖先を見つけるだけで、その場所の場所を分析します。祖先が分岐する木。 「左」に分岐するものは、2つのうち小さい方です。
この手順では、$ mathcal {o} left（ log {n} right）$ $ツリーをルートに登り、祖先リストを取得します。これは整数の比較よりも遅いように見えるのは事実ですが、真実は同じです。 CPU上の整数比較のみが、$ mathcal {o} left（1 右）$を作成するために大きな定数に制限されています。この定数をオーバーフローする場合、複数の整数（$ mathcal {o} left（ log {n} right）$ $ integers）を維持する必要があり、同じ$ mathcal {o} left（ log { n} right）$比較。または、整数と同じ方法でツリーの高さを一定の量だけ「縛る」ことができます。整数と同じ方法で「チート」することができます。現在、クエリは$ mathcal {o} left（1 right）$になります。
挿入操作デモンストレーション
実証するには、質問にリストから注文していくつかの要素を挿入できます。
ステップ1
$ d $から始めます
リスト：
木：
ステップ2
$ c $、$ emptySet <c <d $を挿入します。
リスト：
木：
注意して、文字cがdの前であるためではなく、リストに$ c <d $のためではなく、 "$ d $の前に$ c $を明示的に配置します。
ステップ3
$ a $、$ emptySet <a <c $を挿入します。
リスト：
木：
AVL回転：
ステップ4
$ b $、$ a <b <c $を挿入します。
リスト：
木：
回転は必要ありません。
ステップ5
$ e $、$ d <e < emptySet $を挿入します
リスト：
木：
ステップ6
$ f $、$ b <f <c $を挿入します
「$ b $ in the Tree」の後に正しく置いただけです。この場合、$ b $の右にそれを取り付けるだけです。したがって、$ f $は、ツリーの順序性トラバーサルで$ b $の直後になります。
リスト：
木：
AVL回転：
比較操作デモンストレーション
$ a stackrel {？} {<} f $
ancestors(A) = [C,B]
ancestors(F) = [C,B]
last_common_ancestor = B
B.left = A
B.right = F
... A < F #left is less than right
$ d stackrel {？} {<} f $
ancestors(D) = [C]
ancestors(F) = [C,B]
last_common_ancestor = C
C.left = D
C.right = B #next ancestor for F is to the right
... D < F #left is less than right
$ b stackrel {？} {<} a $
ancestors(B) = [C]
ancestors(A) = [B,C]
last_common_ancestor = B
B.left = A
... A < B #left is always less than parent
