精品久久亚洲人妻视频,日韩一二三四区中文,亚洲av精晨一区二区

本文作者：黃海燕，叩丁狼高級(jí)講師。原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處。

前言

之前很多小伙伴問我怎么看源代碼,還有就是越來越多的程序員都想要看源代碼,搞懂底層原理,但是感覺源代碼非常的晦澀難懂,不夠直接和清晰,所以我希望這篇文章能夠快速帶同學(xué)們看懂java源碼,更加深入的學(xué)習(xí)java,幫助小伙伴們節(jié)約學(xué)習(xí)的時(shí)間成本.

1.樹的介紹

什么是樹結(jié)構(gòu)?其實(shí)就是一個(gè)節(jié)點(diǎn)下面有多個(gè)子節(jié)點(diǎn),我們稱之為樹結(jié)構(gòu),如下圖:
普通節(jié)點(diǎn)：擁有子節(jié)點(diǎn)的節(jié)點(diǎn)。
葉子節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

樹結(jié)構(gòu)

什么是二叉樹?

二叉樹就是一個(gè)節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn),分為左節(jié)點(diǎn)和右節(jié)點(diǎn),如下圖:

二叉樹結(jié)構(gòu)

什么是排序二叉樹?

若左子樹不為空，則左子樹所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值。
若右子樹不為空，則右子樹所有節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值。
如圖:

排序二叉樹.png

什么是紅黑樹?
紅黑樹其實(shí)是一個(gè)平衡排序二叉樹,屬于查詢高效的樹結(jié)構(gòu).請(qǐng)看下圖:

普通排序二叉樹vs紅黑樹

查詢?cè)?普通的二叉樹需要操作6次,紅黑樹只需要操作4次,所以紅黑樹查詢更加高效.

1.TreeMap的結(jié)構(gòu)介紹

1.1 結(jié)構(gòu)關(guān)系

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{

繼承關(guān)系:

父類AbstractMap,讓子類擁有基本Map的方法,比如增(put)刪(remove)查(get)等方法.

實(shí)現(xiàn)關(guān)系:

NavigableMap:父接口為SortedMap,所以NavigableMap為可排序接口,表示TreeMap但是一個(gè)排序的Map:
Cloneable:標(biāo)記型的接口，內(nèi)部都沒有方法和屬性，實(shí)現(xiàn) Cloneable來表示該對(duì)象能被克隆，能使用Object.clone()方法。如果沒有實(shí)現(xiàn) Cloneable的類對(duì)象調(diào)用clone()就會(huì)拋出CloneNotSupportedException。
Serializable:標(biāo)記型的接口，內(nèi)部都沒有方法和屬性，實(shí)現(xiàn)Serializable表示可進(jìn)行序列化和反序列化,表示能夠使用在ObjectOutputStream.writeObject())和ObjectInputStream.readObject()

1.2 基本成員組成

   /**
     * 比較器:類似于一個(gè)"裁判",用于比較插入對(duì)象和樹節(jié)點(diǎn)的內(nèi)容大小
     * 因?yàn)門reeMap是一個(gè)紅黑樹,紅黑樹是一個(gè)排序二叉樹,插入元素的時(shí)候需要進(jìn)行排序,排序可以使用比較器中的方式排序
     */
    private final Comparator<? super K> comparator;
    /**
     *  根節(jié)點(diǎn)
     */
    private transient Entry<K,V> root;
    /**
     * 樹的元素個(gè)數(shù)
     */
    private transient int size = 0;
    /**
     * 操作次數(shù):增加和刪除操作數(shù)都會(huì)加1,用于控制并發(fā)修改異常
     */
    private transient int modCount = 0;

通過root根節(jié)點(diǎn)可以看出一個(gè)節(jié)點(diǎn)(元素)就是一個(gè)Entry對(duì)象,所以一個(gè)節(jié)點(diǎn)(元素)中包含多個(gè)數(shù)據(jù).結(jié)構(gòu)如下:

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;//鍵
        V value;//值
        Entry<K,V> left;//左節(jié)點(diǎn)
        Entry<K,V> right;//右節(jié)點(diǎn)
        Entry<K,V> parent;//父節(jié)點(diǎn)
        boolean color = BLACK;//顏色

節(jié)點(diǎn)表示如下:

樹節(jié)點(diǎn)

1.3添加操作:

