紅黑樹(shù)圖
Java在實(shí)現(xiàn)TreeMap中用到了紅黑樹(shù)，在此記錄自己的理解。
定義
紅黑樹(shù)是二叉搜索樹(shù)的一種實(shí)現(xiàn)方式，任意一條到葉結(jié)點(diǎn)的路徑不會(huì)比其他路徑長(zhǎng)出2倍。
性質(zhì)
紅黑樹(shù)一共有5點(diǎn)性質(zhì)：
- 每個(gè)結(jié)點(diǎn)是紅色或者黑色的
- 根結(jié)點(diǎn)是黑色的
- 葉結(jié)點(diǎn)是黑色的
- 如果一個(gè)結(jié)點(diǎn)是紅色的，那么它的兒子結(jié)點(diǎn)都是黑色的
- 每一個(gè)結(jié)點(diǎn)到其葉結(jié)點(diǎn)的所有路徑中，黑色結(jié)點(diǎn)的個(gè)數(shù)相同
紅黑樹(shù)的一個(gè)結(jié)點(diǎn)如果沒(méi)有兒子，那么它將指向一個(gè)NIL結(jié)點(diǎn)，該NIL結(jié)點(diǎn)為葉結(jié)點(diǎn)。同理，根結(jié)點(diǎn)的父親也指向NIL結(jié)點(diǎn)。NIL結(jié)點(diǎn)為黑色的，其left、right、p、key可以為任何值。
為了便于在紅黑樹(shù)執(zhí)行增加或刪除操作時(shí)的邊界處理，使用一個(gè)哨兵結(jié)點(diǎn)T.nil代表NIL。
操作
一個(gè)二叉樹(shù)的基本操作有增加、刪除和查詢(xún)。紅黑樹(shù)的基本操作時(shí)間復(fù)雜度為O(lgn)。為了保證紅黑樹(shù)進(jìn)行增加或刪除操作后仍然保持其性質(zhì)，需要在基本操作之后進(jìn)行處理，使其滿(mǎn)足特性。
旋轉(zhuǎn)
旋轉(zhuǎn)是修改紅黑樹(shù)結(jié)構(gòu)的一種方法。
增加
往紅黑樹(shù)中增加一個(gè)結(jié)點(diǎn)z，z結(jié)點(diǎn)被設(shè)為紅色，并且占據(jù)了原某一葉子結(jié)點(diǎn)的位置。由于在加入z結(jié)點(diǎn)之前紅黑樹(shù)滿(mǎn)足性質(zhì)，在加入z結(jié)點(diǎn)后，樹(shù)可能不滿(mǎn)足的性質(zhì)為性質(zhì)4，即出現(xiàn)某一紅色結(jié)點(diǎn)的兒子仍為紅色結(jié)點(diǎn)。此時(shí)需要處理該紅色z結(jié)點(diǎn)，主要方法為在滿(mǎn)足其余性質(zhì)的情況下，不斷將紅色上移（不是移動(dòng)結(jié)點(diǎn)，而是不斷更改相鄰結(jié)點(diǎn)的顏色），直到根結(jié)點(diǎn)為紅色，將根結(jié)點(diǎn)變?yōu)楹谏蛘咴谀骋徊缴弦浦?，紅色移動(dòng)到了滿(mǎn)足所有性質(zhì)的位置。
當(dāng)z結(jié)點(diǎn)的父親結(jié)點(diǎn)為黑色時(shí)，不存在不滿(mǎn)足的性質(zhì)，以下討論z結(jié)點(diǎn)的父親為紅色時(shí)的情況。我們不妨另z為其父結(jié)點(diǎn)的左兒子，對(duì)于z為其父結(jié)點(diǎn)右兒子的情況，可以通過(guò)旋轉(zhuǎn)將其變?yōu)樽髢鹤印?/p>
假設(shè)z.p=z.p.p.left，另一種情況與此相似。此時(shí)只需要按照z.p.p.right，即z的叔結(jié)點(diǎn)的顏色進(jìn)行分類(lèi)討論即可。
-
叔結(jié)點(diǎn)為紅色
叔結(jié)點(diǎn)為紅色.png
將z.p和z.p.p.right變?yōu)楹谏?，將z.p.p變?yōu)榧t色。經(jīng)過(guò)上述操作后，原z結(jié)點(diǎn)滿(mǎn)足性質(zhì)4，另z'=z.p.p，繼續(xù)以處理z的方式處理z'。
-
叔結(jié)點(diǎn)為黑色
增加_叔結(jié)點(diǎn)是黑色.png
將z.p.p設(shè)為紅色，將z.p設(shè)為黑色，將z.p.p進(jìn)行左旋轉(zhuǎn)。這里對(duì)p結(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)后，由于q結(jié)點(diǎn)不再是z的父輩結(jié)點(diǎn)，導(dǎo)致z路徑上的黑色結(jié)點(diǎn)減少一個(gè)，將p變?yōu)楹谏鬂M(mǎn)足，此時(shí)滿(mǎn)足性質(zhì)4，完成處理。
刪除
紅黑樹(shù)的刪除基于TRANSPLANT操作，以下為其實(shí)現(xiàn)。
RB-TRANSPLANT(T,u,v)
if(u.p==T.nil)
T.root=v
else if u==u.p.left
u.p.left=v
else
u.p.right=v
v.p=u.p
在紅黑樹(shù)上刪除一個(gè)結(jié)點(diǎn)z后，我們用其子樹(shù)上的y結(jié)點(diǎn)連接z的父結(jié)點(diǎn)，并將y結(jié)點(diǎn)的顏色設(shè)為與z結(jié)點(diǎn)相同，這里需要分類(lèi)討論z的兒子結(jié)點(diǎn)個(gè)數(shù)。
-
當(dāng)左兒子為NIL時(shí)，y結(jié)點(diǎn)為z的右兒子。
刪除_左左兒子為nil.png -
當(dāng)右兒子為NIL時(shí)，y結(jié)點(diǎn)為z的左兒子。
刪除_右兒子為nil.png -
當(dāng)左、右兒子均不為NIL時(shí)，y結(jié)點(diǎn)為樹(shù)中比z結(jié)點(diǎn)大的最小結(jié)點(diǎn)，即z結(jié)點(diǎn)右子樹(shù)中的最小結(jié)點(diǎn)。
刪除_左右兒子非nil.png
在第1或第2的情況下下，如果z結(jié)點(diǎn)為黑色，將y放置到z的位置后，y父輩到葉結(jié)點(diǎn)的路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)減一；或者情況3下y結(jié)點(diǎn)為黑色，將y放置到z的位置后，y的右兒子的父輩到葉結(jié)點(diǎn)的路徑到上的黑色結(jié)點(diǎn)個(gè)數(shù)減一。為了保證紅黑樹(shù)的性質(zhì)5，我們暫時(shí)增加該結(jié)點(diǎn)（情況1、2為y結(jié)點(diǎn)，情況3為x結(jié)點(diǎn)）的“黑色的程度”，即計(jì)算路徑上的黑色結(jié)點(diǎn)時(shí)多計(jì)算一次該結(jié)點(diǎn)的黑色次數(shù)。
我們處理該多余黑色次數(shù)的主要辦法與之前的方法相似，不斷將該黑色次數(shù)上移，直到遇到一個(gè)紅色結(jié)點(diǎn)，將其變?yōu)楹谏驅(qū)⒑谏螖?shù)上移到根節(jié)點(diǎn)再清除。
統(tǒng)一另增加了黑色程度的結(jié)點(diǎn)為x，不妨令x=x.p.left，對(duì)于x=x.p.right的情況與之相似。
- x結(jié)點(diǎn)為紅色
只需要將x結(jié)點(diǎn)變?yōu)楹谏?，即可使?shù)滿(mǎn)足性質(zhì)5。 -
x結(jié)點(diǎn)為黑色，x兄弟結(jié)點(diǎn)w為紅色（此時(shí)x的父結(jié)點(diǎn)為黑色）
將x.p設(shè)為紅色，將x兄弟結(jié)點(diǎn)w設(shè)為黑色，并對(duì)x.p進(jìn)行左旋轉(zhuǎn)，即可通過(guò)下面的分類(lèi)進(jìn)行處理。
刪除_case2.png -
x結(jié)點(diǎn)為黑色，x兄弟結(jié)點(diǎn)w為黑色，且w的兒子均為黑色
將x多余的黑色次數(shù)上移給x.p，并將w結(jié)點(diǎn)設(shè)為紅色。令x'=x.p，繼續(xù)循環(huán)。
刪除_case3.png -
x結(jié)點(diǎn)為黑色，x兄弟結(jié)點(diǎn)w為黑色，且w左兒子為紅色，w右兒子為黑色
將w設(shè)為紅色，w左兒子設(shè)為黑色，對(duì)w進(jìn)行右旋轉(zhuǎn)，使用下面的分類(lèi)進(jìn)行處理。
刪除_case4.png - x結(jié)點(diǎn)為黑色，x兄弟結(jié)點(diǎn)w為黑色，且w右兒子為紅色
-
若x.p為黑色，x.p左旋轉(zhuǎn)，消除黑色次數(shù)
刪除_case5_1.png -
若x.p為紅色，x.p設(shè)為黑色，w設(shè)為紅色，x.p左旋轉(zhuǎn)，消除黑色次數(shù)
刪除_case5_2.png
