かなり長い間、私は赤黒木（以下、kchd）と戦いました。私が見つけたすべての情報は、「木の葉と根は常に黒であるため」、「赤黒木の上位5つのプロパティ」、「バランスをとる場合は3ケース、ノードを削除する場合は12ケース」の精神に基づいていました。この配置は私には合いませんでした。
ツリーのプロパティ、擬似コード、バランシングオプションを覚えたくなかったので、その理由を知りたかったのです。色はどのようにバランスをとるのに役立ちますか？赤いノードに赤い子を持たせられないのはなぜですか？木の深さが「黒の高さ」で測定されるのはなぜですか？
これらの質問に対する回答を受け取ったのは、2、3本の木についての講義へのリンクが与えられたときだけでした。
この記事は3つの論理的な部分に分かれています。示されている順序で読むことをお勧めします。最初の部分（これ）は、ccdの紹介とそれを知ることを目的としています。第2部では、バランス調整とccdへの挿入について説明します。3番目の最後の部分では、ノードを削除するプロセスを分析します。辛抱強く読んで楽しんでください:)
免責事項
この記事では、ツリーの長所と短所、そのアプリケーションなどに関する情報はありません。ツリーの漸近解析とインターネット上での操作に関する情報はたくさんあります。
この資料は、すでにccdに精通していて、今はそれらを理解したい人、およびそれらを知り始めたばかりの人を対象としています。
この記事には、構造の実装の詳細は含まれていません。
— . .
-
- , -
, , - - , , , . - - .
- - , . - ( , ). 2-, - 3-. : . :
, .
- , - .
- - , .
, , 5. - 5 .
12. 12 (, ), "" ( , ), .. . 5-12.
. 17. . 5-12-17.
- , . ! "" . . 12, 5, - 17.
, , - . : , "" . 3 :
. , ( ).
. ( ).
. , .
.
, . 3. , . , 3 5. 3 5 . 3-5.
, :)
4 3-5. 3-4-5, , , . ? , .. "" 4 .
. , 4 , - , 4. 5. :
5 ? : - , - . 5 4, 5 , .. . 5 , "", 4-12 (, 5 , "" ).
, . :
, , .
, , , .
, , .
, . , , - . , - (, 4-5-12, , 5 4 12). , . , , ( , 7? 9?).
, , , . , , , . .
, , , . , , ( ). - .
-
, - - . - . ?
, 3-. 3- 2- . - , , , ( ), .
, , .
, - . , , ( , ).
-
, - , , 3- ( ). , , . , ( ).
1.
. , , - 3- 2-3 . , 4-, :)
2.
. , : .
3.
null- (, ) - . , . , , .
nullノードに触れたので、ツリー内のすべてのノードには常に2つの子孫が必要であり、子孫への参照がゼロの場合は、正確にnullノードになります。実際、これは実装に疑問を投げかけます。ヌルノードを追加する方が便利でした（イテレーターやバランシングなどの問題が少ない）。
プロパティ4。
木の高さは黒いノードによってのみ測定され、「黒い高さ」と呼ばれます。ここでも、一般的にすべてが明らかになります。赤いノードは黒いノードへの追加にすぎず、その一部であるため、高さは黒いノードに基づいていると見なされます。
これで紹介は終わりです。次のパートでは、ノードをツリーに挿入してバランスを取る方法について説明します。