2

シーケンシャル コレクション データ構造 (つまり、リストとして表示できるもの) を探しています。

  1. 基本的なスプライシング操作 (リスト内の任意の場所に要素を追加または削除する) は、O(log N) またはそれ以上に償却されます (配列は修飾されません。最後の要素を追加または削除するのが高速なだけだからです)。

  2. これは、機能的に使用された場合でも当てはまります。つまり、操作は非破壊的です (したがって、非破壊的な操作ではリスト全体をコピーする必要があるため、二重連結リストは資格がありません。私が見る限り、同じことがロープにも当てはまります)。

これらの基準を満たすデータ構造はありますか?

4

1 に答える 1

1

はい、バランスの取れた二分木が必要です。それらは純粋に機能的なフレーバーで提供され、ソートされたマップだけでなくシーケンスにも適しています。

必要な適応は、シーケンス インデックスを値にマップすることです。シーケンス操作の途中でコストのかかる再番号付けを回避するには、キーを直接表現しないでください。代わりに、各ノードがその左側のサブツリーにノードの総数を格納するようにします。下方トラバーサル中、トラバーサルが右に行くたびにカウントを追加することにより、現在のノードのインデックスを維持します。

于 2013-07-12T20:48:57.590 に答える