83

これら2つのデータ構造の主な違いは何ですか? 違い/類似点を強調するソースをオンラインで見つけようとしましたが、あまり有益なものは見つかりませんでした. どのような場合に、一方が他方よりも優先されますか? どちらを使用するのが他の使用よりも「優れている」実際の状況は何ですか?

4

9 に答える 9

56

小さなデータの場合:

insert : RB ツリーと avl ツリーの最大ローテーション数は一定ですが、平均して RB ツリーはより少ないローテーションを使用するため、RB ツリーの方が高速になります。

lookup : AVL ツリーの深さが少ないため、AVL ツリーの方が高速です。

delete : RB ツリーには一定数の最大回転がありますが、AVL ツリーには最悪として O(log N) 回の回転があります。また、平均してRBツリーの回転数も少ないため、RBツリーの方が高速です。

大きなデータの場合:

insert : AVL ツリーの方が高速です。挿入する前に特定のノードを検索する必要があるためです。データが増えると、特定のノードを検索する際の時間差が O(log N) に比例して大きくなります。しかし、AVL ツリーと RB ツリーは、最悪の場合でも一定数の回転しか必要としません。したがって、ボトルネックは、その特定のノードを検索する時間になります。

lookup : AVL ツリーの方が高速です。(小さいデータの場合と同じ)

delete : 平均的には AVL ツリーの方が高速ですが、最悪の場合は RB ツリーの方が高速です。削除する前にスワップする非常に深いノードを検索する必要があるためです (挿入の理由と同様)。平均して、両方の木の回転数は一定です。ただし、RB ツリーには回転の一定の上限があります。

于 2015-03-04T04:11:00.073 に答える
3

木の最大高さは、バランスを保つために最も重要です。1.44 * log(n)AVL ではほぼ同じですが、RB ツリーでは です2 * log(n)。したがって、問題が検索インセンティブである場合は、AVL を使用する方がよいという結論を得ることができます。重要なのは、AVL と RB ツリーに関する別の問題です。ローテーションのコストが低いランダムな挿入に直面する場合、RB ツリーは AVL よりも優れていますが、昇順または降順のデータを挿入するには AVL が適しています。問題が挿入インセンティブである場合は、RB ツリーを使用できます。

于 2014-06-15T04:00:14.470 に答える
3

AVL ツリーがどのように機能するかを理解するには、このインタラクティブな視覚化が役立ちます。

AVL と RedBlack ツリーは、高さのバランスが取れたツリー データ構造です。それらは非常に似ており、実際の違いは、追加/削除操作で実行されるローテーション操作の数にあります。AVL の場合は、全体的に均一なバランスを維持するために高くなります。

両方の実装は、N が葉の数である としてスケーリングしますO(lg N)が、実際には AVL ツリーはルックアップ集中型タスクでより高速です: より良いバランスを利用して、ツリー トラバーサルは平均でより短くなります。一方、挿入と削除に関しては、AVL ツリーは遅くなります。変更時にデータ構造を適切に再調整するには、より多くのローテーションが必要です。

汎用目的の実装 (つまり、ルックアップが操作の大部分を占めているかどうかはアプリオリには明らかではありません) では、RedBlack Trees が推奨されます。データ構造が検索と同じくらい頻繁に変更される場合はいつでも、実装が簡単で、一般的なケースでより高速です。 . 一例として、TreeMapJavaTreeSetではバッキング RedBlack Tree を利用します。

于 2015-12-17T14:58:54.703 に答える
3

AVL ツリーは、赤黒ツリーと比較されることがよくあります。これは、どちらも同じ一連の操作をサポートO(log n)し、基本的な操作に時間がかかるためです。ルックアップを多用するアプリケーションの場合、AVL ツリーは赤黒ツリーよりも高速です。赤黒木と同様に、AVL 木は高さのバランスがとれています。どちらも一般に、μ ≤ ½ の場合、重量バランスも μ バランスもありません。つまり、兄弟ノードは、非常に異なる数の子孫を持つことができます。

AVL ツリーに関するウィキペディアの記事から

于 2013-12-07T22:33:42.827 に答える
2

RedBlack ツリーの回転が少ないという事実により、挿入/削除が高速になりますが、.... それらは通常少し深いため、挿入と削除で遅くなる可能性もあります。ツリーのあるレベルから次のレベルに移動するたびに、要求された情報がキャッシュになく、RAM から取得する必要があるという大きな変化があります。したがって、ローテーションが少なくて得られた時間は、より深くナビゲートする必要があり、キャッシュをより頻繁に更新する必要があるため、すでに失われている可能性があります。キャッシュから操作できるかどうかは大きな違いです。関連する情報がキャッシュにある場合は、追加のレベルをナビゲートするのに必要な時間内に複数のローテーション操作を実行でき、次のレベルの情報はキャッシュにありません。したがって、必要な操作だけを見ると、理論上は RedBlack の方が速い場合でも、実際には遅くなる可能性があります。

于 2016-01-08T15:25:20.820 に答える
1

要約すると、AvlTrees は RedBlackTrees よりもわずかにバランスが取れています。どちらのツリーも、ルックアップ、挿入、および削除に全体で O(log n) 時間かかりますが、挿入と削除の場合、前者は O(log n) ローテーションが必要ですが、後者は O(1) ローテーションしかかかりません。

ローテーションはメモリへの書き込みを意味し、メモリへの書き込みはコストがかかるため、実際には RedBlackTree は AvlTree よりも更新が高速です。

于 2015-05-11T17:18:51.483 に答える
1

私が見てきたことから、AVL ツリーは、AVL ツリーの目的の高さ (Log n) を取得するために必要なだけ多くの回転 (時々再帰的にツリーを上る) を行うようです。これにより、より厳密にバランスが取れます。

Red Black Trees には、挿入と削除を確実に行うために必要な 5 つのルールセットがあります。

赤い黒い木の場合に役立つ主な点は、これらの 5 つのルールに応じて、叔父が赤の場合に木の根元まで再帰的に色を付けることができるという事実です。叔父が黒人の場合、問題を解決するために最大 2 回のローテーションを行う必要がありますが、1 回か 2 回のローテーションで完了です。それを詰め込んで、おやすみなさいと言いましょう。

大きなルールは 5 番です... 「特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます」。

これにより、ツリーを機能させるために必要なほとんどの回転が発生し、ツリーのバランスが崩れすぎなくなります。

于 2013-07-23T22:56:53.593 に答える