基本的に、保証された O(log n) 削除の方法が必要です。これは二分木で行うことができますか、それとも常に最悪の場合 O(n) ですか?
毎回ツリーのバランスをとったらどうなりますか?
助けてください
3 に答える
3
保証が機能するには、バランスの取れたバイナリ ツリーが必要です。Red Black Trees は、バランスの取れたツリー構造の例であり、実装はそれほど難しくありません。
そして、ここにそのための素晴らしい講義があります..
于 2012-06-27T05:56:24.460 に答える
2
バランスの取れた二分木を探している場合は、「ヒープ」を使用できます
于 2012-06-27T05:50:12.553 に答える
1
二分探索木が必要です
上記のwikiページが言ったように：
したがって、最悪の場合、木の高さに比例した時間がかかります
つまり、常にバランスを取ることができれば、削除のために O(logN) を取得できます
于 2012-06-27T05:55:30.083 に答える