バランシングツリーによるバッチ操作

Question

私は自己平衡バイナリ検索ツリーを使用しています（現在はAVLツリーですが、別のツリーに置き換えることができます）。 特定の操作だけが実行されているときは、明確な期間があることに気付きました。ほとんどの場合、大規模な削除または挿入バッチはほとんど実行されず、不変の検索ツリーです。 バッチの終わりにリバランスを延期するとパフォーマンスが向上しますか？

Answer 1

バッチ挿入の場合は、新しい項目を別のAVLツリーに挿入し、http://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/の説明に従って2つのツリーをマージします。ツリーをマージするのはO（m + n）演算で、mとnは2つのツリーのサイズです。このアプローチは、新しいアイテムの数が既存のツリーのアイテムの数に比べて少ない場合にはるかに高速でなければなりません。

バッチ削除の場合は、AVLツリーのアイテムを削除済みとしてマークします。次に、ツリーのインオーダートラバーサルを行い、削除されていないノードから新しいAVLツリーを構築します。例については、http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/を参照してください。ノードのソートされたリストから新しいツリーを構築することは、O（n）操作である。

Answer 2

AVLツリーの漸近的複雑さはO（log（N））です。実際の計算は実行時に明らかに決定されます。

リバランスを遅らせることで速く見せることができますが、リスクが伴います。挿入する平均時間は、ツリーが均衡している場合にのみO（logN）です。バッチインサートによって木が非常に歪んだ場合、O（N）の挿入時間が得られる可能性があります。

とにかく、挿入にはO（logN）が必要なので、リバランスはO（logN）になるので大きな影響はありません。

実際の利点を得るには、挿入のバッチサイズと、挿入/削除中の検索と、挿入されるキーの値を考慮する必要があります。