所有偷的懶總是要還的
紅黑樹作為一個平衡二叉樹廣泛應(yīng)用在軟件系統(tǒng)中衰猛，比如內(nèi)核的vma結(jié)構(gòu)。
之前偷懶沒有徹底理解刹孔，這里做一下最近學(xué)習(xí)的筆記腕侄。
插入
按照正常的二叉樹插入，并給節(jié)點上色為紅色后芦疏。這么做將可能導(dǎo)致該節(jié)點和父節(jié)點同為紅色，顧需要重新平衡微姊。
如下的偽代碼展示了高度抽象了當(dāng)父節(jié)點為爺爺節(jié)點左孩子時的三種情況酸茴。
RB-INSERT-FIXUP(T, c)
1. while color[p[c]] = RED
2. if p[c] = left[p[p[c]]] // parent is left child of gp
3. then uncle = right[p[p[c]]]
4. if color[uncle] = RED // uncle is RED
5. then <Case 1>
6. else if c = right[p[c]] // child is left
7. then <Case 2>
8. <Case 3>
注釋：
- 循環(huán)判斷條件為父節(jié)點是紅色
- Case 1表明 c, p, u同時為紅色，且因為gp必須為黑色兢交，處理方式是將紅色節(jié)點上移
- Case 2是一個中間過程薪捍，目的是通過旋轉(zhuǎn)變換成Case 3
- Case 3是c, p, gp在同一直線上，且c，p為紅色酪穿，gp為黑色凳干，通過旋轉(zhuǎn)將這一分支上多余的紅色轉(zhuǎn)移到了gp的另一個分支上
- Case 1 是唯一不能確定是否終結(jié)的情況，Case 2,3是終結(jié)情況
插入操作的三種情況
嘗試歸納一下插入過程中的平衡步驟：
在父節(jié)點是紅色的前提下：如果叔叔節(jié)點是紅色被济，則父親和叔叔繼承爺爺?shù)暮谏却停瑢⒓t色節(jié)點上移到爺爺節(jié)點；如果叔叔節(jié)點是黑色只磷，則通過旋轉(zhuǎn)將父親上升為爺爺并交換父親和爺爺?shù)念伾酰辜t色轉(zhuǎn)移到爺爺節(jié)點。
刪除
按照正常二叉樹刪除钮追，然后進(jìn)行平衡预厌。
RB-DELETE-FIXUP(T, c)
1. while c != root[T] and color[x] = BLACK
2. do if c = left[p[c]] // c is left child
3. then s = right[p[c]]
4. if color[s] = RED // sibling is red
5. then <Case 1>
6. if color[left[s]] = BLACK and color[left[s]] = BLACK
7. then <Case 2> // both nephews are black
8. else if color[right[s]] = BLACK
9. then <Case 3> // right nephew is black
10. <Case 4> // right nephew is red
注釋：
- 循環(huán)判斷條件為自己不是根且顏色是黑色
- Case 1，兄弟為紅色元媚，則通過旋轉(zhuǎn)轧叽，讓兄弟變成黑色
- Case 2，侄子都是黑色刊棕，只好上移黑色節(jié)點炭晒。如果原父節(jié)點是紅色，則多余的黑色被吸收鞠绰。否則父節(jié)點轉(zhuǎn)化為新節(jié)點腰埂。
- Case 3，離自己近的侄子是紅色蜈膨，通過旋轉(zhuǎn)將紅色轉(zhuǎn)到離自己遠(yuǎn)的侄子
- Case 4屿笼，離自己遠(yuǎn)的侄子是紅色，通過旋轉(zhuǎn)將多余的黑色吸收
刪除操作的四種情況
嘗試歸納一下刪除過程的平衡步驟：
刪除的平衡操作在自身和兄弟及侄子之間進(jìn)行：如果兄弟不是黑色翁巍，則先把它變黑驴一；如果兄弟是黑色且兩個侄子也是黑色，則只能上移多余的黑色灶壶；如果兄弟是黑色且其中有一個侄子是紅色肝断，則能通過旋轉(zhuǎn)將多余的黑色吸收。
