avl ツリーの検索が高速であるいくつかの場所でそれを読みましたが、理解できませんでした。私が理解しているように: 赤黒ツリーの最大高さ = 2*log(N+1) AVL ツリーの高さ = 1.44*logo(N+1)
AVLが短いからですか？
3631 次
3 に答える
17
はい。
アイテムを見つけるために必要なステップ数は、アイテムとルートの間の距離によって異なります。
AVL ツリーは密集している (つまり、最大高さが低い) ため、赤黒の場合よりも多くのアイテムがルートに近いことを意味します。
非常にタイトなパッキングは、要素を挿入するときに AVL ツリーがより多くの作業を必要とすることも意味します。アプリの最適な選択は、挿入が多いアプリか検索が多いアプリかによって異なります...
于 2011-05-20T21:21:35.903 に答える
5
AVL ツリーは、入力キーがほぼ昇順/降順の場合、赤黒ツリーよりも優れています。これは、この要素を追加するために 1 回の回転 (左から左または右から右の場合) を行う必要があるためです。また、ツリーのバランスが取れているため、検索も高速になります。
ただし、ランダムに選択された入力キーの場合、RBTree は AVL と比較して挿入に必要なローテーションが少ないため、優れています。
全体として、ツリーの傾斜度と実行される操作を決定する入力シーケンスに依存します。挿入が集中する場合は Red-Black Tree を使用し、検索が集中する場合は AVL を使用します。
于 2012-12-02T10:23:47.733 に答える