12

何が最適か知りたい：配列または二分探索木（挿入、削除、最大値と最小値の検索）と、両方を改善するにはどうすればよいですか？

4

2 に答える 2

21

配列を使用すると、その中の各要素にランダムアクセスできます。したがって、挿入、削除、およびで特定の要素を検索し、O(1)最大/最小で削除しO(n)ます。[代わりにmax/minO(1)を作成して削除することもできますO(n)]。配列をソートしたままにすると、挿入/削除がになりますが、検索と最小/最大O(n)が得られます。O(logn)O(1)

BSTは定義によってソートされ、通常の[不均衡な] BSTの場合、最悪の場合の動作が発生O(n)します。バランスの取れたBSTの場合、O(logn)挿入/削除/検索を取得します。O(1)あなたは両方のためにどのように最小/最大を得ることができます 。

キャッシュのパフォーマンスが向上するため、配列は通常、反復処理が高速になります[反復の順序は重要ではないと想定] 。また、本質的に無制限のサイズを持つBSTとは異なり、配列は、配列がいっぱいになったときにデータを再割り当てしてコピーする必要があります。

BSTの改善は、 AVLや赤黒木などのバランスをとることで実行できます。

どちらが良いですか？アプリケーションによって異なります。通常、データを挿入して並べ替える場合は、BSTが優先されます。ランダムアクセスまたは反復が主な目的である場合：通常は配列を使用します。

于 2011-12-27T16:55:20.427 に答える
16

配列と二分探索木のパフォーマンス比較：

                 Array                     Binary search tree
          Unsorted   Sorted           Average            Worst case
Space      O(n)       O(n)             O(n)               O(n)
Search     O(n)       O(log n) *       O(log n)           O(n)
Max/Min    O(n)       O(1)             O(1) **            O(1) **
Insert     O(1)       O(n)             O(log n)           O(n)
Delete     O(1)       O(n)             O(log n)           O(n)

*二分探索を想定

**minとmaxへの追加のポインターが必要です。それ以外の場合はO（log n）です。

于 2011-12-27T17:05:38.733 に答える