您的位置：首頁(yè) > 軟件教程 > 教程 > TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

來源：好特整理　|　時(shí)間：2024-09-12 09:55:20 |　閱讀：113　|　標(biāo)簽： a T 黑平衡　 |　分享到：

下載游戲

介紹 TreeSet和TreeMap在Java里有著相同的實(shí)現(xiàn)，前者僅僅是對(duì)后者做了一層包裝，也就是說TreeSet里面有一個(gè)TreeMap(適配器模式)。 Java TreeMap實(shí)現(xiàn)了SortedMap接口，也就是說會(huì)按照key的大小順序?qū)ap中的元素進(jìn)行排序，key大小的評(píng)判可以通過其本身的

介紹

TreeSet 和 TreeMap 在Java里有著相同的實(shí)現(xiàn)，前者僅僅是對(duì)后者做了一層包裝，也就是說 TreeSet里面有一個(gè)TreeMap (適配器模式)。

Java TreeMap 實(shí)現(xiàn)了 SortedMap 接口，也就是說會(huì)按照key的大小順序?qū)? Map 中的元素進(jìn)行排序，key大小的評(píng)判可以通過其本身的自然順序(natural ordering)，也可以通過構(gòu)造時(shí)傳入的比較器(Comparator)。

TreeMap底層通過紅黑樹(Red-Black tree)實(shí)現(xiàn) ，也就意味著containsKey(), get(), put(), remove()都有著log(n)的時(shí)間復(fù)雜度。

TreeMap存儲(chǔ) Key-Value 對(duì)時(shí)，需要根據(jù) key-value 對(duì)進(jìn)行排序。TreeMap 可以保證所有的 Key-Value 對(duì)處于有序狀態(tài)。
- 正常情況下TreeMap是不能存入值為null的鍵的。
- 但通過自定義比較器能讓TreeMap存入一個(gè)值為null的鍵。
- 存入的值為null鍵對(duì)應(yīng)的值不能通過通過它來獲取，只能通過直接遍歷Values。
TreeSet底層使用紅黑樹結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)
TreeMap 的 Key 的排序：
- 自然排序：TreeMap 的所有的 Key 必須實(shí)現(xiàn) Comparable 接口，而且所有的 Key 應(yīng)該是同一個(gè)類的對(duì)象，否則將會(huì)拋出 ClasssCastException
- 定制排序：創(chuàng)建 TreeMap 時(shí)，傳入一個(gè) Comparator 對(duì)象，該對(duì)象負(fù)責(zé)對(duì)TreeMap 中的所有 key 進(jìn)行排序。此時(shí)不需要 Map 的 Key 實(shí)現(xiàn)Comparable 接口
TreeMap判斷兩個(gè)key 相等的標(biāo)準(zhǔn)：兩個(gè)key通過compareTo()方法或者compare()方法返回0。

底層實(shí)現(xiàn)

繼承接口的關(guān)鍵方法

public class TreeMap
    extends AbstractMap
    implements NavigableMap, Cloneable, java.io.Serializable

返回用于排序此映射中的鍵的比較器，如果此映射使用其鍵的自然排序，則返回null。

SortedMap接口：

Comparator comparator()
返回用于排序此映射中的鍵的比較器，如果此映射使用其鍵的自然排序，則返回null。

Set> entrySet()
返回此映射中包含的映射的Set視圖。

K firstKey()
返回當(dāng)前映射中的第一個(gè)(最低)鍵。

K lastKey()
返回當(dāng)前映射中的最后(最高)鍵。

NavigableMap接口：

Map.Entry ceilingEntry(K key)
返回與大于或等于給定鍵的最小鍵相關(guān)聯(lián)的鍵值映射，如果沒有這樣的鍵則返回null。

K ceilingKey(K key)
返回大于或等于給定鍵的最小鍵，如果沒有這樣的鍵，則返回null。

NavigableMap descendingMap()
返回此映射中包含的映射的倒序視圖。

Map.Entry firstEntry()
返回與該映射中最小的鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

Map.Entry floorEntry(K key)
返回與小于或等于給定鍵的最大鍵相關(guān)聯(lián)的鍵值映射，如果沒有這樣的鍵則返回null。

SortedMap headMap(K toKey)
返回該映射中鍵嚴(yán)格小于toKey的部分的視圖。

Map.Entry higherEntry(K key)
返回與嚴(yán)格大于給定鍵的最小鍵關(guān)聯(lián)的鍵值映射，如果沒有這樣的鍵，則返回null。

Map.Entry lastEntry()
返回與此映射中最大鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

