成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

Java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

hiyayiji / 1146人閱讀

摘要：有序可重復(fù)數(shù)組，線程不安全。是基于鏈接節(jié)點的線程安全的隊列。它實質(zhì)上就是一種帶有一點扭曲的數(shù)據(jù)結(jié)構(gòu)。鏈表結(jié)構(gòu)，結(jié)構(gòu)新特性，當節(jié)點數(shù)大于時，將鏈表轉(zhuǎn)換為紅黑樹過長的鏈表搜索性能降低，使用紅黑樹來提高查找性能。

Collection List(有序,可重復(fù)) ArrayList

數(shù)組，線程不安全。

查詢：帶下標訪問數(shù)組，O(1)

修改：由于arraylist不允許空的空間，當在一個arraylist的中間插入或者刪除元素，需要遍歷移動插入/刪除位置到數(shù)組尾部的所有元素。另外arraylist需要擴容時，需要將實際存儲的數(shù)組元素復(fù)制到一個新的數(shù)組去，因此一般認為修改的時間復(fù)雜度O(N)

擴容 
/*minCapacity為原list長度*/
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

默認情況1.5倍增長

Vector

數(shù)組，線程安全(條件)

與ArrayList不同的是使用了同步（Synchronized），基本實現(xiàn)了線程安全

對象進行操作時，不加鎖的話還是有問題，例如下面的例子

public Object deleteLast(Vector v){
    int lastIndex  = v.size()-1;
    v.remove(lastIndex);
}

執(zhí)行deleteLast操作時如果不加鎖，可能會出現(xiàn)remove時size錯誤

擴容默認2倍增長

Stack堆棧

繼承Vector
通過push、pop進行入棧，出棧

LinkedList

雙向鏈表，線程不安全

查詢，需要遍歷鏈表，時間復(fù)雜度O(N)

修改，只需要修改1～2個節(jié)點的指針地址，時間復(fù)雜度O(1)

Set(無序,唯一) HashSet

HashMap, 線程不安全

操作元素時間復(fù)雜度, O(1)

LinkedHashSet

LinkedHashMap，線程不安全

public class LinkedHashSet
extends HashSet
implements Set, Cloneable, java.io.Serializable {
...
    public LinkedHashSet() {super(16, .75f, true);}

}

//hashset.java中的構(gòu)造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

操作元素 O(1)

由于底層結(jié)構(gòu)是LinkedHashMap，可以記錄元素之間插入的順序

TreeSet

TreeMap, 線程不安全

由于是樹結(jié)構(gòu)，可以保證數(shù)據(jù)存儲是有序的

操作元素時間復(fù)雜度，O(logN)

Queue隊列

queue使用時要盡量避免Collection的add()和remove()方法，而是要使用offer()來加入元素，使用poll()來獲取并移出元素。它們的優(yōu)
點是通過返回值可以判斷成功與否，add()和remove()方法在失敗的時候會拋出異常。 如果要使用前端而不移出該元素，使用
element()或者peek()方法。

1、沒有實現(xiàn)的阻塞接口的LinkedList：

實現(xiàn)了java.util.Queue接口和java.util.AbstractQueue接口
　　內(nèi)置的不阻塞隊列： PriorityQueue 和 ConcurrentLinkedQueue
　　PriorityQueue 和 ConcurrentLinkedQueue 類在 Collection Framework 中加入兩個具體集合實現(xiàn)。
　　PriorityQueue 類實質(zhì)上維護了一個有序列表。加入到 Queue 中的元素根據(jù)它們的天然排序（通過其 java.util.Comparable 實現(xiàn)）或者根據(jù)傳遞給構(gòu)造函數(shù)的 java.util.Comparator 實現(xiàn)來定位。
　　ConcurrentLinkedQueue 是基于鏈接節(jié)點的、線程安全的隊列。并發(fā)訪問不需要同步。因為它在隊列的尾部添加元素并從頭部刪除它們，所以只要不需要知道隊列的大小，　　　　 　　ConcurrentLinkedQueue 對公共集合的共享訪問就可以工作得很好。收集關(guān)于隊列大小的信息會很慢，需要遍歷隊列。

