欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JDK集合源碼之解析TreeMap(二)

 更新時(shí)間:2021年07月06日 17:25:22   作者:興趣使然的草帽路飛  
下面小編就為大家?guī)硪黄獪\談java中的TreeMap 排序與TreeSet 排序。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧

刪除元素

刪除元素本身比較簡單,就是采用二叉樹的刪除規(guī)則。

  • 如果刪除的位置有兩個葉子節(jié)點(diǎn),則從其右子樹中取最小的元素放到刪除的位置,然后把刪除位置移到替代元素的位置,進(jìn)入下一步。
  • 如果刪除的位置只有一個葉子節(jié)點(diǎn)(有可能是經(jīng)過第一步轉(zhuǎn)換后的刪除位置),則把那個葉子節(jié)點(diǎn)作為替代元素,放到刪除的位置,然后把這個葉子節(jié)點(diǎn)刪除。
  • 如果刪除的位置沒有葉子節(jié)點(diǎn),則直接把這個刪除位置的元素刪除即可。
  • 針對紅黑樹,如果刪除位置是黑色節(jié)點(diǎn),還需要做再平衡。
  • 如果有替代元素,則以替代元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡。
  • 如果沒有替代元素,則以刪除的位置的元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡,平衡之后再刪除這個節(jié)點(diǎn)。
public V remove(Object key) {
    // 獲取節(jié)點(diǎn)
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
    V oldValue = p.value;
    // 刪除節(jié)點(diǎn)
    deleteEntry(p);
    // 返回刪除的value
    return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
    // 修改次數(shù)加1
    modCount++;
    // 元素個數(shù)減1
    size--;
    if (p.left != null && p.right != null) {
        // 如果當(dāng)前節(jié)點(diǎn)既有左子節(jié)點(diǎn),又有右子節(jié)點(diǎn)
        // 取其右子樹中最小的節(jié)點(diǎn)
        Entry<K,V> s = successor(p);
        // 用右子樹中最小節(jié)點(diǎn)的值替換當(dāng)前節(jié)點(diǎn)的值
        p.key = s.key;
        p.value = s.value;
        // 把右子樹中最小節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)
        p = s;
        // 這種情況實(shí)際上并沒有刪除p節(jié)點(diǎn),而是把p節(jié)點(diǎn)的值改了,實(shí)際刪除的是p的后繼節(jié)點(diǎn)
    }
    // 如果原來的當(dāng)前節(jié)點(diǎn)(p)有2個子節(jié)點(diǎn),則當(dāng)前節(jié)點(diǎn)已經(jīng)變成原來p的右子樹中的最小節(jié)點(diǎn)了,也就是說其沒有左子節(jié)點(diǎn)了
    // 到這一步,p肯定只有一個子節(jié)點(diǎn)了
    // 如果當(dāng)前節(jié)點(diǎn)有子節(jié)點(diǎn),則用子節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn)
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {
        // 把替換節(jié)點(diǎn)直接放到當(dāng)前節(jié)點(diǎn)的位置上(相當(dāng)于刪除了p,并把替換節(jié)點(diǎn)移動過來了)
        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的各項(xiàng)屬性都設(shè)為空
        p.left = p.right = p.parent = null;
        // 如果p是黑節(jié)點(diǎn),則需要再平衡
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {
        // 如果當(dāng)前節(jié)點(diǎn)就是根節(jié)點(diǎn),則直接將根節(jié)點(diǎn)設(shè)為空即可
        root = null;
    } else {
        // 如果當(dāng)前節(jié)點(diǎn)沒有子節(jié)點(diǎn)且其為黑節(jié)點(diǎn),則把自己當(dāng)作虛擬的替換節(jié)點(diǎn)進(jìn)行再平衡
        if (p.color == BLACK)
            fixAfterDeletion(p);
        // 平衡完成后刪除當(dāng)前節(jié)點(diǎn)(與父節(jié)點(diǎn)斷絕關(guān)系)
        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;
        }
    }
}

刪除再平衡

經(jīng)過上面的處理,真正刪除的肯定是黑色節(jié)點(diǎn)才會進(jìn)入到再平衡階段。

因?yàn)閯h除的是黑色節(jié)點(diǎn),導(dǎo)致整顆樹不平衡了,所以這里我們假設(shè)把刪除的黑色賦予當(dāng)前節(jié)點(diǎn),這樣當(dāng)前節(jié)點(diǎn)除了它自已的顏色還多了一個黑色,那么:

(1)如果當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn),則直接涂黑即可,不需要再平衡;

(2)如果當(dāng)前節(jié)點(diǎn)是紅+黑節(jié)點(diǎn),則直接涂黑即可,不需要平衡;