Map.Entry lowerEntry(K key)
返回與嚴(yán)格小于給定鍵的最大鍵關(guān)聯(lián)的鍵值映射，如果沒有這樣的鍵，則返回null。

Map.Entry pollFirstEntry()
刪除并返回與該映射中最小的鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

Map.Entry pollLastEntry()
刪除并返回與此映射中最大鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

SortedMap subMap(K fromKey, K toKey)
返回該映射中鍵范圍從fromKey(包含)到toKey(獨(dú)占)的部分的視圖。

SortedMap tailMap(K fromKey)
返回該映射中鍵大于或等于fromKey的部分的視圖。

初始屬性

//比較器
private final Comparator comparator;

//root根的值
private transient Entry root;

//map中數(shù)據(jù)量
private transient int size = 0;

//修改次數(shù)
private transient int modCount = 0;

構(gòu)造方法

public TreeMap() {
    comparator = null;
}

//有參構(gòu)造，可以重新定義比較器
public TreeMap(Comparator comparator) {
    this.comparator = comparator;
}

//有參構(gòu)造，將其他map用TreeMap存儲(chǔ)
public TreeMap(Map m) {
    comparator = null;
    putAll(m);
}

put 方法

public V put(K key, V value) {
    //將root賦值給局部變量
    Entry t = root;
    if (t == null) {//初始操作
        //檢查key是否為空
        compare(key, key); // type (and possibly null) check
        //將要添加的key value封裝為一個(gè)entry對(duì)象，并賦值給root
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry parent;//父節(jié)點(diǎn)
    // split comparator and comparable paths
    Comparator cpr = comparator;//獲取比較器
    if (cpr != null) {
        do {
            parent = t;//將root賦值給了parent
            cmp = cpr.compare(key, t.key);//和root節(jié)點(diǎn)比較大小
            if (cmp < 0)//key比根節(jié)點(diǎn)更小，t就使其為左節(jié)點(diǎn)
                t = t.left;
            else if (cmp > 0)//否則使其為右節(jié)點(diǎn)
                t = t.right;
            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;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 到此 t 就是要插入節(jié)點(diǎn)的父節(jié)點(diǎn)，即parent
    //將 k v 對(duì)封裝成entry對(duì)象
    Entry e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;//插入節(jié)點(diǎn)在 父節(jié)點(diǎn) 的左側(cè)
    else 
        parent.right = e;//插入節(jié)點(diǎn)在 父節(jié)點(diǎn) 的右側(cè)
    fixAfterInsertion(e);//實(shí)現(xiàn)紅黑樹的平衡
    size++;
    modCount++;
    return null;
}

關(guān)于紅黑樹的平衡，將在后文介紹

紅黑樹

紅黑樹的性質(zhì)

每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
根節(jié)點(diǎn)是黑色。
每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。
每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。
任意一結(jié)點(diǎn)(包含本身)到其葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。

紅黑樹的優(yōu)點(diǎn)：

由于在AVL樹中，由于AVL樹是絕對(duì)平衡的，所有在進(jìn)行插入和刪除的時(shí)候，為了維護(hù)其絕對(duì)的平衡性，有時(shí)候進(jìn)行修改節(jié)點(diǎn)的操作，需要進(jìn)行到根節(jié)點(diǎn)，旋轉(zhuǎn)的次數(shù)比較多，所以出現(xiàn)了紅黑樹，當(dāng)數(shù)據(jù)不是靜態(tài)的數(shù)據(jù)而是動(dòng)態(tài)的數(shù)據(jù)，進(jìn)行插入和刪除的時(shí)候就不用去維護(hù)絕對(duì)的平衡，也就減少了旋轉(zhuǎn)的次數(shù)，照樣可以提高效率，并且紅黑樹的平均查找效率還是logn

紅黑樹平衡源碼

插入紅黑樹初始的顏色肯定為紅色，注意: 插入節(jié)點(diǎn)必須為紅色 ，理由很簡(jiǎn)單，紅色在父節(jié)點(diǎn)(如果存在)為黑色節(jié)點(diǎn)時(shí)，紅黑樹的黑色平衡沒被破壞，不需要做自平衡操作。但如果插入結(jié)點(diǎn)是黑色，那么插入位置所在的子樹黑色結(jié)點(diǎn)總是多1，必須做自平衡。

可以先看TreeMap紅黑樹平衡源碼，也可以先看后文情景

private void fixAfterInsertion(Entry x) {
    x.color = RED;//插入時(shí)先把顏色設(shè)置為紅色
    //循環(huán)條件是x不等于空，x不是根，且父節(jié)點(diǎn)為紅色
    //原因在于①x為根的話可以直接置為黑色(對(duì)應(yīng)情景1)；②父節(jié)點(diǎn)若為黑色，x直接以紅色插入，不影響平衡條件(對(duì)應(yīng)情景3)
    while (x != null && x != root && x.parent.color == RED) {
        //判斷父節(jié)點(diǎn)  是否是  祖父節(jié)點(diǎn)的左側(cè)節(jié)點(diǎn)
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            //獲取 祖父節(jié)點(diǎn)的右側(cè)節(jié)點(diǎn)，也就是叔叔節(jié)點(diǎn)S
            Entry y = rightOf(parentOf(parentOf(x)));
            //如果 叔叔節(jié)點(diǎn)為紅色(對(duì)應(yīng)情景4.1) 
            if (colorOf(y) == RED) {
                //1.將P和S設(shè)置為黑色2.將PP設(shè)置為紅色3.將PP設(shè)置為當(dāng)前插入節(jié)點(diǎn)再執(zhí)行規(guī)則
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {//叔叔節(jié)點(diǎn)不存在(對(duì)應(yīng)情景4.2)
              //如果x 是父節(jié)點(diǎn)的右節(jié)點(diǎn)(對(duì)應(yīng)情景4.2.2)
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);//將x的父節(jié)點(diǎn)P作為插入節(jié)點(diǎn)
                    rotateLeft(x);//左旋
                } //左旋完之后 插入節(jié)點(diǎn)x就是P的左節(jié)點(diǎn)
                //如果x是父節(jié)點(diǎn)的左節(jié)點(diǎn)；那就只做一次右旋(對(duì)應(yīng)情景4.2.1)
                setColor(parentOf(x), BLACK);//將P設(shè)置為黑色
                setColor(parentOf(parentOf(x)), RED);//將PP設(shè)置為紅色
                rotateRight(parentOf(parentOf(x)));//右旋
            }
        } else {//父節(jié)點(diǎn) 是  祖父節(jié)點(diǎn)的右側(cè)節(jié)點(diǎn)
            //獲取 祖父節(jié)點(diǎn)的左側(cè)節(jié)點(diǎn)，也就是叔叔節(jié)點(diǎn)S
            Entry y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {//(對(duì)應(yīng)情景4.1) 
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {//(對(duì)應(yīng)情景4.3)
                if (x == leftOf(parentOf(x))) {//(對(duì)應(yīng)情景4.3.2)
                    x = parentOf(x);
                    rotateRight(x);
                }
                //(對(duì)應(yīng)情景4.3.1)
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //根節(jié)點(diǎn)的顏色為黑色
    root.color = BLACK;
}

左旋：以某個(gè)節(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)節(jié)點(diǎn))，其右子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)，右子節(jié)點(diǎn)的左子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的右子節(jié)點(diǎn)，旋轉(zhuǎn)節(jié)點(diǎn)的左子節(jié)點(diǎn)保持不變。右子節(jié)點(diǎn)的左子節(jié)點(diǎn)相當(dāng)于從右子節(jié)點(diǎn)上“斷開”，重新連接到旋轉(zhuǎn)節(jié)點(diǎn)上。

//左旋
private void rotateLeft(Entry p) {
    if (p != null) {
        //
        Entry 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;
    }
}

右旋：以某個(gè)節(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)節(jié)點(diǎn))，其左子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)，左子節(jié)點(diǎn)的右子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的左子節(jié)點(diǎn)，旋轉(zhuǎn)節(jié)點(diǎn)的右子節(jié)點(diǎn)保持不變。左子節(jié)點(diǎn)的右子節(jié)點(diǎn)相當(dāng)于從左子節(jié)點(diǎn)上“斷開”，重新連接到旋轉(zhuǎn)節(jié)點(diǎn)上。

private void rotateRight(Entry p) {
    if (p != null) {
        Entry 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;
    }
}

以下情景中插入的操作轉(zhuǎn)載于： https://www.jianshu.com/p/e136ec79235c

情景1：紅黑樹為空樹

最簡(jiǎn)單的一種情景，直接把插入結(jié)點(diǎn)作為根結(jié)點(diǎn)就行，但注意，根據(jù)紅黑樹性質(zhì)2：根節(jié)點(diǎn)是黑色。還需要把插入結(jié)點(diǎn)設(shè)為黑色。

處理：把插入結(jié)點(diǎn)作為根結(jié)點(diǎn)，并把結(jié)點(diǎn)設(shè)置為黑色。

情景2：插入結(jié)點(diǎn)的Key已存在

插入結(jié)點(diǎn)的Key已存在，既然紅黑樹總保持平衡，在插入前紅黑樹已經(jīng)是平衡的，那么把插入結(jié)點(diǎn)設(shè)置為將要替代結(jié)點(diǎn)的顏色，再把結(jié)點(diǎn)的值更新就完成插入（這里的更新的其實(shí)是相同 key的 value）

處理：

把I設(shè)為當(dāng)前結(jié)點(diǎn)的顏色
更新當(dāng)前結(jié)點(diǎn)的值為插入結(jié)點(diǎn)的值

情景3：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為黑結(jié)點(diǎn)

由于插入的結(jié)點(diǎn)是紅色的，當(dāng)插入結(jié)點(diǎn)的黑色時(shí)，并不會(huì)影響紅黑樹的平衡，直接插入即可，無需做自平衡。

處理：直接插入。

情景4：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅結(jié)點(diǎn)

再次回想下紅黑樹的性質(zhì)2：根結(jié)點(diǎn)是黑色。如果插入的父結(jié)點(diǎn)為紅結(jié)點(diǎn)，那么該父結(jié)點(diǎn)不可能為根結(jié)點(diǎn)，所以插入結(jié)點(diǎn)總是存在祖父結(jié)點(diǎn)。這點(diǎn)很重要，因?yàn)楹罄m(xù)的旋轉(zhuǎn)操作肯定需要祖父結(jié)點(diǎn)的參與。

