data-structures - AVLツリーと2-3ツリー間の優先順位

Question

2〜3ツリーを使用するよりもAVLを使用する方が好ましいのか、またはその逆であるのか、誰かに教えてもらえますか？その理由は何ですか？

どうも

Answer 1

バランスのとれたバイナリ ツリーのさまざまなフレーバーの中で、私自身が好むのは AVL ツリーです。それらはどの代替手段よりもプログラムが簡単です (私の実装hereおよびhereを参照してください。削除も特に複雑ではないことに注意してください)。代替案よりもバランスが取れている)、隠れた最悪のケースや償却された時間制限はありません。

また、私は通常、ハッシュ テーブルよりも AVL ツリーを好みます。ハッシュ テーブルの期待される時間の複雑さが、AVL ツリーの保証された時間の複雑さよりも優れていることはわかっていますが、実際には、一定の要因によって 2 つのデータ構造は一般的に競合するようになり、悪い動作を引き起こす予期しないデータについての些細な心配はありません。また、プログラムの保守期間中に、ハッシュ テーブルの最初の選択が正しいように見えたときに予見できなかった状況で、ソートされた順序でデータが必要になることがよくあります。ハッシュ テーブルの代わりに AVL ツリー。それを十分な回数行うと、AVL ツリーから始めたほうがよいことがわかります。

キーが文字列の場合、三分探索試行は AVL ツリーの合理的な代替手段を提供します。