2)實現(xiàn)阻塞接口的

java.util.concurrent 中加入了 BlockingQueue 接口和五個阻塞隊列類。它實質(zhì)上就是一種帶有一點扭曲的 FIFO 數(shù)據(jù)結(jié)構(gòu)。不是立即從隊列中添加或者刪除元素，線程執(zhí)行操作阻塞，直到有空間或者元素可用。
五個隊列所提供的各有不同：

ArrayBlockingQueue ：一個由數(shù)組支持的有界隊列。

LinkedBlockingQueue ：一個由鏈接節(jié)點支持的可選有界隊列。

PriorityBlockingQueue ：一個由優(yōu)先級堆支持的無界優(yōu)先級隊列。

DelayQueue ：一個由優(yōu)先級堆支持的、基于時間的調(diào)度隊列。

SynchronousQueue ：一個利用 BlockingQueue 接口的簡單聚集（rendezvous）機制。

Map HashMap

鏈表結(jié)構(gòu)，Node結(jié)構(gòu)

static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;

    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

JDK 1.8新特性，當節(jié)點數(shù)大于8時，將鏈表轉(zhuǎn)換為紅黑樹

static final int TREEIFY_THRESHOLD = 8;

if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

過長的鏈表搜索性能降低，使用紅黑樹來提高查找性能。

hash值計算 
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

對key的hash碼高16位實現(xiàn)異或

a⊕b = (?a ∧ b) ∨ (a ∧?b)

如果a、b兩個值不相同，則異或結(jié)果為1。如果a、b兩個值相同，異或結(jié)果為0

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    ...

插入table時，下標index = (n - 1) & hash
在n較小時，hash碼的低位的0和1不均勻，容易沖突導(dǎo)致碰撞。而通過上述XOR算法調(diào)整后，hash的低16位會變大，從而使得0和1分布更加均勻。

計算表容量 
static final int MAXIMUM_CAPACITY = 1 << 30;

 public HashMap(int initialCapacity, float loadFactor) {
    /**省略此處代碼**/
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

假設(shè)cap=37，則n=36， 100100

右移1， 010010，或結(jié)果=110110

右移2， 001101，或結(jié)果=111111

右移4， 000011，或結(jié)果=111111

右移8， 000000，或結(jié)果=111111

右移16， 000000，或結(jié)果=111111

結(jié)果為63，二進制或操作只有在兩數(shù)都為0時，才為0，因此通過循環(huán)右移，或操作，實際是為了找到n的最高位，并將后面的數(shù)字全部全改寫為1，從而實現(xiàn)返回大于等于initialCapacity的最小的2的冪。

擴容 
final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) { //遍歷舊鏈表
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) //單節(jié)點
                    newTab[e.hash & (newCap - 1)] = e; 
                else if (e instanceof TreeNode) //樹
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { //鏈表
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else { //尾部指針hi
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

這段代碼的含義是將oldTab[j]中的鏈表對半拆到newTab[j]和newTab[j + oldCap]

if ((e.hash & oldCap) == 0)怎么理解

我們知道oldTab中的index = (n - 1) & hash，假設(shè)n=8，則
newTab中的index = (16-1) & hash，那么在newTab中的index為index或者index + 8，那么e.hash & oldCap == 0 ,hash 必然為 X001000的形態(tài)才有可能，也就是說
if ((e.hash & oldCap) == 0)代表newindex == index的情況

loHead loTail/ hiTail hiHead 這2對指針

前面說了if ((e.hash & oldCap) == 0)表示newindex == index，那么lo指針指向的就是此類節(jié)點，hi指針指向剩下的節(jié)點
通過tail指針的移動，實現(xiàn)鏈表拆分以及各節(jié)點next指針的更新

HashTable

Dictionary, 線程安全

操作元素時間復(fù)雜度, O(1)

synchronized 線程安全

寫入數(shù)據(jù) 
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry entry = (Entry)tab[index];
    for(; entry != null ; entry = entry.next) { //遍歷鏈表
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}


private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry e = (Entry) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}
擴容

遍歷，重新計算index，并填入newMap

protected void rehash() {
    int oldCapacity = table.length;
    Entry[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry[] newMap = new Entry[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
            Entry e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry)newMap[index]; //反轉(zhuǎn)鏈表
            newMap[index] = e;
        }
    }
}
TreeMap