情景4.1：叔叔結(jié)點(diǎn)存在并且為紅結(jié)點(diǎn)

從紅黑樹性質(zhì)4可以，祖父結(jié)點(diǎn)肯定為黑結(jié)點(diǎn)，因?yàn)椴豢梢酝瑫r(shí)存在兩個(gè)相連的紅結(jié)點(diǎn)。那么此時(shí)該插入子樹的紅黑層數(shù)的情況是：黑紅紅。顯然最簡(jiǎn)單的處理方式是把其改為：紅黑紅。

(以下描述中I為插入節(jié)點(diǎn)，P為父節(jié)點(diǎn)，PP為祖父節(jié)點(diǎn)，S為叔叔節(jié)點(diǎn))

處理：

將P和S設(shè)置為黑色
將PP設(shè)置為紅色
把PP設(shè)置為當(dāng)前插入結(jié)點(diǎn)

TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

把PP結(jié)點(diǎn)設(shè)為紅色了，如果PP的父結(jié)點(diǎn)是黑色，那么無需再做任何處理；但如果PP的父結(jié)點(diǎn)是紅色，根據(jù)性質(zhì)4(每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。)，此時(shí)紅黑樹已不平衡了，所以還需要把PP當(dāng)作新的插入結(jié)點(diǎn)，繼續(xù)做插入操作自平衡處理，直到平衡為止。

