0

これは存在する場合と存在しない場合がありますが、メモリ内で連続し、適度にコンパクトで、O(log n) の償却された挿入と削除を可能にする、並べ替えられた整数のリストを格納する方法を探しています。さまざまな自己均衡二分探索木は、私が望む挿入と削除のプロパティを持っているように見えますが、いたるところにポインターが実装されているため、私のユースケースにはあまり適していません。何か案は?

(実装言語は、問題がある場合は、ほぼ間違いなく C になります。提案されたものの既存の実装があれば、なおさらですが、自分で作成しても問題ありません。)

4

2 に答える 2

0

「読み取りは書き込みよりも多く発生する」という事実に基づいて、動的にサイズ変更された配列+その上でバイナリ検索を使用することができます。そのため、要素への時間アクセス (読み取り) が得られますが、挿入/削除のO(log n)料金を支払う必要があります( - 配列内の適切な場所を検索 + - 要素を右または左にシフト)。ちょっと遅いですが、これがうまくいく方法です。考えてみてください。O(n)O(log n)O(n)

于 2013-06-13T03:56:18.263 に答える