data-structures - O（logn）アクセスとO（logn）挿入を使用したデータ構造の実装？

Question

最悪の場合O（logn）でk番目のアイテムにアクセスして削除でき、最悪の場合O（logn）でk番目のアイテムの後にアイテムを挿入する操作をサポートできるデータ構造を知っている人はいますか？

Answer 1

はい。あなたが説明することは、増強された木で達成することができます。すべてのノードには、そのサブツリー（それ自体を含む）内のノードの数を示すカウンターがあります。リーフノードの場合、カウンターは1です。ルートノードの場合、カウンターはノードの総数です。このようにして、ルートから始まる二分探索でk番目のアイテムを見つけることができます。要素を挿入/削除するときはいつでも、その位置からルートに移動するパスのカウンターを更新する必要があります。

この種のツリーは、順序統計ツリー、ランクツリー、カウンターツリーと呼ばれています...

ここに実装があり、ここに別の実装があります。

Cormen、Leiserson、Rivest、Steinによる素晴らしい本「IntorductiontoAlgorithms」の第14章「AugmentingDataStructures」を参照してください。

Answer 2

（キーではなく）整数インデックスが必要な場合は、ropeまたはdequeを調べてください。これらの操作では、基本的にO（c）になります。

連想データ構造に関しては、典型的なハッシュテーブルもO（c）で償却され、バランスの取れたツリーはO（log（n））になります。