試想下PP剛好為根結(jié)點(diǎn)時(shí)，那么根據(jù)性質(zhì)2，必須把PP重新設(shè)為黑色，那么樹的紅黑結(jié)構(gòu)變?yōu)椋汉诤诩t。換句話說，從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中，黑色結(jié)點(diǎn)增加了。這也是唯一一種會(huì)增加紅黑樹黑色結(jié)點(diǎn)層數(shù)的插入情景。

我們還可以總結(jié)出另外一個(gè)經(jīng)驗(yàn)：紅黑樹的生長(zhǎng)是自底向上的。這點(diǎn)不同于普通的二叉查找樹，普通的二叉查找樹的生長(zhǎng)是自頂向下的。

情景4.2：叔叔結(jié)點(diǎn)不存在，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子結(jié)點(diǎn)

單純從插入前來看，也即不算情景4.1自底向上處理時(shí)的情況，叔叔結(jié)點(diǎn)非紅即為葉子結(jié)點(diǎn)(Nil)。

我們沒有考慮叔叔節(jié)點(diǎn)是黑節(jié)點(diǎn)情況，因?yàn)槿绻迨褰Y(jié)點(diǎn)為黑結(jié)點(diǎn)，而父結(jié)點(diǎn)為紅結(jié)點(diǎn)，那么叔叔結(jié)點(diǎn)所在的子樹的黑色結(jié)點(diǎn)就比父結(jié)點(diǎn)所在子樹的多了，這不滿足紅黑樹的性質(zhì)5。后續(xù)情景同樣如此，不再多做說明了。

情景4.2.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)

處理：

