赤黒の木からノードを削除するのは簡単な作業ではないため、ノードをいくつかの部分に分割し、それぞれのケースを個別に検討することは理にかなっています。
cartoonbank.ru
では前回の記事、我々は赤黒探索木を形成するためのルールを検討し、要素を追加する際のバランスの例を検討しました。
それでは、アイテムの削除について説明しましょう。
たとえば、この赤黒の木を見てください。
赤黒の木の主な特性は、各ノードの左右で同じ黒の高さであることを思い出してください。したがって、図では、各ノードの横に黒の高さの値を示し、各段階でその安定性を確認できるようにします。
分裂とルール
赤黒の木から要素を削除することは、一見しただけでは簡単な作業ではないので、いくつかの部分に分割して、それぞれを個別に検討することを提案します。
まず、タスクを2つのカテゴリに分けてみましょう。
- 削除されたノードの色：KまたはH
- 子ノードの数：2、1、または0
その結果、K2、Ch2、K1、Ch1、K0、Ch0の6つのオプションのマトリックスが得られます。
オプションごとに、ツリーの対応するノードが示されます。
各オプションの削除プロセスを考えてみましょう。
K2-子供が2人いる赤い結び目
2つの子を持つノードを削除するタスクは、1つまたは0の子を持つノードを削除するタスクに削減されます。
これを行うには、削除された要素よりも少ないまたは多い最も近い要素を見つけて、それらを交換する必要があります。
要素を交換するときは、ツリー構造を壊したり、黒の高さを変更したりしないように、ノードの値のみを変更し、色を同じままにする必要があることに注意してください。
交換後、新しい場所からアイテムを削除する必要があります。これは、左側のブランチの右端の要素（左側の最大）または右側の左端（右側の最小）のいずれかになります。いずれの場合も、左側または右側に1つの子はありません。したがって、2つの子を持つノードを削除するタスクは、1つまたは0つの子を持つ要素を削除するタスクに削減されます。
- K2 => K1またはK0
Ch2-子供が2人いる黒い結び目
前のケースと同様に、黒いノード16を削除する例を示します。
ご覧のとおり、交換後、タスクは1つの子を持つ要素を削除することになります。
- Ch2 => Ch1またはCh0
K1-子供が1人いる赤い結び目
赤のノードに子が1つもない場合は、代わりに黒のNIL要素があり、赤のノードの黒の高さは1です。したがって、一方、黒の高さも1になります。ただし、赤のノードに赤の子を含めることはできないためです。色、そして彼の他の子供は黒でなければなりません。黒の高さは1でなければならないので、通常の黒の要素の場合は高さが高くなるため、黒のNIL要素のみにすることができます。
したがって、K1ケースは発生しません。
Ch1-子供が1人いる黒い結び目
黒の要素に子が1つもない場合は、代わりに高さが黒の黒のNIL要素があります。1したがって、反対側には子のない赤いノードがあるはずです。このような要素を削除するには、黒の高さを維持しながら、赤の要素の値を黒のノードに転送するだけで十分です。
K0-子供がいない赤い結び目
最も単純なケース。要素を削除して、NIL参照に置き換えるだけ
です。赤い要素を削除しても、黒い高さは変わりません。
CH0-子供がいない黒い結び目
子のない黒いノードを削除することも非常に簡単です。NILへの参照に置き換えます。
これでほぼすべてだと思いますか？はは、6回。
黒の要素を削除すると、サブツリーの黒の高さが変化するため、親とのバランスを取る必要があります。
図で削除された要素は、x、その高さ--hで示されます。バランシングを開始したばかりの場合、h = 1ですが、再帰呼び出しでは増加する可能性があります。
明確にするために、削除された要素が正しい子であったことを確認しましょう。取り外した後、その高さは減少し、hになりました。これは、左の息子の身長がh +1のままであることを意味します。左右のサブツリーの高さを揃えて、h +1に等しくする必要があります。
タスクをもう一度いくつかの部分に分割することをお勧めします。どのようなオプションがありますか？
親は赤または黒にすることができます。左の息子も黒または赤にすることができます。そして、右の息子は常に黒人です-そこから私たちは除去後にバランスを取るようになりました。
考慮すべき6つの異なるケースがあります。
- KCH1およびKCH2-親は赤、左の子は黒です。
- CHK3およびCHK4-親は黒、左の子は赤です。
- HH5およびHH6-親は黒、左の子は黒です。
私たちは忍耐とポップコーンを買いだめします、最も興味深くそして神秘的なものは先にあります。
1-親は赤、左の子は黒、孫は黒
赤いノードがある限り、それらを移動または色変更して、黒い高さのバランスを復元できます。この場合、親から左の息子に赤い色を下げて、親の黒の高さを揃える
ことができます。図から、ノードaとbの黒の高さが保持され、サブツリー全体の高さが同じでh +1になっていることを再確認してください。
KCH2-親は赤、左の子は黒、左の赤い孫。
この場合、塗り直しだけでは不十分です。ノード3〜7の間で右に少し曲がる必要があります。その結果、右側のサブツリーの高さをh + 1に増やすことができ
ます。緑色のノードは、黒または赤のいずれかであることを意味します。
注意。ノード「1」が黒で「c」が赤の場合、問題はバリアントHH5に減らすことができます。
CHK3-親は黒、左の息子は赤、右の孫には黒のひ孫がいます
黒の曾孫がいると、孫を赤に塗り直して、小さな右折3〜7を行うことで右のサブツリーに送信できます。理由は聞かないでください。信頼して、黒の高さが安定していることを確認して
ください。赤のノード5は黒を増加させないことに注意してください。高さ。
CHK4-親は黒、左の息子は赤、右の孫は左のひ孫が赤
赤い森の奥には、黒い薪が多く、赤い薪が少なくなっています。つまり、赤いノードの色を変えることで、黒い高さを安定させることができます。
この場合、5-3と5-7の2つの小さなターンで構成される大きな左ターンを行う必要があります。ノードbの色が赤から黒に変わったため、高さが1増加しました。黒の高さが安定していることを確認してください。
HCH5-親は黒、左の息子は黒、右の赤い孫。
前の場合と同様に、サブツリー内の赤い要素が少なくなり、最後の赤い孫を黒く塗り直して、大きく左に曲がります。
サブツリーの黒の高さが安定していることを確認します。
HCH6-親は黒、左の息子は黒、孫も黒
そして、赤い木がなくなった瞬間が来ました。何もする必要はありません。黒いノードを赤く塗り、ノード7の黒い高さを等しくする必要がありますが、右側のサブツリーの黒い高さを増やすのではなく、左側のサブツリーの黒い高さを下げる必要があります。その結果、構造全体の黒の高さが1減少し、先祖に繰り返しバランシングを呼び出す必要があります。
バランシングと再帰を使用した削除の例
赤黒の木から要素を削除した後、黒の高さのバランスをとる6つのケースすべてを調べました。これがどのように機能するかをよりよく理解するために、元のツリーからノード30を削除し続けましょう。
最初のステップ-ノード30を削除するだけです
。2番目のステップ-その親でバランスをとって実行します-ノード
25。CHCH6の場合があります：
安定したユニット25
の半分の高さに悲しみがあります。3番目のステップ-バランスのレベルの祖父-ノード20の
ために。、バランスの前後にツリー全体を描きましょう。これはHK4の場合です。
バランスをとった後、赤黒の木がどのように変化したかに注目してください。左側のサブツリーの一部の要素が右に移動し、高さが安定し、要素が削除されました。誰もが満足しています。
赤黒ツリーからアイテムを削除することは、バイナリ検索ツリーを操作するときに最も難しい操作の1つです。「アルゴリズムとデータ構造」コースでは、バイナリ検索ツリーだけでなく、他の多くの興味深いアルゴリズムについても検討します。詳細については、コースプログラムを参照してください。