public V put(K key, V value) {
        Entry<K, V> t = root;//和插入節(jié)點(diǎn)進(jìn)行比較的樹節(jié)點(diǎn)
        //根節(jié)點(diǎn)為空
        if (t == null) {
            compare(key, key); //key比key,自己比較自己,目的是想要檢查類型,確保傳入了比較器或者是key實(shí)現(xiàn)了可比較接口
            //創(chuàng)建了一個(gè)沒有父節(jié)點(diǎn)的新的節(jié)點(diǎn),作為根節(jié)點(diǎn)
            root = new Entry<>(key, value, null);
            size = 1;//元素個(gè)數(shù)為1
            modCount++;//操作數(shù)+1
            return null;//返回空,根節(jié)點(diǎn)添加結(jié)束
        }
        int cmp;//表示比較結(jié)果
        Entry<K, V> parent;
        // cpr臨時(shí)表示比較器
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {//比較器不為空,就使用比較器比較元素
            do {
                parent = t;//父節(jié)點(diǎn)為t
                cmp = cpr.compare(key, t.key);//通過比較器對(duì)key和樹節(jié)點(diǎn)比較得到比較結(jié)果
                if (cmp < 0)//比較結(jié)果小于0,表示插入的元素比樹節(jié)點(diǎn)小
                    t = t.left;//t往左走
                else if (cmp > 0)//比較結(jié)果大于0,表示插入的元素比樹節(jié)點(diǎn)大
                    t = t.right;//t往右走
                else//cmp比較結(jié)果為0,覆蓋節(jié)點(diǎn)中的value
                    return t.setValue(value);
            } while (t != null);//直到t為空停下來,保證插入的是節(jié)點(diǎn)
        } else {//比較器為空就使用元素中的比較方法
            if (key == null)//插入的元素key為空,沒辦法和樹結(jié)構(gòu)中的元素比較,拋出空指針異常
                throw new NullPointerException();
            /*
             *  key進(jìn)行強(qiáng)轉(zhuǎn),看一下key是否實(shí)現(xiàn)了Comparable接口,是否存在compareTo方法,
             *  如果沒有實(shí)現(xiàn)接口,也就不確定有沒有compareTo方法了,沒辦法進(jìn)行比較了
             */
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;//父節(jié)點(diǎn)為t
                cmp = k.compareTo(t.key);//通過節(jié)點(diǎn)中的比較方法比較插入節(jié)點(diǎn)和樹節(jié)點(diǎn)的大小
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);//直到?jīng)]有節(jié)點(diǎn)可以比較
        }
        Entry<K, V> e = new Entry<>(key, value, parent);
        if (cmp < 0)//如果比較結(jié)果小于0插入左邊
            parent.left = e;
        else
            parent.right = e;//否則插入右邊
        fixAfterInsertion(e);//對(duì)樹進(jìn)行自平衡
        size++;
        modCount++;
        return null;
    }

1.4 元素插入后對(duì)樹進(jìn)行自平衡

紅黑樹的自平衡規(guī)則:(目標(biāo)就是黑色節(jié)點(diǎn)平衡)

每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色

根節(jié)點(diǎn)是黑色

每個(gè)葉節(jié)點(diǎn)（空節(jié)點(diǎn)）是黑色的。

如果一個(gè)結(jié)點(diǎn)是紅的，則它兩個(gè)子節(jié)點(diǎn)都是黑的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。

