TreeMap実装

TreeMapは赤と黒の二叉木を用いて実現した.
赤と黒のツリー:
a.ルートノードは黒い;
b.赤いノードの息子ノードは黒い.
c.いずれかのノードから空のノードへのすべての経路に同じデータを含む黒いノード.
d.リーフノードのサブノードが黒いノード
1本の赤黒い木の黒いノードの個数をRと仮定すると、この木の最短高さはRであり、最大長さは2 Rである.
したがってh<2 R,Rの最大値はlog(n+1)であるため,赤黒樹の高さ<2 log(n+1)は挿入を先に見る.
最初のステップでは、赤と黒の二叉ソートツリーに新しいノードの位置を見つけて挿入します.

  int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;

上記のコードは多く分析する必要はありません.new TreeMapの場合、具体的なComparatorを指定したり、システムのデフォルトのComparableインタフェースを使用したりして、keyに従ってルートノードから探して、具体的に挿入できるインタフェースまで、挿入すればいいです.
2つ目のステップは、ツリーにノードが追加されたため、赤と黒のバランスが影響を受ける場合は、次のように調整する必要があります.
新しく挿入されたノードはまず赤で表示され、その挿入されたノードがルートノードではなく、新しいノードの親ノードが黒であれば、ノードを新しく追加した後、上記abcd 4点に違反することなく、赤と黒の2叉ソートツリーはこれ以上調整する必要はありません.したがって、新しい挿入ノードがrootノードでない場合、または対応する親ノードが赤いノードである場合にのみ、再調整が必要です.

    while (x != null && x != root && x.parent.color == RED) 

新しいノードXに対応する親ノードが左の子ノードである場合、以下の調整が行われる.
新しいノードの親ノードの兄弟ノードyを取得し、兄弟ノードが赤である場合、xとyを黒、xの親ノードとその兄弟ノードyに対応する親ノードを赤とマークします.この場合、親ノードの親ノードも赤である可能性があるため、親ノードをxに割り当て、xを上に調整する必要があります.

Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                }

それ以外の場合、兄弟ノードyが黒い場合:
このときxが左ノードの場合、x親ノードを黒、x親ノードの親ノードを赤、x親ノードの親ノードを右に回すとよい.すなわち、x親ノードの親ノード極小ノードをx親ノードの右サブツリー、xが右ノードの場合、x対応する親ノードをxの左サブに、このときの問題はxが左ノードであるのと同じであるが,このときのxはすでにxの親ノードであるだけで,そのコードは以下の通りである.

 else {
                    if (x == rightOf(parentOf(x))) {//  x      ，   x         x    
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);//x        
                    setColor(parentOf(parentOf(x)), RED);//x            
                    rotateRight(parentOf(parentOf(x)));//x           x       
                }

新しいノードxに対応する親ノードが右子ノードである場合、その調整規則は上記と同様であり、ここでは説明を省略する.詳細コードを参照:

else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }

右回転のコードは以下の通りです.

 private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

効果は、現在のノードをそのサブノードの右ノードに設定し、サブノードノードの元の右ノードを現在のノードの左サブノードに設定することです.
左回転の効果は、現在のノードを右サブノードの左ノードに設定し、右サブノードの元の左サブノードを現在のノードの右サブノードに設定します.コードは次のとおりです.

 private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

TreeMap削除要素:
新しい要素と同様に、削除要素はツリーのバランスを破壊する可能性があります.そのため、調整が必要になる可能性があります.検索プロセスは言わないで、削除時にどのように調整してバランスを維持するかを見てみましょう.
現在削除対象ノードに2つの子ノードがある場合、その後継ノードを検索し、その内容を後継ノードの内容に変換するだけで、問題は後継ノードを削除する問題に移行する.ここでは、現在のノードの右サブツリーで最も小さいノードを見つける代わりに、

  Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;

これにより、2つの子供ノードがあるノードを削除する問題は、1つのサブノードを削除するか、リーフノードを削除する問題に変換されます.次のコードは次のとおりです.

  // Start fixup at replacement node, if it exists.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);

ここのpが上記の後継ノードである場合、このときpに左の子供がいるはずがないため、代替者はp.rightであり、この場合nullであるか、削除されたノードのサブノードが2つ未満である場合、p.leftであるか、p.rightである可能性がある.nullでない場合は、現在のノードを削除するためにpのparentノードに後続ノードを指定します.

replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

この時点でpは削除され、pが赤色であれば赤黒ツリーには影響しないが、削除されたノードが黒色であれば、この時点で黒色ノードが1つ削除されたため、元のツリーを調整する必要がある:

   while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {//  x     
                Entry<K,V> sib = rightOf(parentOf(x));

                if (colorOf(sib) == RED) {//          
                    setColor(sib, BLACK);//        
                    setColor(parentOf(x), RED);//        
                    rotateLeft(parentOf(x));//     
                    sib = rightOf(parentOf(x));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {//               
                    setColor(sib, RED);//         
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } 
        setColor(x, BLACK);

また、replacement値が空の場合は、削除されたノードにサブノードがないことを示し、黒のノードであれば調整して削除する必要があり、そうでなければ直接削除すればよい

 if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }

TreeMapの検索アルゴリズムは簡単なので、ここでは説明しません.さらに、TreeMapの特別な用途は、データの区間範囲クエリーを実現することです.