(3)如果當(dāng)前節(jié)點(diǎn)是黑+黑節(jié)點(diǎn),則我們只要通過旋轉(zhuǎn)把這個多出來的黑色不斷的向上傳遞到一個紅色節(jié)點(diǎn)即可,這又可能會出現(xiàn)以下四種情況:

假設(shè)當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)

情況 策略
1)x是黑+黑節(jié)點(diǎn),x的兄弟是紅節(jié)點(diǎn) (1)將兄弟節(jié)點(diǎn)設(shè)為黑色; (2)將父節(jié)點(diǎn)設(shè)為紅色; (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步;
2)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色 (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色; (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán);
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為黑色,左子節(jié)點(diǎn)為紅色 (1)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色; (2)將兄弟節(jié)點(diǎn)設(shè)為紅色; (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步;
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為紅色,左子節(jié)點(diǎn)任意顏色 (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色; (2)將父節(jié)點(diǎn)設(shè)為黑色; (3)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色; (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋; (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán));

假設(shè)當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn),正好反過來

情況 策略
1)x是黑+黑節(jié)點(diǎn),x的兄弟是紅節(jié)點(diǎn) (1)將兄弟節(jié)點(diǎn)設(shè)為黑色; (2)將父節(jié)點(diǎn)設(shè)為紅色; (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步;
2)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色 (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色; (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán);
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)為黑色,右子節(jié)點(diǎn)為紅色 (1)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色; (2)將兄弟節(jié)點(diǎn)設(shè)為紅色; (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步;
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)為紅色,右子節(jié)點(diǎn)任意顏色 (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色; (2)將父節(jié)點(diǎn)設(shè)為黑色; (3)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色; (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋; (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán));

讓我們來看看TreeMap中的實(shí)現(xiàn):

/**
 * 刪除再平衡
 *(1)每個節(jié)點(diǎn)或者是黑色,或者是紅色。
 *(2)根節(jié)點(diǎn)是黑色。
 *(3)每個葉子節(jié)點(diǎn)(NIL)是黑色。(注意:這里葉子節(jié)點(diǎn),是指為空(NIL或NULL)的葉子節(jié)點(diǎn)?。?
 *(4)如果一個節(jié)點(diǎn)是紅色的,則它的子節(jié)點(diǎn)必須是黑色的。
 *(5)從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
 */
private void fixAfterDeletion(Entry<K,V> x) {
    // 只有當(dāng)前節(jié)點(diǎn)不是根節(jié)點(diǎn)且當(dāng)前節(jié)點(diǎn)是黑色時(shí)才進(jìn)入循環(huán)
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            // 如果當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
            // sib是當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
            Entry<K,V> sib = rightOf(parentOf(x));
            // 情況1)如果兄弟節(jié)點(diǎn)是紅色
            if (colorOf(sib) == RED) {
                // (1)將兄弟節(jié)點(diǎn)設(shè)為黑色
                setColor(sib, BLACK);
                // (2)將父節(jié)點(diǎn)設(shè)為紅色
                setColor(parentOf(x), RED);
                // (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
                rotateLeft(parentOf(x));
                // (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                // 情況2)如果兄弟節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色
                // (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色
                setColor(sib, RED);
                // (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán)
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    // 情況3)如果兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為黑色
                    // (1)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色
                    setColor(leftOf(sib), BLACK);
                    // (2)將兄弟節(jié)點(diǎn)設(shè)為紅色
                    setColor(sib, RED);
                    // (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
                    rotateRight(sib);
                    // (4)重新設(shè)置x的兄弟節(jié)點(diǎn)
                    sib = rightOf(parentOf(x));
                }
                // 情況4)
                // (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色
                setColor(sib, colorOf(parentOf(x)));
                // (2)將父節(jié)點(diǎn)設(shè)為黑色
                setColor(parentOf(x), BLACK);
                // (3)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色
                setColor(rightOf(sib), BLACK);
                // (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
                rotateLeft(parentOf(x));
                // (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán))
                x = root;
            }
        } else { // symmetric
            // 如果當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
            // sib是當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
            Entry<K,V> sib = leftOf(parentOf(x));
            // 情況1)如果兄弟節(jié)點(diǎn)是紅色
            if (colorOf(sib) == RED) {
                // (1)將兄弟節(jié)點(diǎn)設(shè)為黑色
                setColor(sib, BLACK);
                // (2)將父節(jié)點(diǎn)設(shè)為紅色
                setColor(parentOf(x), RED);
                // (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
                rotateRight(parentOf(x));
                // (4)重新設(shè)置x的兄弟節(jié)點(diǎn)
                sib = leftOf(parentOf(x));
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                // 情況2)如果兄弟節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色
                // (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色
                setColor(sib, RED);
                // (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán)
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    // 情況3)如果兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)為黑色
                    // (1)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色
                    setColor(rightOf(sib), BLACK);
                    // (2)將兄弟節(jié)點(diǎn)設(shè)為紅色
                    setColor(sib, RED);
                    // (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
                    rotateLeft(sib);
                    // (4)重新設(shè)置x的兄弟節(jié)點(diǎn)
                    sib = leftOf(parentOf(x));
                }
                // 情況4)
                // (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色
                setColor(sib, colorOf(parentOf(x)));
                // (2)將父節(jié)點(diǎn)設(shè)為黑色
                setColor(parentOf(x), BLACK);
                // (3)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色
                setColor(leftOf(sib), BLACK);
                // (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
                rotateRight(parentOf(x));
                // (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán))
                x = root;
            }
        }
    }
    // 退出條件為多出來的黑色向上傳遞到了根節(jié)點(diǎn)或者紅節(jié)點(diǎn)
    // 則將x設(shè)為黑色即可滿足紅黑樹規(guī)則
    setColor(x, BLACK);
}

