JDK集合源碼之解析TreeMap(二)
刪除元素
刪除元素本身比較簡(jiǎn)單，就是采用二叉樹(shù)的刪除規(guī)則。
- 如果刪除的位置有兩個(gè)葉子節(jié)點(diǎn)，則從其右子樹(shù)中取最小的元素放到刪除的位置，然后把刪除位置移到替代元素的位置，進(jìn)入下一步。
- 如果刪除的位置只有一個(gè)葉子節(jié)點(diǎn)（有可能是經(jīng)過(guò)第一步轉(zhuǎn)換后的刪除位置），則把那個(gè)葉子節(jié)點(diǎn)作為替代元素，放到刪除的位置，然后把這個(gè)葉子節(jié)點(diǎn)刪除。
- 如果刪除的位置沒(méi)有葉子節(jié)點(diǎn)，則直接把這個(gè)刪除位置的元素刪除即可。
- 針對(duì)紅黑樹(shù)，如果刪除位置是黑色節(jié)點(diǎn)，還需要做再平衡。
- 如果有替代元素，則以替代元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡。
- 如果沒(méi)有替代元素，則以刪除的位置的元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡，平衡之后再刪除這個(gè)節(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++;
// 元素個(gè)數(shù)減1
size--;
if (p.left != null && p.right != null) {
// 如果當(dāng)前節(jié)點(diǎn)既有左子節(jié)點(diǎn)，又有右子節(jié)點(diǎn)
// 取其右子樹(shù)中最小的節(jié)點(diǎn)
Entry<K,V> s = successor(p);
// 用右子樹(shù)中最小節(jié)點(diǎn)的值替換當(dāng)前節(jié)點(diǎn)的值
p.key = s.key;
p.value = s.value;
// 把右子樹(shù)中最小節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)
p = s;
// 這種情況實(shí)際上并沒(méi)有刪除p節(jié)點(diǎn)，而是把p節(jié)點(diǎn)的值改了，實(shí)際刪除的是p的后繼節(jié)點(diǎn)
}
// 如果原來(lái)的當(dāng)前節(jié)點(diǎn)（p）有2個(gè)子節(jié)點(diǎn)，則當(dāng)前節(jié)點(diǎn)已經(jīng)變成原來(lái)p的右子樹(shù)中的最小節(jié)點(diǎn)了，也就是說(shuō)其沒(méi)有左子節(jié)點(diǎn)了
// 到這一步，p肯定只有一個(gè)子節(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)移動(dòng)過(guò)來(lái)了）
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)沒(méi)有子節(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)過(guò)上面的處理，真正刪除的肯定是黑色節(jié)點(diǎn)才會(huì)進(jìn)入到再平衡階段。
因?yàn)閯h除的是黑色節(jié)點(diǎn)，導(dǎo)致整顆樹(shù)不平衡了，所以這里我們假設(shè)把刪除的黑色賦予當(dāng)前節(jié)點(diǎn)，這樣當(dāng)前節(jié)點(diǎn)除了它自已的顏色還多了一個(gè)黑色，那么：
（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)，則我們只要通過(guò)旋轉(zhuǎn)把這個(gè)多出來(lái)的黑色不斷的向上傳遞到一個(gè)紅色節(jié)點(diǎn)即可，這又可能會(huì)出現(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)的兩個(gè)子節(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)，正好反過(guò)來(lái)）
| 情況 | 策略 |
|---|---|
| 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)的兩個(gè)子節(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)）； |
讓我們來(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 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)的兩個(gè)子節(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)的兩個(gè)子節(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;
}
}
}
// 退出條件為多出來(lái)的黑色向上傳遞到了根節(jié)點(diǎn)或者紅節(jié)點(diǎn)
// 則將x設(shè)為黑色即可滿足紅黑樹(shù)規(guī)則
setColor(x, BLACK);
}
刪除元素舉例
假設(shè)我們有下面這樣一顆紅黑樹(shù)。
我們刪除6號(hào)元素，則從右子樹(shù)中找到了最小元素7，7又沒(méi)有子節(jié)點(diǎn)了，所以把7作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。
我們看到7是黑節(jié)點(diǎn)，且其兄弟為黑節(jié)點(diǎn)，且其兄弟的兩個(gè)子節(jié)點(diǎn)都是紅色，滿足情況4），平衡之后如下圖所示。
我們?cè)賱h除7號(hào)元素，則從右子樹(shù)中找到了最小元素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)，則直接把它涂成黑色即滿足了紅黑樹(shù)的特性，不需要再過(guò)多的平衡了。
這次我們來(lái)個(gè)狠的，把根節(jié)點(diǎn)刪除，從右子樹(shù)中找到了最小的元素5，5沒(méi)有子節(jié)點(diǎn)，所以把5作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。
我們看到5是黑節(jié)點(diǎn)，且其兄弟為紅色，符合情況1），平衡之后如下圖所示，然后進(jìn)入情況2）。
對(duì)情況2）進(jìn)行再平衡后如下圖所示。
然后進(jìn)入下一次循環(huán)，發(fā)現(xiàn)不符合循環(huán)條件了，直接把x涂為黑色即可，退出這個(gè)方法之后會(huì)把舊x刪除掉（見(jiàn)deleteEntry()方法），最后的結(jié)果就是下面這樣。
二叉樹(shù)的遍歷
我們知道二叉查找樹(shù)的遍歷有前序遍歷、中序遍歷、后序遍歷。
（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個(gè)元素的樹(shù)
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();
}
}
/**
* 樹(shù)節(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)典的二叉樹(shù)插入元素的方法
*/
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ù)的遍歷我們很明顯地看到，它是通過(guò)遞歸的方式實(shí)現(xiàn)的，但是遞歸會(huì)占用額外的空間，直接到線程棧整個(gè)釋放掉才會(huì)把方法中申請(qǐng)的變量銷毀掉，所以當(dāng)元素特別多的時(shí)候是一件很危險(xiǎn)的事。
（上面的例子中，沒(méi)有申請(qǐng)額外的空間，如果有聲明變量，則可以理解為直到方法完成才會(huì)銷毀變量）
那么，有沒(méi)有什么方法不用遞歸呢？
讓我們來(lái)看看java中的實(shí)現(xiàn)：
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
// 遍歷前的修改次數(shù)
int expectedModCount = modCount;
// 執(zhí)行遍歷，先獲取第一個(gè)元素的位置，再循環(huán)遍歷后繼節(jié)點(diǎn)
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
// 執(zhí)行動(dòng)作
action.accept(e.key, e.value);
// 如果發(fā)現(xiàn)修改次數(shù)變了，則拋出異常
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
是不是很簡(jiǎn)單？！
（1）尋找第一個(gè)節(jié)點(diǎn)；
從根節(jié)點(diǎn)開(kāi)始找最左邊的節(jié)點(diǎn)，即最小的元素。
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
// 從根節(jié)點(diǎn)開(kāi)始找最左邊的節(jié)點(diǎn)，即最小的元素
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
（2）循環(huán)遍歷后繼節(jié)點(diǎn)；
尋找后繼節(jié)點(diǎn)這個(gè)方法我們?cè)趧h除元素的時(shí)候也用到過(guò)，當(dāng)時(shí)的場(chǎng)景是有右子樹(shù)，則從其右子樹(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)有右子樹(shù)，取右子樹(shù)中最小的節(jié)點(diǎn)
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
// 如果當(dāng)前節(jié)點(diǎn)沒(méi)有右子樹(shù)
// 如果當(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)，一直往上找，直到找到一個(gè)祖先節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)為止，返回這個(gè)祖先節(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;
}
}
讓我們一起來(lái)分析下這種方式的時(shí)間復(fù)雜度吧。
首先，尋找第一個(gè)元素，因?yàn)榧t黑樹(shù)是接近平衡的二叉樹(shù)，所以找最小的節(jié)點(diǎn)，相當(dāng)于是從頂?shù)降琢耍瑫r(shí)間復(fù)雜度為O(log n)；
其次，尋找后繼節(jié)點(diǎn)，因?yàn)榧t黑樹(shù)插入元素的時(shí)候會(huì)自動(dòng)平衡，最壞的情況就是尋找右子樹(shù)中最小的節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(log k)，k為右子樹(shù)元素個(gè)數(shù)；
最后，需要遍歷所有元素，時(shí)間復(fù)雜度為O(n)；
所以，總的時(shí)間復(fù)雜度為 O(log n) + O(n * log k) ≈ O(n)。
雖然遍歷紅黑樹(shù)的時(shí)間復(fù)雜度是O(n)，但是它實(shí)際是要比跳表要慢一點(diǎn)的，啥？跳表是啥？安心，后面會(huì)講到跳表的。
總結(jié)
到這里紅黑樹(shù)就整個(gè)講完了，讓我們?cè)倩仡櫹录t黑樹(shù)的特性：
- 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
- 根節(jié)點(diǎn)是黑色。
- 每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。（注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)?。?/li>
- 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
- 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
除了上述這些標(biāo)準(zhǔn)的紅黑樹(shù)的特性，你還能講出來(lái)哪些TreeMap的特性呢？
- TreeMap的存儲(chǔ)結(jié)構(gòu)只有一顆紅黑樹(shù)；
- TreeMap中的元素是有序的，按key的順序排列；
- TreeMap比HashMap要慢一些，因?yàn)镠ashMap前面還做了一層桶，尋找元素要快很多；
- TreeMap沒(méi)有擴(kuò)容的概念；
- TreeMap的遍歷不是采用傳統(tǒng)的遞歸式遍歷；
- TreeMap可以按范圍查找元素，查找最近的元素；
本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
同一種類型數(shù)據(jù)的集合。其實(shí)數(shù)組就是一個(gè)容器。運(yùn)算的時(shí)候有很多數(shù)據(jù)參與運(yùn)算,那么首先需要做的是什么下面我們就一起來(lái)看看。2016-07-07
SpringBoot Application的exclude不生效問(wèn)題及排查
這篇文章主要介紹了SpringBoot Application的exclude不生效問(wèn)題及排查,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
Java正則表達(dá)式之Pattern和Matcher的使用
本文詳細(xì)介紹了Java中處理正則表達(dá)式的Pattern和Matcher類的使用方法和實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-09-09
SpringBoot實(shí)現(xiàn)OneDrive文件上傳的詳細(xì)步驟
這篇文章主要介紹了SpringBoot實(shí)現(xiàn)OneDrive文件上傳的詳細(xì)步驟,文中通過(guò)代碼示例和圖文講解的非常詳細(xì),對(duì)大家實(shí)現(xiàn)OneDrive文件上傳有一定的幫助,需要的朋友可以參考下2024-02-02
SpringBoot集成Druid實(shí)現(xiàn)多數(shù)據(jù)源的兩種方式
這篇文章主要介紹了SpringBoot集成Druid實(shí)現(xiàn)多數(shù)據(jù)源的兩種方式,集成com.baomidou的方式和基于AOP手動(dòng)實(shí)現(xiàn)多數(shù)據(jù)源原生的方式,文中通過(guò)代碼示例講解的非常詳細(xì),需要的朋友可以參考下2024-03-03
使用Spring源碼報(bào)錯(cuò)java:找不到類 InstrumentationSavingAgent的問(wèn)題
這篇文章主要介紹了使用Spring源碼報(bào)錯(cuò)java:找不到類 InstrumentationSavingAgent的問(wèn)題,本文給大家分享解決方法，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-10-10
java后端如何調(diào)用第三方接口(往header和body中的參數(shù)傳參)
這篇文章主要介紹了java后端如何調(diào)用第三方接口(往header和body中的參數(shù)傳參),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12
Java中的數(shù)組流ByteArrayOutputStream用法
Java中的ByteArrayOutputStream是java.io包中的一個(gè)類,用于在內(nèi)存中創(chuàng)建字節(jié)數(shù)組緩沖區(qū),支持動(dòng)態(tài)擴(kuò)展,它繼承自O(shè)utputStream,允許以字節(jié)形式寫入數(shù)據(jù),無(wú)需與外部設(shè)備交互,常用方法包括write()、toByteArray()、toString()等2024-09-09
Java中BeanUtils.copyProperties基本用法與小坑
本文主要介紹了Java中BeanUtils.copyProperties基本用法與小坑，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
生產(chǎn)者消費(fèi)者模型ThreadLocal原理及實(shí)例詳解
這篇文章主要介紹了生產(chǎn)者消費(fèi)者模型ThreadLocal原理及實(shí)例詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09