0
私は整数値とセグメント[L、R]を持つバランスの取れたAVLツリーを持っています。
この範囲の値を持つすべてのノードを削除し、残りのノードがバランスの取れたAVLツリーを形成するようにツリーを再調整したいとします。AVLツリーから一連の要素を削除する最も効率的な方法は何でしょうか？
この操作の計算量はどのくらいですか？
A
答えて
1
慎重に実行すると、AVLツリーの分割と結合はO（log n）になります。 2つの分割と1つの結合と、ファイナライザ/デストラクタを呼び出す場合は、LからRのすべての値を破棄するためのコストを加えて、操作を行うことができます。したがって、総コストは、デストラクタを呼び出すかどうかによって、O（log n）またはO（log n + k）になります。
私はAVLツリーの分割/結合をやり直すことはありません。挿入や削除のような退屈なケース分析のほんの一握りだからです。 However, I did that elaboration a few years ago for red-black trees.
関連する問題
- 1. MATLABの行列から要素を削除する最も効率的でエレガントな方法は何ですか？
- 2. DenseMatrixから一連の行を削除する最も効率的な方法は？
- 3. Laravel 5.4のデータベースからデータをロードする最も効率的な方法は何でしょうか？
- 4. 配列から項目を削除する最も効率的な方法は？
- 5. MySQLサーバから複数のレコードを削除する最も効率的な方法は何ですか？
- 6. このロジックでVueJSアプリケーションを構築する最も効率的な方法は何でしょうか？
- 7. Hazelcast IMap - 複数のキーの値を取得する最も効率的な方法は何でしょうか？
- 8. クローズとガベージコレクション：リンクされたリストから連続したノードを削除する最も効率的な方法
- 9. 一連の逆転で配列をソートする最も効率的な方法は何ですか？
- 10. ある配列のすべての要素を別の配列から削除する最も効率的な方法は何ですか？
- 11. ArrayListから要素を削除する方が効率的ですか？
- 12. AVLツリーのローテーション効率
- 13. イベントリスナーから関連モデルを更新する最も効率的な方法
- 14. Cでキューからデキューする最も効率的な方法＃
- 15. ソートされたベクトルに要素を挿入する最も効率的な方法は何ですか？
- 16. jQueryでDOM要素にアクセスする最も効率的な方法は何ですか？
- 17. 最も効率的なページヒットを生成する最も効率的な方法
- 18. ハッシュマップオブジェクトから値を削除する効率的な方法
- 19. ユーザーのDirectoryEntryをロードする最も効率的な方法は何ですか？
- 20. ウェブページのアニメーションヘッダをコーディングする最も効率的な方法は何ですか？
- 21. リストビューを作成する最も効率的な方法は何ですか？
- 22. アナリティクスビーコンを保存する最も効率的な方法は何ですか？
- 23. C++ - nullポインタをテストする最も効率的な方法は何ですか？
- 24. UIImageViewを移動する最も効率的な方法は何ですか？
- 25. ダイナミックメニューをレンダリングする最も効率的な方法は何ですか
- 26. ログファイルから最初のN行を削除する最も効率的な方法
- 27. ページにAPIを含める最も効率的な方法は何ですか？
- 28. Zend_Gdata_Spreadsheets：削除し、効率的な方法
- 29. HTML要素がビューポートにあるかどうかを判断する最も効率的な方法は？
- 30. シングルトンと対話する最も効率的な方法は何ですか？
'（R-L）* O（logN）+ K * O（logN）'？すなわち「R-L」回はK回の検索と削除を行い、Kは見つかったノードの数である。 –
@GiorgiNakeuriこれは素朴なアプローチです。私は、任意の与えられた範囲の木の要素の数だけに依存して、最悪の場合の複雑さを持つ解を探しています。 – kichatos