紅黑樹是平衡二叉樹排序樹，我們來看下它的特性

紅黑樹特性

二叉排序樹特性

是一棵空樹，

或者是具有下列性質(zhì)的二叉樹

左子樹也是二叉排序樹，且非空左子樹上所有結(jié)點的值均小于它的根結(jié)點的值

右子樹也是二叉排序樹，且非空右子樹上所有結(jié)點的值均大于它的根結(jié)點的值

平衡二叉樹特性

它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1

左右兩個子樹都是一棵平衡二叉樹。

紅黑樹的特性:

節(jié)點是紅色或黑色。

根節(jié)點是黑色。

每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。

每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)

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

查找

基于遞歸的思想處理

/*查找大于等于K的最小節(jié)點*/
final Entry getCeilingEntry(K key) {
    Entry p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) { //key < p.key
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) { key > p.key
            if (p.right != null) {
                p = p.right;
            } else { //叔節(jié)點
                Entry parent = p.parent;
                Entry ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}

/*查找小于等于K的最大節(jié)點, 原理類似，省略*/
final Entry getFloorEntry(K key) {
    ...
}

/*查找大于K的最大節(jié)點, 原理類似，省略*/
final Entry getHigherEntry(K key) {
    ...
}

/*查找小于K的最大節(jié)點, 原理類似，省略*/
final Entry getLowerEntry(K key) {
    ...
}
恢復(fù)平衡

插入/刪除節(jié)點會破壞紅黑樹的平衡，為了恢復(fù)平衡，可以進行2類操作：旋轉(zhuǎn)和著色

旋轉(zhuǎ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;
    }
}
右旋

插入節(jié)點

插入節(jié)點總是為紅色

場景分析

情形1: 新節(jié)點位于樹的根上，沒有父節(jié)點

