JDK集合源碼之解析TreeMap(一)
簡(jiǎn)介
TreeMap使用紅黑樹存儲(chǔ)元素,可以保證元素按key值的大小進(jìn)行遍歷。
繼承體系
TreeMap
實(shí)現(xiàn)了Map、SortedMap、NavigableMap、Cloneable、Serializable
等接口。
SortedMap
規(guī)定了元素可以按key的大小來(lái)遍歷,它定義了一些返回部分map的方法。
public interface SortedMap<K,V> extends Map<K,V> { // key的比較器 Comparator<? super K> comparator(); // 返回fromKey(包含)到toKey(不包含)之間的元素組成的子map SortedMap<K,V> subMap(K fromKey, K toKey); // 返回小于toKey(不包含)的子map SortedMap<K,V> headMap(K toKey); // 返回大于等于fromKey(包含)的子map SortedMap<K,V> tailMap(K fromKey); // 返回最小的key K firstKey(); // 返回最大的key K lastKey(); // 返回key集合 Set<K> keySet(); // 返回value集合 Collection<V> values(); // 返回節(jié)點(diǎn)集合 Set<Map.Entry<K, V>> entrySet(); }
NavigableMap是對(duì)SortedMap的增強(qiáng),定義了一些返回離目標(biāo)key最近的元素的方法。
public interface NavigableMap<K,V> extends SortedMap<K,V> { // 小于給定key的最大節(jié)點(diǎn) Map.Entry<K,V> lowerEntry(K key); // 小于給定key的最大key K lowerKey(K key); // 小于等于給定key的最大節(jié)點(diǎn) Map.Entry<K,V> floorEntry(K key); // 小于等于給定key的最大key K floorKey(K key); // 大于等于給定key的最小節(jié)點(diǎn) Map.Entry<K,V> ceilingEntry(K key); // 大于等于給定key的最小key K ceilingKey(K key); // 大于給定key的最小節(jié)點(diǎn) Map.Entry<K,V> higherEntry(K key); // 大于給定key的最小key K higherKey(K key); // 最小的節(jié)點(diǎn) Map.Entry<K,V> firstEntry(); // 最大的節(jié)點(diǎn) Map.Entry<K,V> lastEntry(); // 彈出最小的節(jié)點(diǎn) Map.Entry<K,V> pollFirstEntry(); // 彈出最大的節(jié)點(diǎn) Map.Entry<K,V> pollLastEntry(); // 返回倒序的map NavigableMap<K,V> descendingMap(); // 返回有序的key集合 NavigableSet<K> navigableKeySet(); // 返回倒序的key集合 NavigableSet<K> descendingKeySet(); // 返回從fromKey到toKey的子map,是否包含起止元素可以自己決定 NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive); // 返回小于toKey的子map,是否包含toKey自己決定 NavigableMap<K,V> headMap(K toKey, boolean inclusive); // 返回大于fromKey的子map,是否包含fromKey自己決定 NavigableMap<K,V> tailMap(K fromKey, boolean inclusive); // 等價(jià)于subMap(fromKey, true, toKey, false) SortedMap<K,V> subMap(K fromKey, K toKey); // 等價(jià)于headMap(toKey, false) SortedMap<K,V> headMap(K toKey); // 等價(jià)于tailMap(fromKey, true) SortedMap<K,V> tailMap(K fromKey); }
存儲(chǔ)結(jié)構(gòu)
TreeMap只使用到了紅黑樹,所以它的時(shí)間復(fù)雜度為O(log n),我們?cè)賮?lái)回顧一下紅黑樹的特性。
(1)每個(gè)節(jié)點(diǎn)或者是黑色,或者是紅色。
(2)根節(jié)點(diǎn)是黑色。
(3)每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色。(注意:這里葉子節(jié)點(diǎn),是指為空(NIL或NULL)的葉子節(jié)點(diǎn)?。?/p>
(4)如果一個(gè)節(jié)點(diǎn)是紅色的,則它的子節(jié)點(diǎn)必須是黑色的。
(5)從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
源碼解析
屬性
/** * 比較器,如果沒傳則key要實(shí)現(xiàn)Comparable接口 */ private final Comparator<? super K> comparator; /** * 根節(jié)點(diǎn) */ private transient Entry<K,V> root; /** * 元素個(gè)數(shù) */ private transient int size = 0; /** * 修改次數(shù) */ private transient int modCount = 0;
(1)comparator
按key的大小排序有兩種方式,一種是key實(shí)現(xiàn)Comparable接口,一種方式通過構(gòu)造方法傳入比較器。
(2)root
根節(jié)點(diǎn),TreeMap沒有桶的概念,所有的元素都存儲(chǔ)在一顆樹中。
Entry內(nèi)部類
存儲(chǔ)節(jié)點(diǎn),典型的紅黑樹結(jié)構(gòu)。
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; }
構(gòu)造方法
/** * 默認(rèn)構(gòu)造方法,key必須實(shí)現(xiàn)Comparable接口 */ public TreeMap() { comparator = null; } /** * 使用傳入的comparator比較兩個(gè)key的大小 */ public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } /** * key必須實(shí)現(xiàn)Comparable接口,把傳入map中的所有元素保存到新的TreeMap中 */ public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } /** * 使用傳入map的比較器,并把傳入map中的所有元素保存到新的TreeMap中 */ public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }
構(gòu)造方法主要分成兩類,一類是使用comparator比較器,一類是key必須實(shí)現(xiàn)Comparable接口。
其實(shí),筆者認(rèn)為這兩種比較方式可以合并成一種,當(dāng)沒有傳comparator的時(shí)候,可以用以下方式來(lái)給comparator賦值,這樣后續(xù)所有的比較操作都可以使用一樣的邏輯處理了,而不用每次都檢查comparator為空的時(shí)候又用Comparable來(lái)實(shí)現(xiàn)一遍邏輯。
// 如果comparator為空,則key必須實(shí)現(xiàn)Comparable接口,所以這里肯定可以強(qiáng)轉(zhuǎn) // 這樣在構(gòu)造方法中統(tǒng)一替換掉,后續(xù)的邏輯就都一致了 comparator = (k1, k2) -> ((Comparable<? super K>)k1).compareTo(k2);
get(Object key)方法
獲取元素,典型的二叉查找樹的查找方法。
public V get(Object key) { // 根據(jù)key查找元素 Entry<K,V> p = getEntry(key); // 找到了返回value值,沒找到返回null return (p==null ? null : p.value); } final Entry<K,V> getEntry(Object key) { // 如果comparator不為空,使用comparator的版本獲取元素 if (comparator != null) return getEntryUsingComparator(key); // 如果key為空返回空指針異常 if (key == null) throw new NullPointerException(); // 將key強(qiáng)轉(zhuǎn)為Comparable @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; // 從根元素開始遍歷 Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) // 如果小于0從左子樹查找 p = p.left; else if (cmp > 0) // 如果大于0從右子樹查找 p = p.right; else // 如果相等說(shuō)明找到了直接返回 return p; } // 沒找到返回null return null; } final Entry<K,V> getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; if (cpr != null) { // 從根元素開始遍歷 Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) // 如果小于0從左子樹查找 p = p.left; else if (cmp > 0) // 如果大于0從右子樹查找 p = p.right; else // 如果相等說(shuō)明找到了直接返回 return p; } } // 沒找到返回null return null; }
(1)從root遍歷整個(gè)樹;
(2)如果待查找的key比當(dāng)前遍歷的key小,則在其左子樹中查找;
(3)如果待查找的key比當(dāng)前遍歷的key大,則在其右子樹中查找;
(4)如果待查找的key與當(dāng)前遍歷的key相等,則找到了該元素,直接返回;
(5)從這里可以看出是否有comparator分化成了兩個(gè)方法,但是內(nèi)部邏輯一模一樣,因此可見筆者comparator = (k1, k2) -> ((Comparable<? super K>)k1).compareTo(k2);
這種改造的必要性。
特性再回顧
(1)每個(gè)節(jié)點(diǎn)或者是黑色,或者是紅色。
(2)根節(jié)點(diǎn)是黑色。
(3)每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色。(注意:這里葉子節(jié)點(diǎn),是指為空(NIL或NULL)的葉子節(jié)點(diǎn)?。?/p>
(4)如果一個(gè)節(jié)點(diǎn)是紅色的,則它的子節(jié)點(diǎn)必須是黑色的。
(5)從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
左旋
左旋,就是以某個(gè)節(jié)點(diǎn)為支點(diǎn)向左旋轉(zhuǎn)。
整個(gè)左旋過程如下:
(1)將 y的左節(jié)點(diǎn) 設(shè)為 x的右節(jié)點(diǎn),即將 β 設(shè)為 x的右節(jié)點(diǎn);
(2)將 x 設(shè)為 y的左節(jié)點(diǎn)的父節(jié)點(diǎn),即將 β的父節(jié)點(diǎn) 設(shè)為 x;
(3)將 x的父節(jié)點(diǎn) 設(shè)為 y的父節(jié)點(diǎn);
(4)如果 x的父節(jié)點(diǎn) 為空節(jié)點(diǎn),則將y設(shè)置為根節(jié)點(diǎn);如果x是它父節(jié)點(diǎn)的左(右)節(jié)點(diǎn),則將y設(shè)置為x父節(jié)點(diǎn)的左(右)節(jié)點(diǎn);
(5)將 x 設(shè)為 y的左節(jié)點(diǎn);
(6)將 x的父節(jié)點(diǎn) 設(shè)為 y;
讓我們來(lái)看看TreeMap中的實(shí)現(xiàn):
/** * 以p為支點(diǎn)進(jìn)行左旋 * 假設(shè)p為圖中的x */ private void rotateLeft(Entry<K,V> p) { if (p != null) { // p的右節(jié)點(diǎn),即y Entry<K,V> r = p.right; // (1)將 y的左節(jié)點(diǎn) 設(shè)為 x的右節(jié)點(diǎn) p.right = r.left; // (2)將 x 設(shè)為 y的左節(jié)點(diǎn)的父節(jié)點(diǎn)(如果y的左節(jié)點(diǎn)存在的話) if (r.left != null) r.left.parent = p; // (3)將 x的父節(jié)點(diǎn) 設(shè)為 y的父節(jié)點(diǎn) r.parent = p.parent; // (4)... if (p.parent == null) // 如果 x的父節(jié)點(diǎn) 為空,則將y設(shè)置為根節(jié)點(diǎn) root = r; else if (p.parent.left == p) // 如果x是它父節(jié)點(diǎn)的左節(jié)點(diǎn),則將y設(shè)置為x父節(jié)點(diǎn)的左節(jié)點(diǎn) p.parent.left = r; else // 如果x是它父節(jié)點(diǎn)的右節(jié)點(diǎn),則將y設(shè)置為x父節(jié)點(diǎn)的右節(jié)點(diǎn) p.parent.right = r; // (5)將 x 設(shè)為 y的左節(jié)點(diǎn) r.left = p; // (6)將 x的父節(jié)點(diǎn) 設(shè)為 y p.parent = r; } }
右旋
右旋,就是以某個(gè)節(jié)點(diǎn)為支點(diǎn)向右旋轉(zhuǎn)。
整個(gè)右旋過程如下:
(1)將 x的右節(jié)點(diǎn) 設(shè)為 y的左節(jié)點(diǎn),即 將 β 設(shè)為 y的左節(jié)點(diǎn);
(2)將 y 設(shè)為 x的右節(jié)點(diǎn)的父節(jié)點(diǎn),即 將 β的父節(jié)點(diǎn) 設(shè)為 y;
(3)將 y的父節(jié)點(diǎn) 設(shè)為 x的父節(jié)點(diǎn);
(4)如果 y的父節(jié)點(diǎn) 是 空節(jié)點(diǎn),則將x設(shè)為根節(jié)點(diǎn);如果y是它父節(jié)點(diǎn)的左(右)節(jié)點(diǎn),則將x設(shè)為y的父節(jié)點(diǎn)的左(右)節(jié)點(diǎn);
(5)將 y 設(shè)為 x的右節(jié)點(diǎn);
(6)將 y的父節(jié)點(diǎn) 設(shè)為 x;
讓我們來(lái)看看TreeMap中的實(shí)現(xiàn):
/** * 以p為支點(diǎn)進(jìn)行右旋 * 假設(shè)p為圖中的y */ private void rotateRight(Entry<K,V> p) { if (p != null) { // p的左節(jié)點(diǎn),即x Entry<K,V> l = p.left; // (1)將 x的右節(jié)點(diǎn) 設(shè)為 y的左節(jié)點(diǎn) p.left = l.right; // (2)將 y 設(shè)為 x的右節(jié)點(diǎn)的父節(jié)點(diǎn)(如果x有右節(jié)點(diǎn)的話) if (l.right != null) l.right.parent = p; // (3)將 y的父節(jié)點(diǎn) 設(shè)為 x的父節(jié)點(diǎn) l.parent = p.parent; // (4)... if (p.parent == null) // 如果 y的父節(jié)點(diǎn) 是 空節(jié)點(diǎn),則將x設(shè)為根節(jié)點(diǎn) root = l; else if (p.parent.right == p) // 如果y是它父節(jié)點(diǎn)的右節(jié)點(diǎn),則將x設(shè)為y的父節(jié)點(diǎn)的右節(jié)點(diǎn) p.parent.right = l; else // 如果y是它父節(jié)點(diǎn)的左節(jié)點(diǎn),則將x設(shè)為y的父節(jié)點(diǎn)的左節(jié)點(diǎn) p.parent.left = l; // (5)將 y 設(shè)為 x的右節(jié)點(diǎn) l.right = p; // (6)將 y的父節(jié)點(diǎn) 設(shè)為 x p.parent = l; } }
插入元素
插入元素,如果元素在樹中存在,則替換value;如果元素不存在,則插入到對(duì)應(yīng)的位置,再平衡樹。
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { // 如果沒有根節(jié)點(diǎn),直接插入到根節(jié)點(diǎn) compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } // key比較的結(jié)果 int cmp; // 用來(lái)尋找待插入節(jié)點(diǎn)的父節(jié)點(diǎn) Entry<K,V> parent; // 根據(jù)是否有comparator使用不同的分支 Comparator<? super K> cpr = comparator; if (cpr != null) { // 如果使用的是comparator方式,key值可以為null,只要在comparator.compare()中允許即可 // 從根節(jié)點(diǎn)開始遍歷尋找 do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) // 如果小于0從左子樹尋找 t = t.left; else if (cmp > 0) // 如果大于0從右子樹尋找 t = t.right; else // 如果等于0,說(shuō)明插入的節(jié)點(diǎn)已經(jīng)存在了,直接更換其value值并返回舊值 return t.setValue(value); } while (t != null); } else { // 如果使用的是Comparable方式,key不能為null if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; // 從根節(jié)點(diǎn)開始遍歷尋找 do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) // 如果小于0從左子樹尋找 t = t.left; else if (cmp > 0) // 如果大于0從右子樹尋找 t = t.right; else // 如果等于0,說(shuō)明插入的節(jié)點(diǎn)已經(jīng)存在了,直接更換其value值并返回舊值 return t.setValue(value); } while (t != null); } // 如果沒找到,那么新建一個(gè)節(jié)點(diǎn),并插入到樹中 Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) // 如果小于0插入到左子節(jié)點(diǎn) parent.left = e; else // 如果大于0插入到右子節(jié)點(diǎn) parent.right = e; // 插入之后的平衡 fixAfterInsertion(e); // 元素個(gè)數(shù)加1(不需要擴(kuò)容) size++; // 修改次數(shù)加1 modCount++; // 如果插入了新節(jié)點(diǎn)返回空 return null; }
插入再平衡
插入的元素默認(rèn)都是紅色,因?yàn)椴迦爰t色元素只違背了第4條特性,那么我們只要根據(jù)這個(gè)特性來(lái)平衡就容易多了。
根據(jù)不同的情況有以下幾種處理方式:
- 插入的元素如果是根節(jié)點(diǎn),則直接涂成黑色即可,不用平衡;
- 插入的元素的父節(jié)點(diǎn)如果為黑色,不需要平衡;
- 插入的元素的父節(jié)點(diǎn)如果為紅色,則違背了特性4,需要平衡,平衡時(shí)又分成下面三種情況:
(如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左節(jié)點(diǎn))
情況 | 策略 |
---|---|
1)父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)也為紅色 | (1)將父節(jié)點(diǎn)設(shè)為黑色; (2)將叔叔節(jié)點(diǎn)設(shè)為黑色; (3)將祖父節(jié)點(diǎn)設(shè)為紅色; (4)將祖父節(jié)點(diǎn)設(shè)為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán)判斷; |
2)父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)為黑色,且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右節(jié)點(diǎn) | (1)將父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn); (2)以新當(dāng)節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋,進(jìn)入情況3); |
3)父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)為黑色,且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左節(jié)點(diǎn) | (1)將父節(jié)點(diǎn)設(shè)為黑色; (2)將祖父節(jié)點(diǎn)設(shè)為紅色; (3)以祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋,進(jìn)入下一次循環(huán)判斷; |
(如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右節(jié)點(diǎn),則正好與上面反過來(lái))
情況 | 策略 |
---|---|
1)父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)也為紅色 | (1)將父節(jié)點(diǎn)設(shè)為黑色; (2)將叔叔節(jié)點(diǎn)設(shè)為黑色; (3)將祖父節(jié)點(diǎn)設(shè)為紅色; (4)將祖父節(jié)點(diǎn)設(shè)為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán)判斷; |
2)父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)為黑色,且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左節(jié)點(diǎn) | (1)將父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn); (2)以新當(dāng)節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋; |
3)父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)為黑色,且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右節(jié)點(diǎn) | (1)將父節(jié)點(diǎn)設(shè)為黑色; (2)將祖父節(jié)點(diǎn)設(shè)為紅色; (3)以祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋,進(jìn)入下一次循環(huán)判斷; |
讓我們來(lái)看看TreeMap中的實(shí)現(xiàn):
/** * 插入再平衡 *(1)每個(gè)節(jié)點(diǎn)或者是黑色,或者是紅色。 *(2)根節(jié)點(diǎn)是黑色。 *(3)每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色。(注意:這里葉子節(jié)點(diǎn),是指為空(NIL或NULL)的葉子節(jié)點(diǎn)?。? *(4)如果一個(gè)節(jié)點(diǎn)是紅色的,則它的子節(jié)點(diǎn)必須是黑色的。 *(5)從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。 */ private void fixAfterInsertion(Entry<K,V> x) { // 插入的節(jié)點(diǎn)為紅節(jié)點(diǎn),x為當(dāng)前節(jié)點(diǎn) x.color = RED; // 只有當(dāng)插入節(jié)點(diǎn)不是根節(jié)點(diǎn)且其父節(jié)點(diǎn)為紅色時(shí)才需要平衡(違背了特性4) while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // a)如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左節(jié)點(diǎn) // y為叔叔節(jié)點(diǎn) Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { // 情況1)如果叔叔節(jié)點(diǎn)為紅色 // (1)將父節(jié)點(diǎn)設(shè)為黑色 setColor(parentOf(x), BLACK); // (2)將叔叔節(jié)點(diǎn)設(shè)為黑色 setColor(y, BLACK); // (3)將祖父節(jié)點(diǎn)設(shè)為紅色 setColor(parentOf(parentOf(x)), RED); // (4)將祖父節(jié)點(diǎn)設(shè)為新的當(dāng)前節(jié)點(diǎn) x = parentOf(parentOf(x)); } else { // 如果叔叔節(jié)點(diǎn)為黑色 // 情況2)如果當(dāng)前節(jié)點(diǎn)為其父節(jié)點(diǎn)的右節(jié)點(diǎn) if (x == rightOf(parentOf(x))) { // (1)將父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn) x = parentOf(x); // (2)以新當(dāng)前節(jié)點(diǎn)左旋 rotateLeft(x); } // 情況3)如果當(dāng)前節(jié)點(diǎn)為其父節(jié)點(diǎn)的左節(jié)點(diǎn)(如果是情況2)則左旋之后新當(dāng)前節(jié)點(diǎn)正好為其父節(jié)點(diǎn)的左節(jié)點(diǎn)了) // (1)將父節(jié)點(diǎn)設(shè)為黑色 setColor(parentOf(x), BLACK); // (2)將祖父節(jié)點(diǎn)設(shè)為紅色 setColor(parentOf(parentOf(x)), RED); // (3)以祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋 rotateRight(parentOf(parentOf(x))); } } else { // b)如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右節(jié)點(diǎn) // y是叔叔節(jié)點(diǎn) Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { // 情況1)如果叔叔節(jié)點(diǎn)為紅色 // (1)將父節(jié)點(diǎn)設(shè)為黑色 setColor(parentOf(x), BLACK); // (2)將叔叔節(jié)點(diǎn)設(shè)為黑色 setColor(y, BLACK); // (3)將祖父節(jié)點(diǎn)設(shè)為紅色 setColor(parentOf(parentOf(x)), RED); // (4)將祖父節(jié)點(diǎn)設(shè)為新的當(dāng)前節(jié)點(diǎn) x = parentOf(parentOf(x)); } else { // 如果叔叔節(jié)點(diǎn)為黑色 // 情況2)如果當(dāng)前節(jié)點(diǎn)為其父節(jié)點(diǎn)的左節(jié)點(diǎn) if (x == leftOf(parentOf(x))) { // (1)將父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn) x = parentOf(x); // (2)以新當(dāng)前節(jié)點(diǎn)右旋 rotateRight(x); } // 情況3)如果當(dāng)前節(jié)點(diǎn)為其父節(jié)點(diǎn)的右節(jié)點(diǎn)(如果是情況2)則右旋之后新當(dāng)前節(jié)點(diǎn)正好為其父節(jié)點(diǎn)的右節(jié)點(diǎn)了) // (1)將父節(jié)點(diǎn)設(shè)為黑色 setColor(parentOf(x), BLACK); // (2)將祖父節(jié)點(diǎn)設(shè)為紅色 setColor(parentOf(parentOf(x)), RED); // (3)以祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋 rotateLeft(parentOf(parentOf(x))); } } } // 平衡完成后將根節(jié)點(diǎn)設(shè)為黑色 root.color = BLACK; }
插入元素舉例
我們依次向紅黑樹中插入 4、2、3 三個(gè)元素,來(lái)一起看看整個(gè)紅黑樹平衡的過程。
三個(gè)元素都插入完成后,符合父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左節(jié)點(diǎn),叔叔節(jié)點(diǎn)為黑色,且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右節(jié)點(diǎn),即情況2)。
情況2)需要做以下兩步處理:
(1)將父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn);
(2)以新當(dāng)節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋,進(jìn)入情況3);
情況3)需要做以下三步處理:
(1)將父節(jié)點(diǎn)設(shè)為黑色;
(2)將祖父節(jié)點(diǎn)設(shè)為紅色;
(3)以祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋,進(jìn)入下一次循環(huán)判斷;
下一次循環(huán)不符合父節(jié)點(diǎn)為紅色了,退出循環(huán),插入再平衡完成。
總結(jié)
本篇文章就到這里了,希望能給你帶來(lái)幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
Java創(chuàng)建,編輯與刪除Excel迷你圖表的實(shí)現(xiàn)方法
迷你圖是Excel工作表單元格中表示數(shù)據(jù)的微型圖表。本文將通過Java代碼示例介紹如何在Excel中創(chuàng)建迷你圖表,以及編輯和刪除表格中的迷你圖表,需要的可以參考一下2022-05-05Java中==符號(hào)與equals()的使用詳解(測(cè)試兩個(gè)變量是否相等)
下面小編就為大家?guī)?lái)一篇Java中==符號(hào)與equals()的使用詳解(測(cè)試兩個(gè)變量是否相等)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧2017-07-07WebSocket 中使用 @Autowired 注入對(duì)應(yīng)為null的解決方案
SpringBoot集成WebSocket時(shí),會(huì)遇到service對(duì)象為null的情況,原因是Spring默認(rèn)為單例模式與WebSocket的多對(duì)象模式相沖突,當(dāng)客戶端與服務(wù)器端建立連接時(shí),會(huì)創(chuàng)建新的WebSocket對(duì)象,本文給大家介紹WebSocket 中使用 @Autowired 注入對(duì)應(yīng)為null的問題,感興趣的朋友一起看看吧2024-10-10FutureTask為何單個(gè)任務(wù)僅執(zhí)行一次原理解析
這篇文章主要為大家介紹了FutureTask為何單個(gè)任務(wù)僅執(zhí)行一次原理解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11Java中的動(dòng)態(tài)和靜態(tài)編譯實(shí)例詳解
這篇文章主要介紹了Java中的動(dòng)態(tài)和靜態(tài)編譯實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04