algorithm - 赤黒木はどのように機能しますか?

Question

赤黒木については多くの質問がありますが、どのように機能するかについては誰も答えていません。なぜ赤黒と呼ばれるのですか？これにより、どのようにツリーのバランスが保たれますか (したがって、バランスの取れていない通常の二分探索ツリーよりもパフォーマンスが向上します)? それがどのように、そしてなぜ機能するかの概要を探しているだけです。

Answer 1

検索とトラバーサルについては、バイナリ ツリーと同じです。

挿入と削除については、ツリーのバランスが崩れないようにすることを目的とした、より洗練されたアルゴリズムが適用されます。これらは、すべての単一項目操作が常に最悪の O(log n) 時間で実行されることを保証しますが、単純な二分木では、二分木が非常に不均衡になり、事実上リンクされたリストになり、O(n) の最悪の場合のパフォーマンスが得られます。各単一項目操作。

赤黒ツリーの基本的な考え方は、ノードごとに最大 3 つのキーと 4 つの子を持つ B ツリーを模倣することです。B ツリー (または B+ ツリーなどのバリエーション) は、主にデータベースのインデックスと、ハード ディスクに格納されたデータに使用されます。

各バイナリ ツリー ノードには「色」 (赤または黒) があります。各黒いノードは、B ツリーの例えでは、その B ツリー ノード内に収まるサブツリーのサブツリー ルートです。このノードに赤い子がある場合、それらも同じ B ツリー ノードの一部と見なされます。そのため、(実際には行われていませんが) 赤黒ツリーを B ツリーに変換し、(ほとんどの) 構造を保持して戻すことができます。唯一の異常は、B ツリー ノードに 2 つのキーと 3 つの子がある場合、同等の赤黒ツリーの黒ノードにどのキーを入れるかを選択できることです。

たとえば、赤黒木では、根から葉までのすべての線に同じ数の黒ノードがあります。このルールは、すべてのリーフ ノードが同じ深さにあるという B ツリー ルールから派生しています。

これは赤黒木が派生する基本的な考え方ですが、挿入と削除に実際に使用されるアルゴリズムは、更新中にすべての B-tree ルール (マイナーな例外があるかもしれません - 私は忘れました) を適用するように変更されていますが、二分木形式に合わせて調整されています。これは、赤黒ツリーの挿入または削除を行うと、B ツリーの挿入または削除を行う場合と比較して、予想される結果とは異なる構造が得られる可能性があることを意味します。

詳細については、MigDus が既に提供しているウィキペディアのリンクに従ってください。

Answer 2

赤黒木は、各頂点が赤または黒に着色された順序付けられた二分木です。 直観的には、赤い頂点はその親と同じ高さにあると見なされます(つまり、赤い頂点へのエッジは「下降」ではなく「水平」と見なされます)。

[ウィキペディアのエントリがこの点を明確にしているとは思えません。]

赤黒木の通常のルールでは、赤い頂点が別の赤い頂点を決して指していないことが必要です。これは、黒い頂点をルートとするサブツリー (bbb、bbr、rbb、rbr -- [左の子][ルート][右の子]) の可能な頂点配置は、234 本の木に対応することを意味します。

赤黒木の検索は、通常の二分木の検索とまったく同じです。挿入と削除は似ていますが、赤黒の不変条件を維持するために、ある時点で「修正」回転が必要になる場合があります。

乾杯！