將P設(shè)為黑色
將PP設(shè)為紅色
對(duì)PP進(jìn)行右旋

TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

左邊兩個(gè)紅結(jié)點(diǎn)，右邊不存在，那么一邊一個(gè)剛剛好，并且因?yàn)闉榧t色，肯定不會(huì)破壞樹的平衡。

情景4.2.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)

這種情景顯然可以轉(zhuǎn)換為情景4.2.1

處理：

對(duì)P進(jìn)行左旋
把P設(shè)置為插入結(jié)點(diǎn)，得到情景4.2.1
進(jìn)行情景4.2.1的處理

TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

情景4.3：叔叔結(jié)點(diǎn)不存在，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn)

該情景對(duì)應(yīng)情景4.2，只是方向反轉(zhuǎn)

情景4.3.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)

處理：

將P設(shè)為黑色
將PP設(shè)為紅色
對(duì)PP進(jìn)行左旋

TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

情景4.3.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)

處理：

對(duì)P進(jìn)行右旋
把P設(shè)置為插入結(jié)點(diǎn)，得到情景4.3.1
進(jìn)行情景4.3.1的處理

TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

關(guān)于作者

來自一線程序員Seven的探索與實(shí)踐，持續(xù)學(xué)習(xí)迭代中~

本文已收錄于我的個(gè)人博客： https://www.seven97.top

公眾號(hào)：seven97，歡迎關(guān)注~

小編推薦閱讀

好特網(wǎng)發(fā)布此文僅為傳遞信息，不代表好特網(wǎng)認(rèn)同期限觀點(diǎn)或證實(shí)其描述。

a 1.0: 類型：休閑益智　　運(yùn)營(yíng)狀態(tài)：正式運(yùn)營(yíng)　　語言：中文　　; 游戲攻略

游戲禮包

游戲視頻

游戲下載

游戲活動(dòng); 《alittletotheleft》官網(wǎng)正版是一款備受歡迎的休閑益智整理游戲。玩家的任務(wù)是對(duì)日常生活中的各種雜亂物

立即下載

黑 1.0.3: 類型：休閑益智　　運(yùn)營(yíng)狀態(tài)：正式運(yùn)營(yíng)　　語言：英文　　; 游戲攻略

游戲禮包

游戲視頻

游戲下載

游戲活動(dòng); 《黑》是游戲商BartBonte開發(fā)的一款非常有趣的休閑游戲。采用極簡(jiǎn)式的畫風(fēng)，前面的關(guān)卡都非常簡(jiǎn)單，各個(gè)

首頁(yè)

找游戲

游戲庫(kù)

開測(cè)表

搶禮包

看攻略

手游排行榜

新聞中心

游戲中心

熱門專區(qū)

熱門頻道

小編推薦

特色欄目

抖音熱游

一刀999

絕地吃雞

沙雕游戲

BT手游

經(jīng)典街機(jī)

真人互動(dòng)

TreeMap源碼詳解—徹底搞懂紅黑樹的平衡操作

下載游戲

介紹

底層實(shí)現(xiàn)

繼承接口的關(guān)鍵方法

初始屬性

構(gòu)造方法

put 方法

紅黑樹

紅黑樹平衡源碼

情景1：紅黑樹為空樹

情景2：插入結(jié)點(diǎn)的Key已存在

情景3：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為黑結(jié)點(diǎn)

情景4：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅結(jié)點(diǎn)

情景4.1：叔叔結(jié)點(diǎn)存在并且為紅結(jié)點(diǎn)

情景4.2：叔叔結(jié)點(diǎn)不存在，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子結(jié)點(diǎn)

情景4.2.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)

情景4.2.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)

情景4.3：叔叔結(jié)點(diǎn)不存在，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn)

情景4.3.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)

情景4.3.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)

關(guān)于作者

好特網(wǎng)發(fā)布此文僅為傳遞信息，不代表好特網(wǎng)認(rèn)同期限觀點(diǎn)或證實(shí)其描述。

游戲攻略

游戲禮包

游戲視頻

游戲下載

游戲活動(dòng)

立即下載

游戲攻略

游戲禮包

游戲視頻

游戲下載

游戲活動(dòng)

立即下載

相關(guān)視頻攻略

更多

同類最新

更多

熱門資訊

更多

更多

更多

情景4.3：叔叔結(jié)點(diǎn)不存在，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn)

好特網(wǎng)發(fā)布此文僅為傳遞信息，不代表好特網(wǎng)認(rèn)同期限觀點(diǎn)或證實(shí)其描述。