問題タブ [red-black-tree]

私が学んでいる教科書 (Lafore) は、最初に Red-Black Trees を提示し、疑似コードは含まれていませんが、提示された関連アルゴリズムはかなり複雑で、多くのユニークなケースがあります。

次に、彼は 2-3-4 Trees を提示します。これは、私には理解するのがはるかに簡単で、実装するのが簡単だと思います。彼には、非常に明確な実際の Java コードがいくつか含まれています。彼は 2-3-4 の方が実装しやすいとほのめかしているようで、これまで見てきたことに基づいて同意します。

ただし、ウィキペディアは反対のことを言っています...おそらく間違っていると思います：

http://en.wikipedia.org/wiki/2-3-4_tree

2-3-4 木は赤黒木の等長図であり、同等のデータ構造であることを意味します。つまり、2-3-4 ツリーごとに、データ要素が同じ順序の赤黒ツリーが少なくとも 1 つ存在します。さらに、ノードの拡張、分割、およびマージを引き起こす 2-3-4 ツリーの挿入および削除操作は、赤黒ツリーの色反転および回転と同等です。赤黒木への導入では、概念的に単純であるため、通常、最初に 2-3-4 木を紹介します。ただし、2-3-4 ツリーは、ツリーの操作に多数の特殊なケースが含まれるため、ほとんどのプログラミング言語で実装するのが難しい場合があります。赤黒木は実装が簡単なので、代わりに使用される傾向があります。

具体的には「特例が多い」という部分がかなり後ろ向きに思えます（特例が多いのは2-3-4ではなくRBだと思います）。しかし、私はまだ学んでいます (そして、正直なところ、赤黒の木について完全に理解していません) ので、他の意見を聞きたいです。

補足として...私はLaforeの言うことのほとんどに同意しますが、ウィキペディアが一般的であると言っているのとは逆の順序で彼がそれらを提示したことは興味深いと思います（RBの前に2-3-4）。RBは概念化するのが非常に難しいため、最初に2-3-4がより理にかなっていると思います。おそらく、彼がその順序を選んだのは、RB が、彼が前の章で完成させたばかりの BST とより密接に関連していたからです。

赤黒の木と 2-3-4 の木の両方と、それらが高さのバランスを維持して最悪の場合の操作が O(n logn) であることを確認する方法について、基本的な理解があります。

しかし、ウィキペディアからこのテキストを理解することはできません

2-3-4 木は赤黒木の等長図であり、同等のデータ構造であることを意味します。つまり、2-3-4 ツリーごとに、データ要素が同じ順序の赤黒ツリーが少なくとも 1 つ存在します。さらに、ノードの拡張、分割、およびマージを引き起こす 2-3-4 ツリーの挿入および削除操作は、赤黒ツリーの色反転および回転と同等です。

操作がどのように同等かわかりません。ウィキペディアのこの引用は正確ですか? 操作が同等であることをどのように確認できますか?

Cで赤黒の木を完成させましたが、レベル順で印刷するのは難しいと思います。print-inorder がありますが、コンソール印刷でツリーとして表示する方法を想像できません。それは実現可能ですか？ここに BFS または DFS を実装できますか? ウィキでアルゴリズムを見つけましたが、適用できません。誰かが C でコードを持っている場合は、ここに投稿して勉強できますか? ウィキから：

赤黒木がほぼ完成しましたが、削除が誤動作しています。削除されない可能性のあるノードを削除する可能性があります。ルートを削除して印刷オプションを押すと、ツリーにすでに存在するノードが画面にスパム送信されます。プログラムがクラッシュするまで、2,1,7,5,8,11,14,15,4削除root=7して順番に印刷するなどのテストツリーで取得します。2,4,5,8,1,2,4,5,8,1,.....2を削除すると、プログラムが即座にクラッシュします。ノード11は、1-4-15のようなすべての葉と同様に、正常に削除されます。デバッグの問題を見つけようとしましたが、すべて正常に機能しているようです。このコードは、コーメンのアルゴリズムの紹介に基づいています。ありがとう！

標準の二分探索木とその操作を完全に理解するのは非常に簡単です。その理解のおかげで、挿入、削除、検索操作の実装を覚える必要さえありません。

私は現在赤黒木を学んでおり、木のバランスを保つためのその特性を理解しています。しかし、その挿入と削除の手順を理解するのは非常に難しいと感じています。

新しいノードを挿入するときは、ノードを赤でマークすることを理解しています (赤黒木の法則をあまり破らないようにするには、赤が最善であるため)。新しい赤いノードは、「連続した赤いノードの法則」にまだ違反している可能性があります。次に、次の方法で修正します。

1. 赤の場合は叔父の色を確認し、親と叔父を黒としてマークし、祖父母に移動します。

2. 右の子の場合、親を左回転

3. 親を黒、祖父母を赤としてマークし、祖父母を右回転させます。

完了 (基本的には上記のように)。

上記のように赤黒木の挿し込みを記載している箇所が多いです。彼らはただそれを行う方法を教えてくれます。しかし、なぜこれらの手順でツリーを修正できるのでしょうか? なぜ最初に左に回転し、次に右に回転するのですか?

CLRSよりも明確に、なぜ私にもっと明確に説明できますか? 回転の魔法とは？

1年も経てば、本を読まなくても自分で赤黒木を実装できるようになるので、本当に理解したいと思っています。

ありがとう

Cormenの擬似コードに従って、Pythonの赤黒木に実装しましたIntroduction to Algorithms。

insert自分が本当に自分であるかどうかを自分の目で確認したかったので、ノードをツリーO(logn)に挿入するのにかかる時間をプロットしました。n=1, 10, 20, ..., 5000

結果は次のとおりです。

x-axisはnであり、-axisyはミリ秒単位の時間です。

私には、グラフは対数よりも線形に見えます。何がそれを説明できますか？

ここで、stackoverflow で同様の質問を見ましたが、(明らかに) 回答がありませんでした。

5 つの RB ツリーのいずれも無効にすることなく、そのようなツリー (8 つの黒いノードと 12 の赤いノード) を構築しようとすることができます (ただし、これまでのところ、それを行うことはできませんでした)。

1. ノードは赤または黒のいずれかです
2. 根元が黒い
3. 葉っぱが全部黒い
4. すべての赤いノードの両方の子は黒です
5. 特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます。

しかし、私はよりエレガントな答えに本当に興味があります(それが機能するかどうか試してみる以外に)。

編集：葉が黒としてカウントされる場合、そのようなツリーを構築することは不可能であることは明らかです. しかし、葉が黒いノードとしてカウントされない場合はどうでしょうか (8 つの非葉ノード)。

削除機能が動作しません。ノードを削除すると、残っているのはノードのサブツリーです。

これの何が悪いと思いますか？前もって感謝します。

赤黒ツリーに新しく挿入されたノードが赤の親、黒の叔父を持ち、祖父母（黒）とインラインである場合のこのケース（5番目のケース）の処理方法を知っています。たとえば、次の場合:
R2(現在のノード、R1 の左の子) -----R1(左の子)-----B0(ルート)----B1(右の子)

上記のケースでは、ルート ノード (B0) を中心にツリーを回転させて、

R1----R2(新しいルート ノード)------B0(R2 の右の子)------B1(B0 の右の子)

次に、B0 の色を赤に、R2 を黒に変更します。

これは標準的な解決策ですが、B0 の色を赤に、R2 を黒に変更する代わりに、R1 の色を黒に変更すると、赤黒ツリーのプロパティが侵害されていることがわかりません。

誰でもこれに光を当てることができますか？ありがとう （：