https://www.bilibili.com/video/av45909616?from=search&seid=4110673649068381683

https://blog.csdn.net/v_july_v/article/details/6105630

http://www.tianxiaobo.com/2018/01/11/紅黑樹詳細(xì)分析/#323-情況三

性質(zhì)

1. 每個(gè)節(jié)點(diǎn)非紅即黑
2. 根節(jié)點(diǎn)總是黑色的
3. 如果某個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的（反之不一定）
4. 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）
5. 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每條路徑，必須包含相同數(shù)目的黑色節(jié)點(diǎn)（即相同的黑色高度）

修復(fù)違規(guī)：變色/旋轉(zhuǎn)

img

插入

如果插入的節(jié)點(diǎn)是黑色，那么這個(gè)節(jié)點(diǎn)所在路徑比其他路徑多出一個(gè)黑色節(jié)點(diǎn)，這個(gè)調(diào)整起來會(huì)比較麻煩。如果插入的節(jié)點(diǎn)是紅色，此時(shí)所有路徑上的黑色節(jié)點(diǎn)數(shù)量不變，僅可能會(huì)出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)的情況。這種情況下，通過變色和旋轉(zhuǎn)進(jìn)行調(diào)整即可，比之前的簡單多了。

以紅色為默認(rèn)插入

• 如果父節(jié)點(diǎn)是黑色，沒有影響
• 如果父節(jié)點(diǎn)是紅色，那么就破環(huán)了一個(gè)紅色節(jié)點(diǎn)的孩子節(jié)點(diǎn)是黑色的性質(zhì)，需要進(jìn)行旋轉(zhuǎn)和染色讓這條路徑上的黑色節(jié)點(diǎn)數(shù)保持不變。也可能黑色節(jié)點(diǎn)數(shù)量整體加一

1. 叔叔節(jié)點(diǎn)也為紅色。
   1. 變色即可
2. 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子
   1. 左旋
3. 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子
   1. 父節(jié)點(diǎn)和祖父節(jié)點(diǎn)變色，以祖父節(jié)點(diǎn)右旋

image

刪除

刪除修復(fù)操作在遇到被刪除的節(jié)點(diǎn)是紅色節(jié)點(diǎn)或者到達(dá)root節(jié)點(diǎn)時(shí)，修復(fù)操作完畢。

刪除修復(fù)操作是針對刪除黑色節(jié)點(diǎn)才有的，當(dāng)黑色節(jié)點(diǎn)被刪除后會(huì)讓整個(gè)樹不符合RBTree的定義的第四條。需要做的處理是從兄弟節(jié)點(diǎn)上借調(diào)黑色的節(jié)點(diǎn)過來，如果兄弟節(jié)點(diǎn)沒有黑節(jié)點(diǎn)可以借調(diào)的話，就只能往上追溯，將每一級的黑節(jié)點(diǎn)數(shù)減去一個(gè)，使得整棵樹符合紅黑樹的定義。

1. 節(jié)點(diǎn)是紅色或黑色。
2. 根是黑色。
3. 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。
4. 每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）
5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)（簡稱黑高）。

這個(gè)時(shí)候性質(zhì)4和性質(zhì)5用途就凸顯了，有了這兩個(gè)性質(zhì)作為約束，即可保證任意節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)路徑最長不會(huì)超過最短路徑的2倍。

當(dāng)某條路徑最短時(shí)，這條路徑必然都是由黑色節(jié)點(diǎn)構(gòu)成。當(dāng)某條路徑長度最長時(shí)，這條路徑必然是由紅色和黑色節(jié)點(diǎn)相間構(gòu)成（性質(zhì)4限定了不能出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）。而性質(zhì)5又限定了從任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的所有路徑必須包含相同數(shù)量的黑色節(jié)點(diǎn)。此時(shí)，在路徑最長的情況下，路徑上紅色節(jié)點(diǎn)數(shù)量 = 黑色節(jié)點(diǎn)數(shù)量。該路徑長度為兩倍黑色節(jié)點(diǎn)數(shù)量，也就是最短路徑長度的2倍。

左旋是將某個(gè)節(jié)點(diǎn)旋轉(zhuǎn)為其右孩子的左孩子，而右旋是節(jié)點(diǎn)旋轉(zhuǎn)為其左孩子的右孩子

上面五種情況中，情況一和情況二比較簡單，情況三、四、五稍復(fù)雜。但如果細(xì)心觀察，會(huì)發(fā)現(xiàn)這三種情況的區(qū)別在于叔叔節(jié)點(diǎn)的顏色，如果叔叔節(jié)點(diǎn)為紅色，直接變色即可。如果叔叔節(jié)點(diǎn)為黑色，則需要選選擇，再交換顏色。

image

刪除

除操作首先要確定待刪除節(jié)點(diǎn)有幾個(gè)孩子，如果有兩個(gè)孩子，不能直接刪除該節(jié)點(diǎn)。而是要先找到該節(jié)點(diǎn)的前驅(qū)（該節(jié)點(diǎn)左子樹中最大的節(jié)點(diǎn)）或者后繼（該節(jié)點(diǎn)右子樹中最小的節(jié)點(diǎn)），然后將前驅(qū)或者后繼的值復(fù)制到要?jiǎng)h除的節(jié)點(diǎn)中，最后再將前驅(qū)或后繼刪除。由于前驅(qū)和后繼至多只有一個(gè)孩子節(jié)點(diǎn)，這樣我們就把原來要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)孩子的問題轉(zhuǎn)化為只有一個(gè)孩子節(jié)點(diǎn)的問題

紅黑樹刪除操作的復(fù)雜度在于刪除節(jié)點(diǎn)的顏色

• 當(dāng)刪除的節(jié)點(diǎn)是紅色時(shí)，直接拿其孩子節(jié)點(diǎn)補(bǔ)空位即可
• 當(dāng)刪除的節(jié)點(diǎn)是黑色時(shí)，破壞了性質(zhì)5。
  • 如果該節(jié)點(diǎn)的孩子為紅色，直接拿孩子節(jié)點(diǎn)替換被刪除的節(jié)點(diǎn)，并將孩子節(jié)點(diǎn)染成黑色，即可恢復(fù)性質(zhì)5。
  • 但如果孩子節(jié)點(diǎn)為黑色，處理起來就要復(fù)雜的多。分為6種情況，下面會(huì)展開說明。

AVL樹和紅黑樹的區(qū)別

1. 插入都是最多只需要2次旋轉(zhuǎn)操作，即兩者都是O(1)
2. 刪除node，最壞情況下AVL需要維護(hù)從被刪node到根節(jié)點(diǎn)路徑上所有node的平衡性，因此需要旋轉(zhuǎn)的量級O(logN)，而RB-Tree最多只需3次旋轉(zhuǎn)，只需要O(1)的復(fù)雜度。
3. AVL查找效率更高
4. map的實(shí)現(xiàn)只是折衷了兩者在search、insert以及delete下的效率?？傮w來說，RB-tree的統(tǒng)計(jì)性能是高于AVL的。