從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

    private void fixAfterInsertion(Entry<K, V> x) {//x表示插入的節(jié)點(diǎn),
        x.color = RED;//設(shè)置插入的節(jié)點(diǎn)為紅色
        //當(dāng)x不為空,x不為根節(jié)點(diǎn),x的父節(jié)點(diǎn)為紅色就需要進(jìn)行平衡
        while (x != null && x != root && x.parent.color == RED) {
            //x的父節(jié)點(diǎn)等于x的爺爺節(jié)點(diǎn)的左邊,其實(shí)就是說x的父節(jié)點(diǎn)是否屬于左節(jié)點(diǎn)
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                //獲取x的爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)
                Entry<K, V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {//爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)為紅色
                    setColor(parentOf(x), BLACK);//將x的父節(jié)點(diǎn)設(shè)置為黑色
                    setColor(y, BLACK);//x父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)設(shè)置為黑色
                    setColor(parentOf(parentOf(x)), RED);//爺爺節(jié)點(diǎn)設(shè)置為紅色
                    x = parentOf(parentOf(x));//x指向原來的爺爺節(jié)點(diǎn),目的是為了繼續(xù)往上修改顏色
                } else {//不為紅色,也就是子節(jié)點(diǎn)和父節(jié)點(diǎn)的顏色出現(xiàn)沖突
                    //如果x等于父節(jié)點(diǎn)的右節(jié)點(diǎn)
                    if (x == rightOf(parentOf(x))) {
                        //操作的x為x的父節(jié)點(diǎn)
                        x = parentOf(x);
                        //左自旋,旋轉(zhuǎn)后x為原來x的子節(jié)點(diǎn)
                        rotateLeft(x);
                    }
                    //x的父節(jié)點(diǎn)設(shè)置為黑色
                    setColor(parentOf(x), BLACK);
                    //x的爺爺節(jié)點(diǎn)設(shè)置為紅色
                    setColor(parentOf(parentOf(x)), RED);
                    //右自旋
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                //y為爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)(父節(jié)點(diǎn)的兄弟節(jié)點(diǎn))
                Entry<K, V> y = leftOf(parentOf(parentOf(x)));
                //如果y的顏色為紅色
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);//父節(jié)點(diǎn)設(shè)置為黑色
                    setColor(y, BLACK);//y設(shè)置為黑色
                    setColor(parentOf(parentOf(x)), RED);//爺爺節(jié)點(diǎn)設(shè)置為紅色
                    x = parentOf(parentOf(x));//x指向原來的爺爺節(jié)點(diǎn),目的是為了繼續(xù)往上修改顏色
                } else {
                    //如果父節(jié)點(diǎn)的左節(jié)點(diǎn)為x
                    if (x == leftOf(parentOf(x))) {
                        //x為父節(jié)點(diǎn)
                        x = parentOf(x);
                        //右自旋,旋轉(zhuǎn)后x為原來x的子節(jié)點(diǎn)
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);//父節(jié)點(diǎn)設(shè)置為黑色
                    setColor(parentOf(parentOf(x)), RED);//爺爺節(jié)點(diǎn)設(shè)置為紅色
                    rotateLeft(parentOf(parentOf(x)));//左自旋
                }
            }
        }
        root.color = BLACK;//保證根節(jié)點(diǎn)必須為黑色
    }

1.5左自旋

    private void rotateLeft(Entry<K, V> p) {
        //p不為空
        if (p != null) {
            //r表示p的右節(jié)點(diǎn)
            Entry<K, V> r = p.right;
            //將r的左節(jié)點(diǎn) 賦值給 p的有右節(jié)點(diǎn)
            p.right = r.left;
            //如果r的左節(jié)點(diǎn)不為空
            if (r.left != null)
                //r的左節(jié)點(diǎn)的父節(jié)點(diǎn)為p
                r.left.parent = p;
            //r的父節(jié)點(diǎn)為p的父節(jié)點(diǎn)
            r.parent = p.parent;
            //如果p的父節(jié)點(diǎn)為空
            if (p.parent == null)
                //r作為根節(jié)點(diǎn)
                root = r;
            //如果p的父節(jié)點(diǎn)的左節(jié)點(diǎn)等于p,說明p為父節(jié)點(diǎn)的左節(jié)點(diǎn)
            else if (p.parent.left == p)
                //p的父節(jié)點(diǎn)的左節(jié)點(diǎn)為r
                p.parent.left = r;
            else
                //p的父節(jié)點(diǎn)的左節(jié)點(diǎn)為r
                p.parent.right = r;
            //r的左節(jié)點(diǎn)為p
            r.left = p;
            //p的父節(jié)點(diǎn)為r
            p.parent = r;
        }
    }

1.6右自旋

 private void rotateRight(Entry<K, V> p) {
        //p不為空
        if (p != null) {
            //l表示p的左節(jié)點(diǎn)
            Entry<K, V> l = p.left;
            //p的左節(jié)點(diǎn)指向l的右節(jié)點(diǎn)
            p.left = l.right;
            //如果l的右節(jié)點(diǎn)不為空
            if (l.right != null)
                //l的右節(jié)點(diǎn)的父節(jié)點(diǎn)為p
                l.right.parent = p;
            //l的父節(jié)點(diǎn)指向p的父節(jié)點(diǎn)
            l.parent = p.parent;
            //如果p的父節(jié)點(diǎn)為空
            if (p.parent == null)
                //l為根節(jié)點(diǎn)
                root = l;
            //如果p的父節(jié)點(diǎn)的右節(jié)點(diǎn)為p
            else if (p.parent.right == p)
                //p的父節(jié)點(diǎn)的右節(jié)點(diǎn)為l
                p.parent.right = l;
            else
                //p的父節(jié)點(diǎn)的左節(jié)點(diǎn)為l
                p.parent.left = l;
            //l的右節(jié)點(diǎn)指向p
            l.right = p;
            //p的父節(jié)點(diǎn)指向l
            p.parent = l;
        }
    }