0

O（logn）が削除されたデータ構造をお勧めします。O（1）またはO（logn）のデータ構造の要素のインデックスが必要ですか??

4

1 に答える 1

2

ほとんどの自己平衡順序付き二分木は、各ノードの子の数を維持するように変更でき、操作ごとのlg（n）時間でそれを維持するのは非常に簡単です。

それらは明らかに操作ごとにlg（n）未満のノードを変更し、私の経験では、それらが変更するノードはしばしば「垂直に関連」しています。無料ではありませんが、高くはない傾向があります。 1

ツリーのノードにそのデータがあれば、 nth要素を見つけるのは簡単です（n左側のサブツリーの＃より大きい場合は、左側のサブツリーの＃を減算nして右側のサブツリーに再帰します。それ以外の場合は、変更せずに左側のサブツリーに再帰しますn）。

これは、Bツリーなどの非バイナリの自己平衡ツリーでも機能します。

私の知る限り、stdランダムな対数の削除、挿入、および索引付け操作をサポートするコンテナーはありません。少し前に探しました。また、マルチインデックスコンテナを見ても、ブーストを簡単にチェックしましたが、それを機能させる方法を見つけることができませんでした。

脚注：

1ノードの子の数をノードでO（1）にするコストが必要なツリーを変更する場合、変更からルートまでノードを変更する必要があります。変更されたノードごとに最大でlg（n）個あります。ただし、ノードが相互に「垂直に関連」している場合、修正する必要のあるノードは、ノードが変更されるたびにほぼすべて同じになります。

一方、ツリーリバランスアルゴリズムがなんとかしてlg（n）のまったく無関係なノードを変更したとすると、カウントを維持するためのコストはlg（n）* lg（n）と同じくらい高くなります。

于 2013-02-04T18:58:31.640 に答える