刪除元素舉例

假設(shè)我們有下面這樣一顆紅黑樹。

treemap-delete1

我們刪除6號元素,則從右子樹中找到了最小元素7,7又沒有子節(jié)點(diǎn)了,所以把7作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。

我們看到7是黑節(jié)點(diǎn),且其兄弟為黑節(jié)點(diǎn),且其兄弟的兩個子節(jié)點(diǎn)都是紅色,滿足情況4),平衡之后如下圖所示。

treemap-delete2

我們再刪除7號元素,則從右子樹中找到了最小元素8,8有子節(jié)點(diǎn)且為黑色,所以8的子節(jié)點(diǎn)9是替代節(jié)點(diǎn),以9為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。

我們發(fā)現(xiàn)9是紅節(jié)點(diǎn),則直接把它涂成黑色即滿足了紅黑樹的特性,不需要再過多的平衡了。

treemap-delete3

這次我們來個狠的,把根節(jié)點(diǎn)刪除,從右子樹中找到了最小的元素5,5沒有子節(jié)點(diǎn),所以把5作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。

我們看到5是黑節(jié)點(diǎn),且其兄弟為紅色,符合情況1),平衡之后如下圖所示,然后進(jìn)入情況2)。

treemap-delete4

對情況2)進(jìn)行再平衡后如下圖所示。

treemap-delete5

然后進(jìn)入下一次循環(huán),發(fā)現(xiàn)不符合循環(huán)條件了,直接把x涂為黑色即可,退出這個方法之后會把舊x刪除掉(見deleteEntry()方法),最后的結(jié)果就是下面這樣。

treemap-delete6

二叉樹的遍歷

我們知道二叉查找樹的遍歷有前序遍歷、中序遍歷、后序遍歷。

(1)前序遍歷,先遍歷我,再遍歷我的左子節(jié)點(diǎn),最后遍歷我的右子節(jié)點(diǎn);

(2)中序遍歷,先遍歷我的左子節(jié)點(diǎn),再遍歷我,最后遍歷我的右子節(jié)點(diǎn);

(3)后序遍歷,先遍歷我的左子節(jié)點(diǎn),再遍歷我的右子節(jié)點(diǎn),最后遍歷我;

這里的前中后都是以“我”的順序?yàn)闇?zhǔn)的,我在前就是前序遍歷,我在中就是中序遍歷,我在后就是后序遍歷。

下面讓我們看看經(jīng)典的中序遍歷是怎么實(shí)現(xiàn)的:

public class TreeMapTest {
    public static void main(String[] args) {
        // 構(gòu)建一顆10個元素的樹
        TreeNode<Integer> node = new TreeNode<>(1, null).insert(2)
                .insert(6).insert(3).insert(5).insert(9)
                .insert(7).insert(8).insert(4).insert(10);
        // 中序遍歷,打印結(jié)果為1到10的順序
        node.root().inOrderTraverse();
    }
}
/**
 * 樹節(jié)點(diǎn),假設(shè)不存在重復(fù)元素
 * @param <T>
 */
