赤と黒の木は、バイナリバランスの取れたルックアップツリーです。各ノードには、ノードの色を表すためのストレージビットがあり、これは赤または黒です。
赤と黒の木には次の特性があります。
（1）各ノードは赤または黒です
（2）ルートノードは黒です
（3）ノードが赤い場合、その2人の息子は黒人です
（4）各ノードについて、そのノードからその子孫へのすべてのパスには、同じ数の黒いノードが含まれています。
赤黒樹のプロパティを通じて、すべての赤黒樹のツリーベースの実装により、操作の実行時間が対数的であることが保証されています（範囲ルックアップを除く。
JavaのTreemapは、赤と黒の木を通して実装されています。
絵を描かないと、混乱するのは簡単です。以下は、赤と黒の木の挿入操作を示す図です。
赤いノードを赤と黒の木に挿入した後、6つの状況があります。nは挿入されたノードを表し、pは親ノードを表し、uは叔父ノードを表し、gは祖父ノードを表し、xは現在の操作ノードを表します
コードは次のとおりです。
パブリッククラスredblackbst <key extends carpleable <key>、value> {private node root;プライベート静的ファイナルブールレッド= true;プライベート静的ファイナルブールブラック= false;プライベートクラスノード{プライベートキーキー。 //キープライベートバリューバル。 //左、右、親の値のプライベートノード。 //左および左の子供の木と親ノードプライベートブールカラー。 //親ノードパブリックノード（キーキー、値val、ノード親、ブールカラー）を指すリンクの色{this.key = key; this.val = val; this.color = color; }} public value get（key key）{node x = root; while（x！= null）{int cmp = key.compareto（x.key）; if（cmp <0）x = x.Left; else if（cmp> 0）x = x.right;それ以外の場合はx.valを返します。 } nullを返します。 } public void put（key key、value val）{if（root == null）{//ルートノードの場合、ブラックルート= newノード（key、val、null、black）としてノードを作成します。戻る; } //適切な挿入位置node parent = nullを見つけます。ノードcur = root; while（cur！= null）{parent = cur; if（key.compareto（cur.key）> 0）cur = cur.right; else cur = cur.Left; } node n = new Node（key、val、parent、red）; // ordノーマル新しいノードは赤//親の下に新しいノードを挿入if（key.comPareto（parent.key）> 0）parent.right = n; else parent.left = n; //新しいノードを挿入した後、木のいくつかのノードの色とプロパティを調整して、赤と黒の木の特徴が破壊されないようにする必要があります。 fixafterinsertion（n）; } private node parentof（node x）{return（x == null？null：x.parent）; } private boolean colorof（node x）{return（x == null？null：x.right）; }プライベートノードLeftof（ノードx）{return（x == null？null：x.right）; }プライベートノードrightof（node x）{return（x == null？null：x.right）; } private void setcolor（ノードX、ブールカラー）{if（x！= null）x.color = color; } private void fixafterinsertion（node x）{while（x！= null && colorof（parentof（x））== red）{node grandpa = parentof（parentof（x））; node parent = parentof（x）; if（parent == leftof（grandpa））{//ケース1 || case2 || case3 node uncle = rightof（grandpa）; if（colorof（uncle）== red）{// case1、叔父は赤いセットカラー（親、黒）です。 //親ノードはブラックセットコラー（叔父、黒）です。 //叔父ノードは黒いセットカラー（おじいちゃん、赤）です。 //祖父ノードは赤x =おじいちゃんです。 //祖父ノードは黒から赤に赤いため、親ノードとその祖先の赤と黒の属性を再調整する必要があります} elles {// case2 || case3、叔父は黒ですif（x == rightof（parent））{// case2 x = parent; Rotateleft（x）; } // case3 setColor（親、黒）; setcolor（おじいちゃん、赤）; rotateright（おじいちゃん）; }} else {// case4 ||ケース5 || case6ノードuncle = leftof（grandpa）; if（colorof（uncle）== red）{// case4 || case5 || case6 setcolor（親、黒）; setcolor（叔父、黒）; setcolor（おじいちゃん、赤）; x =おじいちゃん; } else {// case5 || case6、叔父は黒ですif（x == leftof（parent））{// case5 x = parent; rotateright（x）; } // case6 setColor（親、黒）; setcolor（おじいちゃん、赤）; Rotateleft（おじいちゃん）; }}}} private void rotateleft（node x）{if（x == null）return;ノードy = x.right; x.right = y.left; if（y.left！= null）y.left.parent = x; Y.Left = X; Y.Parent = X.Parent; if（x.parent == null）{root = y; } else if（x.parent.left == x）{x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } private void erotateright（node x）{if（x == null）return;ノードy = x.Left; X.Left = Y.Right; if（y.right！= null）y.right.parent = x; Y.Right = X; Y.Parent = X.Parent; if（x.parent == null）{root = y; } else if（x.parent.left == x）{x.parent.left = y; } else {x.parent.right = y; } x.parent = y; }}上記の回転式と回転式の図を描く必要があります。
上記の記事は、私があなたと共有するすべてのコンテンツである赤と黒の木の挿入操作とJava実装方法（共有）の原理に基づいています。参照を提供できることを願っています。wulin.comをもっとサポートできることを願っています。