將新節(jié)點(根節(jié)點設(shè)置為黑色）

情形2: 新節(jié)點的父節(jié)點是黑色

無處理

情形3:新節(jié)點的父節(jié)點是紅色，分3類情況

3A: 當前節(jié)點的父節(jié)點是紅色，且當前節(jié)點的祖父節(jié)點的另一個子節(jié)點（叔叔節(jié)點）也是紅色。

3B: 當前節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且當前節(jié)點是其父節(jié)點的右孩子

3C: 當前節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且當前節(jié)點是其父節(jié)點的左孩子

總結(jié)

==為了保證紅黑樹特性5，插入的節(jié)點需要是紅色==

==根節(jié)點是紅色或者黑色，都不影響紅黑樹特性5，也就是說當父節(jié)點和叔節(jié)點均為紅色時，可以通過將互換祖父與父、叔節(jié)點的顏色來上朔不平衡，并最終通過將根節(jié)點從紅色設(shè)置為黑色來解決不平衡==

==當叔節(jié)點為黑色，父節(jié)點為紅色時，按照上述思路將父節(jié)點與祖父節(jié)點顏色互換后，必然會使得當前節(jié)點所在的子樹黑色節(jié)點過多而影響紅黑樹特性5，因此需要通過旋轉(zhuǎn)將黑色節(jié)點向相反方向轉(zhuǎn)移，以平衡根的兩側(cè)==

3A

當前節(jié)點的父節(jié)點是紅色，且當前節(jié)點的祖父節(jié)點的另一個子節(jié)點（叔叔節(jié)點）也是紅色。

處理思路:

父節(jié)點與叔節(jié)點變黑色

祖父節(jié)點變紅色

當前節(jié)點轉(zhuǎn)換為祖父節(jié)點，迭代處理

graph TD
1[祖父紅]-->2[父黑]
1-->3[叔黑]
2-->4{新紅}
2-->5[兄]
3B

當前節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且當前節(jié)點是其父節(jié)點的右孩子

處理思路:

左旋/右旋父節(jié)點

后續(xù)操作見3C

3C

當前節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且當前節(jié)點是其父節(jié)點的左孩子

處理思路

父節(jié)點設(shè)置為黑色

祖父節(jié)點設(shè)置為紅色

右旋/左旋祖父節(jié)點

private void fixAfterInsertion(Entry x) {
    x.color = RED; //新插入的節(jié)點為紅色

    while (x != null && x != root && x.parent.color == RED) {
        // x的父節(jié)點 == x的父-父-左子節(jié)點
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry y = rightOf(parentOf(parentOf(x)));
            // y為x的叔節(jié)點
            if (colorOf(y) == RED) { //叔節(jié)點為紅色, 3A
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else { //叔節(jié)點為黑色
                if (x == rightOf(parentOf(x))) { //3B
                    x = parentOf(x);
                    rotateLeft(x);
                }
                //3C
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) { //3A
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) { //3C
                    x = parentOf(x);
                    rotateRight(x);
                }
                //3B
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
刪除節(jié)點

情況分析

被刪除節(jié)點沒有兒子，即為葉節(jié)點。那么，直接將該節(jié)點刪除就OK了。

被刪除節(jié)點只有一個兒子。那么，直接刪除該節(jié)點，并用該節(jié)點的唯一子節(jié)點頂替它的位置。

被刪除節(jié)點有兩個兒子。那么，先找出它的后繼節(jié)點；然后把“它的后繼節(jié)點的內(nèi)容”復(fù)制給“該節(jié)點的內(nèi)容”；之后，刪除“它的后繼節(jié)點”。在這里，后繼節(jié)點相當于替身，在將后繼節(jié)點的內(nèi)容復(fù)制給"被刪除節(jié)點"之后，再將后繼節(jié)點刪除。這樣就巧妙的將問題轉(zhuǎn)換為"刪除后繼節(jié)點"的情況了，下面就考慮后繼節(jié)點。 在"被刪除節(jié)點"有兩個非空子節(jié)點的情況下，它的后繼節(jié)點不可能是雙子非空。既然"的后繼節(jié)點"不可能雙子都非空，就意味著"該節(jié)點的后繼節(jié)點"要么沒有兒子，要么只有一個兒子。若沒有兒子，則按"情況①"進行處理；若只有一個兒子，則按"情況② "進行處理。

private void deleteEntry(Entry p) {
    modCount++;
    size--;

    // 情況3 將p的值賦予后繼節(jié)點s，并轉(zhuǎn)換為刪除s
    if (p.left != null && p.right != null) {
        Entry s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }

    // 情況2
    Entry replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to 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;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {
        root = null; //p是根節(jié)點
    } else { //情況1
        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;
        }
    }
}
重新平衡

刪除節(jié)點x，根據(jù)上文分析，x有0或1個子節(jié)點

x是紅色節(jié)點，那么刪除它不會破壞平衡

如果x是黑色

4A 兄節(jié)點為紅色

4B 兄節(jié)點的兩個子節(jié)點均為黑色

4C 兄節(jié)點的遠端子節(jié)點為黑色，另一個為紅色或無

4D 兄節(jié)點的遠端子節(jié)點為紅色，另一個為紅色或無

兄節(jié)點及其子樹的黑色節(jié)點應(yīng)該比X多一個

4A 兄節(jié)點為紅色

處理方法：

兄節(jié)點設(shè)置為黑色

父節(jié)點設(shè)置為紅色

左旋/右旋父節(jié)點，變形為B/C/D情況

4B 兄節(jié)點的兩個子節(jié)點均為黑色

處理方法：

兄節(jié)點設(shè)置為紅色

x設(shè)置為父節(jié)點，上溯不平衡

4C 遠端侄節(jié)點為黑色，另一個為紅色或無

處理方法

近端侄節(jié)點設(shè)置為黑色

兄節(jié)點設(shè)置為紅色

右旋/左旋兄節(jié)點

轉(zhuǎn)換為4D處理

4D 兄節(jié)點為黑色，遠端侄節(jié)點為紅色，一個為紅色或無

處理方法

將父節(jié)點的顏色賦予兄節(jié)點

將父節(jié)點設(shè)置為黑色

將遠端侄節(jié)點的顏色設(shè)置為黑色

左旋父節(jié)點

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/73022.html

相關(guān)文章

  • Java學(xué)習(xí)路線總結(jié)，搬磚工逆襲Java架構(gòu)師（全網(wǎng)最強）

    摘要：哪吒社區(qū)技能樹打卡打卡貼函數(shù)式接口簡介領(lǐng)域優(yōu)質(zhì)創(chuàng)作者哪吒公眾號作者架構(gòu)師奮斗者掃描主頁左側(cè)二維碼，加入群聊，一起學(xué)習(xí)一起進步歡迎點贊收藏留言前情提要無意間聽到領(lǐng)導(dǎo)們的談話，現(xiàn)在公司的現(xiàn)狀是碼農(nóng)太多，但能獨立帶隊的人太少，簡而言之，不缺干 ? 哪吒社區(qū)Java技能樹打卡?【打卡貼 day2...

    Scorpion 評論0 收藏0

  • JavaSE與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識系列——專欄導(dǎo)航

    ??前面的話?? 大家好！這是Java基礎(chǔ)知識與數(shù)據(jù)結(jié)構(gòu)博文的導(dǎo)航帖，收藏我！學(xué)習(xí)Java不迷路！ ?博客主頁：未見花聞的博客主頁 ?歡迎關(guān)注?點贊?收藏??留言? ?本文由未見花聞原創(chuàng)，CSDN首發(fā)！ ?首發(fā)時間：?2021年11月11日? ??堅持和努力一定能換來詩與遠方！ ?參考書籍：?《Java核心技術(shù)卷1》，?《Java核心技術(shù)卷2》，?《Java編程思想》 ?參考在線編程網(wǎng)站：?牛...

    Cc_2011 評論0 收藏0

  • 學(xué)Java編程需要注意的地方

    摘要：學(xué)編程真的不是一件容易的事不管你多喜歡或是多會編程，在學(xué)習(xí)和解決問題上總會碰到障礙。熟練掌握核心內(nèi)容，特別是和多線程初步具備面向?qū)ο笤O(shè)計和編程的能力掌握基本的優(yōu)化策略。 　　學(xué)Java編程真的不是一件容易的事,不管你多喜歡或是多會Java編程，在學(xué)習(xí)和解決問題上總會碰到障礙。工作的時間越久就越能明白這個道理。不過這倒是一個讓人進步的機會，因為你要一直不斷的學(xué)習(xí)才能很好的解決你面前的難題...

    leanxi 評論0 收藏0

  • java源碼

    摘要：集合源碼解析回歸基礎(chǔ)，集合源碼解析系列，持續(xù)更新和源碼分析與是兩個常用的操作字符串的類。這里我們從源碼看下不同狀態(tài)都是怎么處理的。 Java 集合深入理解：ArrayList 回歸基礎(chǔ)，Java 集合深入理解系列，持續(xù)更新~ JVM 源碼分析之 System.currentTimeMillis 及 nanoTime 原理詳解 JVM 源碼分析之 System.currentTimeMi...

    Freeman 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<