class TreeNode<T extends Comparable<T>> {
    T value;
    TreeNode<T> parent;
    TreeNode<T> left, right;
    public TreeNode(T value, TreeNode<T> parent) {
        this.value = value;
        this.parent = parent;
    }
    /**
     * 獲取根節(jié)點(diǎn)
     */
    TreeNode<T> root() {
        TreeNode<T> cur = this;
        while (cur.parent != null) {
            cur = cur.parent;
        }
        return cur;
    }
    /**
     * 中序遍歷
     */
    void inOrderTraverse() {
        if(this.left != null) this.left.inOrderTraverse();
        System.out.println(this.value);
        if(this.right != null) this.right.inOrderTraverse();
    }
    /**
     * 經(jīng)典的二叉樹插入元素的方法
     */
    TreeNode<T> insert(T value) {
        // 先找根元素
        TreeNode<T> cur = root();
        TreeNode<T> p;
        int dir;
        // 尋找元素應(yīng)該插入的位置
        do {
            p = cur;
            if ((dir=value.compareTo(p.value)) < 0) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        } while (cur != null);
        // 把元素放到找到的位置
        if (dir < 0) {
            p.left = new TreeNode<>(value, p);
            return p.left;
        } else {
            p.right = new TreeNode<>(value, p);
            return p.right;
        }
    }
}

TreeMap的遍歷

從上面二叉樹的遍歷我們很明顯地看到,它是通過遞歸的方式實(shí)現(xiàn)的,但是遞歸會占用額外的空間,直接到線程棧整個釋放掉才會把方法中申請的變量銷毀掉,所以當(dāng)元素特別多的時(shí)候是一件很危險(xiǎn)的事。

(上面的例子中,沒有申請額外的空間,如果有聲明變量,則可以理解為直到方法完成才會銷毀變量)

那么,有沒有什么方法不用遞歸呢?

讓我們來看看java中的實(shí)現(xiàn):

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    // 遍歷前的修改次數(shù)
    int expectedModCount = modCount;
    // 執(zhí)行遍歷,先獲取第一個元素的位置,再循環(huán)遍歷后繼節(jié)點(diǎn)
    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
        // 執(zhí)行動作
        action.accept(e.key, e.value);
        // 如果發(fā)現(xiàn)修改次數(shù)變了,則拋出異常
        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }
}

是不是很簡單?!

(1)尋找第一個節(jié)點(diǎn);

從根節(jié)點(diǎn)開始找最左邊的節(jié)點(diǎn),即最小的元素。

    final Entry<K,V> getFirstEntry() {
        Entry<K,V> p = root;
        // 從根節(jié)點(diǎn)開始找最左邊的節(jié)點(diǎn),即最小的元素
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

(2)循環(huán)遍歷后繼節(jié)點(diǎn);

尋找后繼節(jié)點(diǎn)這個方法我們在刪除元素的時(shí)候也用到過,當(dāng)時(shí)的場景是有右子樹,則從其右子樹中尋找最小的節(jié)點(diǎn)。

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        // 如果當(dāng)前節(jié)點(diǎn)為空,返回空
        return null;
    else if (t.right != null) {
        // 如果當(dāng)前節(jié)點(diǎn)有右子樹,取右子樹中最小的節(jié)點(diǎn)
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 如果當(dāng)前節(jié)點(diǎn)沒有右子樹
        // 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn),直接返回父節(jié)點(diǎn)
        // 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn),一直往上找,直到找到一個祖先節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)為止,返回這個祖先節(jié)點(diǎn)的父節(jié)點(diǎn)
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

讓我們一起來分析下這種方式的時(shí)間復(fù)雜度吧。

首先,尋找第一個元素,因?yàn)榧t黑樹是接近平衡的二叉樹,所以找最小的節(jié)點(diǎn),相當(dāng)于是從頂?shù)降琢?,時(shí)間復(fù)雜度為O(log n);

其次,尋找后繼節(jié)點(diǎn),因?yàn)榧t黑樹插入元素的時(shí)候會自動平衡,最壞的情況就是尋找右子樹中最小的節(jié)點(diǎn),時(shí)間復(fù)雜度為O(log k),k為右子樹元素個數(shù);

最后,需要遍歷所有元素,時(shí)間復(fù)雜度為O(n);

所以,總的時(shí)間復(fù)雜度為 O(log n) + O(n * log k) ≈ O(n)。

雖然遍歷紅黑樹的時(shí)間復(fù)雜度是O(n),但是它實(shí)際是要比跳表要慢一點(diǎn)的,啥?跳表是啥?安心,后面會講到跳表的。

總結(jié)

到這里紅黑樹就整個講完了,讓我們再回顧下紅黑樹的特性:

  • 每個節(jié)點(diǎn)或者是黑色,或者是紅色。
  • 根節(jié)點(diǎn)是黑色。
  • 每個葉子節(jié)點(diǎn)(NIL)是黑色。(注意:這里葉子節(jié)點(diǎn),是指為空(NIL或NULL)的葉子節(jié)點(diǎn)!)
  • 如果一個節(jié)點(diǎn)是紅色的,則它的子節(jié)點(diǎn)必須是黑色的。
  • 從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

