赤と黒の木
赤と黒の木は、データ構造やアルゴリズムでよく言及されるが、詳細に説明することはできない木です。また、技術的なインタビューでよく尋ねられる木でもあります。しかし、それが本の資料であろうとオンラインの資料であろうと、それらは通常より厳格で理解しにくいです。赤と黒の木をより直感的に理解できますか？この記事では、赤と黒の木の挿入と削除操作についてグラフィカルな方法で説明します。
ツリー構造を学ぶことは進歩的なプロセスです。私たちが通常接触する木はバイナリツリーです。簡単に言えば、各非葉のノードには、左の子供と右の子供と呼ばれる2人の子供のみがあります。バイナリ検索ツリーと呼ばれるバイナリツリーには、特別なタイプのツリーがあります。バイナリ検索ツリーは順序付けられたツリーです。葉以外のノードごとに、左サブツリーの値はそれよりも小さく、右サブツリーの値はそれよりも大きくなります。バイナリ検索ツリーよりもさらなるステップは、バイナリバランスツリーです。順序を確保することに加えて、バイナリバランスツリーは、各ノードの左と右のサブツリーの高さの違いを維持することもできます。一般的なバランスの取れた木は、AVLツリー、TREAP、赤と黒の木、ストレッチツリーなどです。
赤と黒の木はバイナリ検索ツリーですが、各ノードにストレージビットを追加して、ノードの色を表します。ノードは赤または黒です。各ノードがルートから葉までのパス上でどのようにシェーディングしているかを制限することにより、赤黒の木は、他のパスの2倍の長さのパスがないことを保証し、バランスに近づきます。
赤と黒の木は5つの特性を満たします：
赤黒の木では、従来のバイナリツリーの葉のノードの子供をnilに指し、赤黒樹の葉のノードをnilと呼ぶことに注意してください。 NILノードには、親ノードへのポインターが含まれています。これが、NILに変更する必要がある理由である場合があります。
1.操作を挿入します
まず、バイナリ検索ツリーを挿入する方法に新しいノードを挿入し（挿入された新しいノードはすべて葉のノードにあります）、赤で描画します。次に、色を再描画するか、それを回転させて、赤と黒の木の特性を維持します。調整は、次の3つの状況に分かれています。
1新しいノードnには親ノードがありません（つまり、ルートにあります）
新しいノードnを黒としてペイントします。
2新しいノードnの親ノードPは黒です
調整する必要はありません。
3新しいノードnの親ノードPは赤です
赤と黒の木は2つの連続した赤いノード（プロパティ4）を許可していないため、調整する必要があります。 nの叔父ノードの色に応じて、それは2つの状況に分かれています：（nの親ノードPを左子として例として、Pを同様の状況として適切な子供として使用するので、詳細に説明しません）
3.1新しいノードnの叔父ノードuは赤です。新しいノードnの親ノードPとアンクルノードUは黒として塗装され、祖父ノードGは赤として塗装されているため、Gから各ヌルノードへのパスに含まれる黒いノードの数が元のものと一致するようにします。しかし、Gを赤に変えるので、Gの父親も赤である場合、2つの連続した赤いノード（自然4に違反）につながる可能性があるため、Gが赤と黒の木の性質に違反するかどうかを再確認する必要があります。
3.2新しいノードnの叔父ノードuは黒です。新しいノードnが親ノードPの左子である場合、親ノードPを黒として描画し、祖父ノードGを赤として描画し、次にGを1回回転させます。
新しいノードnが親ノードPの右子である場合、親ノードで左回転を実行すると、問題は左子の状況に変換されます。
2.操作を削除します
「アルゴリズムの紹介」とウィキペディアの方法は、ブラックノードDを削除し、Dの黒を子ノードCに押し下げる「プッシュダウン」を削除することです。つまり、Cは独自の色に加えて黒の余分な層を持ち、その後、木に沿ってツリーに沿って黒の余分な層を移動し続け、赤いノードに遭遇し、ブラックが根を移動するか、ブラックを移動させます。そのため、すべてのパスの黒いノードの数が1つずつ減少し、等しいままです。上向きの動きの間、パス上の黒いノードの数が変化しないようにするために、いくつかのノードの色を回転および変更する必要がある場合があります。
このアプローチは、コードの実装（反復的な方法で使用できます）の実装に有益かもしれませんが、理解するのは便利ではありません（個人的には信じています）。優先順位を理解するために、削除されたノードDの子がゼロかどうかに基づいて、次の分類を作成しました。
1ノードDが削除された両方の子供はnilです
1.1削除されたノードDが赤の場合は、Dをnilに置き換えます。
1.2削除されたノードDは黒です（例としてDを取りましょう）
1.2.1兄弟Dが削除されたノードBの両方の子供はnilです
Dの兄弟ノードBは赤と親ノードPが黒として塗装されているように塗装されています。
フィギュアの半分と半分は、ノードが赤または黒である可能性があることを意味します。 Pが赤であることが判明した場合、変更後のパス上の黒いノードの数は、削除前と同じです。 Pが黒であることが判明した場合、Dを削除すると、削除前よりもパス上の黒いノードの数が1つ少なくなるため、Pを通過するパス上のブラックノードの数の変化が赤と黒の木の特性に影響するかどうかを確認し続ける必要があります。
1.2.2ノードDの兄弟ノードBには子供がいない
子供は赤でなければなりません。そうしないと、Dの親ノードから各リーフノードまでのパス上の黒いノードの数は異なります（違反5）。
この子供が右の子供の場合は、Bの右の子供を黒として描き、親ノードPの元の色としてBを描き、Pを黒として描画し、片方の左でPを回転させます。
この子供が左の子供である場合は、Bの左の子供を黒、Bの赤い子供として描画し、Bを右に回転させると、問題は右子の状況に変わります。
1.2.3削除されたノードBの両方の子供はnilではありません
Bが赤の場合、Bの2人の子供は黒人でなければなりません。 Bを黒、Bの左の子供を赤として描き、次にPの左回転を実行します
Bが黒い場合、Bの2人の子供は赤でなければなりません。 Bの親ノードPを黒として描画し、Bの右子は黒、Bの元の色は親ノードPとして、次に片方の左でPを回転させます。
2ノードDが削除された子供はnilではありません
ノードを削除するバイナリ検索ツリーによれば、dの後継ノードsを見つけ、dとsの内容を交換し（色は変わらないまま）、削除されたノードはSになります。Sがnilではないノードを持つ場合、sの後継ノードをsの後継ノードに置き換え続けます。問題は、削除されたノードDの両方の子供がゼロである状況に変わります。
3削除されたノードDには、nilではなく子供がいます
この子cは赤いノードでなければなりません。そうしないと、dから各nilノードまでのパス上の黒いノードの数が異なります（違反5）。
dとcの内容は交換され（色は同じままです）、削除されたノードはcになり、問題は削除されたノードDの両方の子供がnilである状況に変わります。
バイナリツリーのトラバーサル
バイナリツリーには3種類のトラバーサルがあります：事前注文トラバーサル、中間トラバーサル、およびポストオーダートラバーサル。横断的実装には、再帰と反復の2種類があります。この記事では、よりエレガントなコードを使用してバイナリツリーのトラバーサルを実装する方法について説明します。
まず、バイナリツリーのノードを定義します。
public class treeNode {int val;左のtreenode; treenode右; public Treenode（int x）{val = x; }}
1。トレーバーを予約注文します
簡単に言えば、予約注文トラバーサルは、最初に親ノードにアクセスし、次に左の子供にアクセスし、最後に右の子供にアクセスすることです。つまり、親の順に左右に通過します。
再帰的実装は非常に簡単で、コードは次のとおりです。
パブリッククラスソリューション{list <integer> result = new ArrayList <Integer>（）; public List <Integer> Preodertraversal（treeNode root）{dfs（root）;返品結果; } private void dfs（treenode root）{if（root == null）{return; } result.add（root.val）; dfs（root.left）; dfs（root.right）; }}反復実装では、アクセスされない正しいノードを保存するためのスタックが必要です。コードは次のとおりです。
パブリッククラスソリューション{public list <integer> pre -ordertraversal（treeNode root）{list <integer> result = new ArrayList <Integer>（）; if（root == null）{return result; } stack <treenode> stack = new stack <treenode>（）; stack.push（root）; while（！stack.isempty（））{treenode curr = stack.pop（）; result.add（curr.val）; if（curr.right！= null）{stack.push（curr.right）; } if（curr.left！= null）{stack.push（curr.left）; }} return result; }}
2。オーダートラバーサル
簡単に言えば、ミドルオーバートラバーサルは、最初に左の子供にアクセスし、次に親ノードにアクセスし、最後に右の子供にアクセスすることです。つまり、左の順序で、親、および右に移動します。
以下に示すように、再帰コードも簡単です。
パブリッククラスソリューション{public list <integer> inordertraversal（treeNode root）{list <integer> result = new arraylist <integer>（）;再発（root、result）;返品結果; } private void recurse（treenode root、list <integer> result）{if（root == null）return;再発（root.left、result）; result.add（root.val）;再発（root.right、result）; }}上記の執筆方法は、予約注文トラバーサルの再帰コードとは異なります。メンバー変数を使用して、トラバーサルの結果を予約注文トラバーサルに保存します。ここでは、メソッドパラメーターを使用してトラバーサルの結果を保存します。どちらの執筆方法も大丈夫です。好きなものは何でも使用します。
中期トラバーサルの反復実装は、予約注文トラバーサルほど単純ではありません。スタックも必要ですが、反復終了の条件は異なります。バイナリツリーの場合、最初にアクセスするノードが左端のノードであると想像してください。もちろん、しばらくループを通して左端のノードに到達することができますが、後退すると、ノードの左の子がアクセスされているかどうかをどのようにして知ることができますか？ Curr変数を使用して、現在アクセスされているノードを記録します。サブツリーの右ノードにアクセスしたら、サブツリーの親ノードに戻る必要があります。現時点では、Currはnullなので、これを使用して、ノードの左サブツリーにアクセスされているかどうかを区別できます。コードは次のとおりです。
パブリッククラスソリューション{public list <integer> inordertraversal（treeNode root）{list <integer> result = new arraylist <integer>（）; stack <treenode> stack = new stack <treenode>（）; treenode curr = root; while（curr！= null ||！stack.isempty（））{while（curr！= null）{stack.push（curr）; Curr = Curr.Left; } curr = stack.pop（）; result.add（curr.val）; curr = curr.right; } return result; }}
3。順序のトラバーサル
簡単に言えば、ポストオーバートラバーサルは、最初に左の子供にアクセスし、右の子供にアクセスし、最後に親ノード、つまり左、右、親の順に横断することです。
ミドルオーダートラバーサルを模倣することにより、ポストオーバートラバーサルの再帰的実装を簡単に書き込むことができます。
パブリッククラスソリューション{public list <integer> postordertraversal（treeNode root）{list <integer> result = new ArrayList <Integer>（）;再発（root、result）;返品結果; } private void recurse（treenode root、list <integer> result）{if（root == null）return;再発（root.left、result）;再発（root.right、result）; result.add（root.val）; }}ポストオーバートラバーサルの反復には、ノードの左と右の子供がアクセスされたかどうかを区別するための識別が必要です。そうでない場合、左と右の子供に順番にアクセスされます。アクセスした場合、ノードにアクセスします。この目的のために、プリ変数を使用して、アクセスしたノードを表します。訪問したノードが現在のノードの左または右の子である場合、現在のノードの左と右の子供がアクセスし、ノードにアクセスできることを意味します。それ以外の場合は、左右の子供を入力して順番にアクセスする必要があります。コードは次のとおりです。
パブリッククラスソリューション{public list <integer> postorderTraversal（treeNode root）{list <integer> result = new linkedlist <integer>（）; stack <treenode> stack = new stack <treenode>（）; if（root！= null）stack.push（root）; treenode pre = root; while（！stack.isempty（））{treenode curr = stack.peek（）; if（curr.left == pre || curr.right == pre ||（curr.left == null && curr.right == null））{result.add（curr.val）; stack.pop（）; pre = curr; } else {if（curr.right！= null）stack.push（curr.right）; if（curr.left！= null）stack.push（curr.left）; }} return result; }}郵便局面トラバーサルの反復に関する別の比較的単純な実装があります。予約注文トラバーサルの順序は親、左、右であることがわかっていますが、ポストオーダートラバーサルの順序は左、右、親です。したがって、予約注文のトラバーサルをわずかに変更し、親の順序、右、左に変更すると、それはポストオーダートラバーサルの順序の正反対です。この順序でアクセスした後、最後にアクセス結果を反転させることができます。予約注文トラバーサルの反復実装は比較的簡単です。上記の執筆方法によると、次のように実装できます。
パブリッククラスソリューション{public list <integer> postorderTraversal（treeNode root）{list <integer> result = new linkedlist <integer>（）; stack <treenode> stack = new stack <treenode>（）; if（root！= null）stack.push（root）; while（！stack.isempty（））{treenode curr = stack.pop（）; result.add（curr.val）; if（curr.left！= null）stack.push（curr.left）; if（curr.right！= null）stack.push（curr.right）; } collections.Reverse（result）;返品結果; }}
4。概要
3つのトラバーサルすべての再帰的実装は簡単です。予約注文トラバーサルの反復実装を記述するのが最善であり、1つのスタックのみが必要です。中期のトラバーサルが最も困難です。スタックが空であるかどうかを判断することに加えて、ループ条件は、左サブツリーが横断されているかどうかを示すために、現在のノードが空であるかどうかを判断する必要があります。後続のトラバーサルの反復が予約注文トラバーサル反復に変換される場合、それははるかに簡単です。それ以外の場合は、以前のアクセスノードを記録して、現在のノードの左と右のサブツリーがアクセスされているかどうかを示す必要があります。