[data-structures] 赤黒木とAVL樹木の違い



3 Answers

小さなデータの場合

挿入 :RBツリーとavlツリーは最大回転数が一定ですが、RBツリーの方が平均RBツリーの回転が少ないため、RBツリーが高速になります。

ルックアップ :AVLツリーの方が速いため、AVLツリーの方が速くなります。

削除 :RBツリーは最大回転数が一定ですが、AVLツリーは回転のO(ログN)回を最悪として持つことができます。 平均的なRBツリーの回転数も少なくなり、RBツリーがより速くなる。

大きなデータの場合

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

ルックアップ :AVLツリーが高速です。 (小データの場合と同じ)

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

Question

誰かが、これら2つのデータ構造の主な違いを説明してください。 私は差異/類似点を強調するソースをオンラインで見つけることを試みてきましたが、あまりにも有益なものは見つかりませんでした。 どのような場合には、一方が他方より優先されるでしょうか? どのような実用的な状況では、他のものよりも使い勝手が良いのですか?




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




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




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

Red Black Treesには、挿入と取り外しを確実に行うために必要な5つのルールがあります。このルールは、 http://en.wikipedia.org/wiki/Red-black_tree見つけることができます。

赤い黒い木のためにあなたを助けるかもしれない主な事実は、叔父が赤い場合、それらの5つのルールに応じて、あなたは再帰的に木を根に色づけることができるという事実です。 叔父が黒人ならば、あなたが持っている問題を修正するために最大2回の回転をする必要がありますが、1回または2回の回転の後にはあなたは完了です。 あなたがする必要がある操作の終わりなので、それをパックし、おやすみを言う。

大きなルールは5番です... '与えられたノードからその子孫の葉までのすべての単純なパスには、同じ数の黒いノードが含まれます。

これは、あなたが木の仕事をするために必要な回転の大部分を引き起こし、木がバランスを崩し過ぎないようにします。






Related