performance - AVLツリー上の二分探索木

Question

私の知る限り、AVLツリーとバイナリサーチツリーの時間計算量は平均的な場合と同じであり、最悪のシナリオではAVLがBSTを上回っています。これは、AVLと相互作用するためのあらゆる方法でAVLがBSTよりも常に優れていることを示唆しており、実装のバランスをとる際に少し複雑になる可能性があります。

そもそもAVLの代わりにBSTを使うべき理由はありますか？

Answer 1

まず、可能な限り最高のパフォーマンスを得ることは、プログラミングの最終目標ではありません。そのため、オプション B が常に A よりも高速で消費メモリが少なかったとしても、それがより複雑であれば、常により良いオプションであるとは限りません。より複雑なコードは、作成に時間がかかり、理解しにくく、バグが含まれる可能性が高くなります。したがって、単純だが効率の悪いオプション A で十分である場合は、それがより良い選択であることを意味します。

ここで、バランスをとらずに AVL ツリーを単純な二分探索木 (BST) と比較する場合、AVL はより多くのメモリを消費し (各ノードはバランス係数を記憶する必要があります)、各操作は遅くなる可能性があります (バランスを維持する必要があるため)。因数分解し、場合によってはローテーションを実行します)。

あなたが言ったように、バランシングなしのBSTには非常に悪い（線形の）最悪のケースがあります. しかし、このような最悪のケースが起こらないことがわかっている場合、またはまれに動作が遅くても大丈夫な場合は、バランス調整なしの BST が AVL よりも優れている可能性があります。

Answer 2

私の仮定は次のとおりです。BSTについて言及する場合、バランスのないBSTを意味します。

ナビゲート可能なデータ構造が必要で、データが最悪のケース (ソート済み) ではなく、やや小さいことがわかっている場合は、BST (バランスなし) が適切であると主張できます。

しかし、それはおそらくまれなケースです。

Answer 3

AVL ツリーも BST ですが、それ自体を再調整できます。この動作により、最悪の場合でも高速になります。それは自分自身を再調整し続けるので、最悪の場合、プレーンな BST が O(n) かかるときに O(log n ) の時間を消費します。したがって、あなたの質問への答え: 単純な BST よりも AVL ツリーを実装する方が常に優れています。