除了上述這些標(biāo)準(zhǔn)的紅黑樹的特性,你還能講出來哪些TreeMap的特性呢?

  • TreeMap的存儲結(jié)構(gòu)只有一顆紅黑樹;
  • TreeMap中的元素是有序的,按key的順序排列;
  • TreeMap比HashMap要慢一些,因?yàn)镠ashMap前面還做了一層桶,尋找元素要快很多;
  • TreeMap沒有擴(kuò)容的概念;
  • TreeMap的遍歷不是采用傳統(tǒng)的遞歸式遍歷;
  • TreeMap可以按范圍查找元素,查找最近的元素;

本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • 實(shí)例解析如何正確使用Java數(shù)組

    實(shí)例解析如何正確使用Java數(shù)組

    同一種類型數(shù)據(jù)的集合。其實(shí)數(shù)組就是一個容器。運(yùn)算的時(shí)候有很多數(shù)據(jù)參與運(yùn)算,那么首先需要做的是什么下面我們就一起來看看。
    2016-07-07
  • SpringBoot Application的exclude不生效問題及排查

    SpringBoot Application的exclude不生效問題及排查

    這篇文章主要介紹了SpringBoot Application的exclude不生效問題及排查,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-11-11
  • Java正則表達(dá)式之Pattern和Matcher的使用

    Java正則表達(dá)式之Pattern和Matcher的使用

    本文詳細(xì)介紹了Java中處理正則表達(dá)式的Pattern和Matcher類的使用方法和實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2024-09-09
  • SpringBoot實(shí)現(xiàn)OneDrive文件上傳的詳細(xì)步驟

    SpringBoot實(shí)現(xiàn)OneDrive文件上傳的詳細(xì)步驟

    這篇文章主要介紹了SpringBoot實(shí)現(xiàn)OneDrive文件上傳的詳細(xì)步驟,文中通過代碼示例和圖文講解的非常詳細(xì),對大家實(shí)現(xiàn)OneDrive文件上傳有一定的幫助,需要的朋友可以參考下
    2024-02-02
  • SpringBoot集成Druid實(shí)現(xiàn)多數(shù)據(jù)源的兩種方式

    SpringBoot集成Druid實(shí)現(xiàn)多數(shù)據(jù)源的兩種方式

    這篇文章主要介紹了SpringBoot集成Druid實(shí)現(xiàn)多數(shù)據(jù)源的兩種方式,集成com.baomidou的方式和基于AOP手動實(shí)現(xiàn)多數(shù)據(jù)源原生的方式,文中通過代碼示例講解的非常詳細(xì),需要的朋友可以參考下
    2024-03-03
  • 使用Spring源碼報(bào)錯java:找不到類 InstrumentationSavingAgent的問題

    使用Spring源碼報(bào)錯java:找不到類 InstrumentationSavingAgent的問題

    這篇文章主要介紹了使用Spring源碼報(bào)錯java:找不到類 InstrumentationSavingAgent的問題,本文給大家分享解決方法,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-10-10
  • java后端如何調(diào)用第三方接口(往header和body中的參數(shù)傳參)

    java后端如何調(diào)用第三方接口(往header和body中的參數(shù)傳參)

    這篇文章主要介紹了java后端如何調(diào)用第三方接口(往header和body中的參數(shù)傳參),具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-12-12
  • Java中的數(shù)組流ByteArrayOutputStream用法

    Java中的數(shù)組流ByteArrayOutputStream用法

    Java中的ByteArrayOutputStream是java.io包中的一個類,用于在內(nèi)存中創(chuàng)建字節(jié)數(shù)組緩沖區(qū),支持動態(tài)擴(kuò)展,它繼承自O(shè)utputStream,允許以字節(jié)形式寫入數(shù)據(jù),無需與外部設(shè)備交互,常用方法包括write()、toByteArray()、toString()等
    2024-09-09
  • Java中BeanUtils.copyProperties基本用法與小坑

    Java中BeanUtils.copyProperties基本用法與小坑

    本文主要介紹了Java中BeanUtils.copyProperties基本用法與小坑,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-04-04
  • 生產(chǎn)者消費(fèi)者模型ThreadLocal原理及實(shí)例詳解

    生產(chǎn)者消費(fèi)者模型ThreadLocal原理及實(shí)例詳解

    這篇文章主要介紹了生產(chǎn)者消費(fèi)者模型ThreadLocal原理及實(shí)例詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-09-09

最新評論