這篇文章給大家分享的是有關(guān)如何實現(xiàn)TreeMap的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序定制開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了荊門免費(fèi)建站歡迎大家使用！

/**

• The comparator used to maintain order in this tree map, or

• null if it uses the natural ordering of its keys.

• @serial
  */
  //自然排序
  private final Comparator comparator;
  //根節(jié)點
  private transient Entry root;

  /**

• The number of entries in the tree
  */
  //大小
  private transient int size = 0;

public TreeMap() {
comparator = null;
}

public V put(K key, V value) {
Entry t = root;//紅黑樹的根節(jié)點
if (t == null) {
compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);//構(gòu)造根節(jié)點，root沒有父節(jié)點，傳入null
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry parent;  //定義節(jié)點
    // split comparator and comparable paths
    Comparator cpr = comparator; //獲得比較器
    if (cpr != null) {//定義了比較器，采用自定義比較器進(jìn)行比較
        do {
            parent = t;//將紅黑樹根節(jié)點賦值給parent
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;//指向左子節(jié)點
            else if (cmp > 0)
                t = t.right;//指向右子節(jié)點
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        //自然排序，沒有指定比較器
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable k = (Comparable) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;//左子節(jié)點
            else if (cmp > 0)
                t = t.right;//右子節(jié)點
            else
                return t.setValue(value);
        } while (t != null);
    }
    //創(chuàng)建新節(jié)點，并指定父點
    Entry e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    //新插入節(jié)點后重新調(diào)整紅黑樹
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

/** From CLR */
private void fixAfterInsertion(Entry x) {
    //加入的節(jié)點默認(rèn)的顏色是紅色
    x.color = RED;
    //情形1：新節(jié)點x是樹的根節(jié)點，沒有父節(jié)點不需要任何操作
    //情形2：新節(jié)點x的父節(jié)點顏色是黑色的，不需要操作
    while (x != null && x != root && x.parent.color == RED) {
        //情形3：新節(jié)點的父節(jié)點顏色是紅色的
        //判斷x的節(jié)點的父節(jié)點位置，是否屬于左子節(jié)點
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            //獲取x節(jié)點的父節(jié)點的兄弟節(jié)點，上面語句已經(jīng)判斷出x節(jié)點的父節(jié)點為左子節(jié)點，所以直接取右子節(jié)點
            Entry y = rightOf(parentOf(parentOf(x)));
            //判斷是否x節(jié)點的父節(jié)點的兄弟節(jié)點為紅色
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);//x節(jié)點的父節(jié)點設(shè)置為黑色
                setColor(y, BLACK);//y節(jié)點的顏色設(shè)置為黑色
                setColor(parentOf(parentOf(x)), RED);//x的父節(jié)點的父節(jié)點設(shè)置為紅色
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry 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)));
            }
        }
    }
    root.color = BLACK;
}

感謝各位的閱讀！關(guān)于“如何實現(xiàn)TreeMap”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！