成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

hiyayiji / 1102人閱讀

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

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

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

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

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

擴(kuò)容 
/*minCapacity為原list長(zhǎng)度*/
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);
}

默認(rèn)情況1.5倍增長(zhǎng)

Vector

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

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

對(duì)象進(jìn)行操作時(shí)，不加鎖的話還是有問題，例如下面的例子

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

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

擴(kuò)容默認(rèn)2倍增長(zhǎng)

Stack堆棧

繼承Vector
通過push、pop進(jìn)行入棧，出棧

LinkedList

雙向鏈表，線程不安全

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

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

Set(無序,唯一) HashSet

HashMap, 線程不安全

操作元素時(shí)間復(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ù)存儲(chǔ)是有序的

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

Queue隊(duì)列

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

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

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

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

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

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

LinkedBlockingQueue ：一個(gè)由鏈接節(jié)點(diǎn)支持的可選有界隊(duì)列。

PriorityBlockingQueue ：一個(gè)由優(yōu)先級(jí)堆支持的無界優(yōu)先級(jí)隊(duì)列。

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

SynchronousQueue ：一個(gè)利用 BlockingQueue 接口的簡(jiǎn)單聚集（rendezvous）機(jī)制。

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新特性，當(dāng)節(jié)點(diǎn)數(shù)大于8時(shí)，將鏈表轉(zhuǎn)換為紅黑樹

static final int TREEIFY_THRESHOLD = 8;

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

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

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

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

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

如果a、b兩個(gè)值不相同，則異或結(jié)果為1。如果a、b兩個(gè)值相同，異或結(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時(shí)，下標(biāo)index = (n - 1) & hash
在n較小時(shí)，hash碼的低位的0和1不均勻，容易沖突導(dǎo)致碰撞。而通過上述XOR算法調(diào)整后，hash的低16位會(huì)變大，從而使得0和1分布更加均勻。

計(jì)算表容量 
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，二進(jìn)制或操作只有在兩數(shù)都為0時(shí)，才為0，因此通過循環(huán)右移，或操作，實(shí)際是為了找到n的最高位，并將后面的數(shù)字全部全改寫為1，從而實(shí)現(xiàn)返回大于等于initialCapacity的最小的2的冪。

擴(kuò)容 
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é)點(diǎn)
                    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]中的鏈表對(duì)半拆到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對(duì)指針

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

HashTable

Dictionary, 線程安全

操作元素時(shí)間復(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++;
}
擴(kuò)容

遍歷，重新計(jì)算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é)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值

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

平衡二叉樹特性

它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1

左右兩個(gè)子樹都是一棵平衡二叉樹。

紅黑樹的特性:

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

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

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

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

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

查找

基于遞歸的思想處理

/*查找大于等于K的最小節(jié)點(diǎn)*/
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é)點(diǎn)
                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é)點(diǎn), 原理類似，省略*/
final Entry getFloorEntry(K key) {
    ...
}

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

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

插入/刪除節(jié)點(diǎn)會(huì)破壞紅黑樹的平衡，為了恢復(fù)平衡，可以進(jìn)行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é)點(diǎn)

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

場(chǎng)景分析

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

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

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

無處理

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

3A: 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）也是紅色。

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

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

總結(jié)

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

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

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

3A

當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）也是紅色。

處理思路:

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

祖父節(jié)點(diǎn)變紅色

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

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

當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子

處理思路:

左旋/右旋父節(jié)點(diǎn)

后續(xù)操作見3C

3C

當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子

處理思路

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

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

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

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

    while (x != null && x != root && x.parent.color == RED) {
        // x的父節(jié)點(diǎn) == x的父-父-左子節(jié)點(diǎn)
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry y = rightOf(parentOf(parentOf(x)));
            // y為x的叔節(jié)點(diǎn)
            if (colorOf(y) == RED) { //叔節(jié)點(diǎn)為紅色, 3A
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else { //叔節(jié)點(diǎn)為黑色
                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é)點(diǎn)

情況分析

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

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

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

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

    // 情況3 將p的值賦予后繼節(jié)點(diǎn)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é)點(diǎn)
    } 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é)點(diǎn)x，根據(jù)上文分析，x有0或1個(gè)子節(jié)點(diǎn)

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

如果x是黑色

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

4B 兄節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)均為黑色

4C 兄節(jié)點(diǎn)的遠(yuǎn)端子節(jié)點(diǎn)為黑色，另一個(gè)為紅色或無

4D 兄節(jié)點(diǎn)的遠(yuǎn)端子節(jié)點(diǎn)為紅色，另一個(gè)為紅色或無

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

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

處理方法：

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

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

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

4B 兄節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)均為黑色

處理方法：

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

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

4C 遠(yuǎn)端侄節(jié)點(diǎn)為黑色，另一個(gè)為紅色或無

處理方法

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

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

右旋/左旋兄節(jié)點(diǎn)

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

4D 兄節(jié)點(diǎn)為黑色，遠(yuǎn)端侄節(jié)點(diǎn)為紅色，一個(gè)為紅色或無

處理方法

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

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

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

左旋父節(jié)點(diǎn)

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73022.html

相關(guān)文章

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

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

    Scorpion 評(píng)論0 收藏0

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

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

    Cc_2011 評(píng)論0 收藏0

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

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

    leanxi 評(píng)論0 收藏0

  • java源碼

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

    Freeman 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<