[資演] 紅黑樹 deletion

[jenny2921 (耶)]

deletion真是ㄐㄅ的要命 我終於弄懂了...以下為我整理的

希望能救到大家 (快稱讚我人很好,這我可是弄很久的耶!無私的分享給大家啊!!XDD)


我真的弄了很久Q_______________Q

=========
一些簡寫註記(怕大家看不懂)
1.r = red, 紅色
2.b = black, 黑色
3.bh = blackhight
4.n.c = n的child
5.n.p = n的parent
6.bx = 老師投影片上的x, 加上b代表黑色的
7.b1,b2,... = 點1(black),點2(black)...
8.r1,r2,... = 點1(red),點2(red)...
9.w1 = 點1(white:不限定為紅或黑)
9.stuvwy = 不重要的子樹們
10.(1,w1,2) = w1左邊的黑值=1,w1右邊黑值=2
=========
delete(n):

1.沒有手/沒有child/degree=0/是leaf => 直接拿掉n
  (1)n=r: color-OK, bh-OK
  (2)n=b: adjust(n.p.nil)
2.有一隻手/degree=1 => 把n.child接到n.parent
  (1)n=r: color-OK, bh-OK
  (2)n=b: adjust(n.c)
3.有兩隻手 => 取左手最大(或右手最小)的點y來補, y變成n的顏色
  (1)y=r: color-OK, bh-OK
  (2)y=b: adjust(y.c) <y沒有手:y.c=nil / y有左手(右手):即為y.c>
=========
adjust(bx): [bx: x現在是b但x處還缺一個b / x處有2個b ]

1.bx=r: bx直接由r變b,return

2.bx=root: return

3-1.紅弟弟(爸爸必為黑):弟弟轉到爸爸位置,爸爸由黑變紅,弟弟紅變黑,繼續adjust(bx)
   b1            b2
  /  \          /  \
 bx   r2       r1   v
/  \ /  \     /  \
s  t u  v    bx  u
            /  \
            s  t
<uv值2黑,bx值1黑,st值0黑>
(1,b1,2) => (1,r1,2) => 繼續處理bx

3-2.黑弟弟+2個黑姪子/nil(爸爸顏色不定):弟弟由黑變紅,往上:adjust(w1)
    w1               w1
   /  \             /  \
 bx    b2         bx    r2
/  \  /  \       /  \  /  \
s  t b3   b4     s  t b3   b4
    /  \ /  \        /  \ /  \
    u  v w  y        u  v w  y
<bx值1黑;stuvwy值0黑>
(1,w1,2) => (1,w1,1),但w1以下全部少1黑 => 往上處理w1

3-3.黑弟弟+與弟弟同一邊的姪子黑+另一邊姪子紅:黑弟弟轉向黑姪子,弟弟黑變紅,紅姪
子紅變黑,繼續adjust(bx)
    w1               w1
   /  \             /  \
 bx    b2         bx    b3
/  \  /  \       /  \  /  \
s  t r3   b4     s  t  u   r2
    /  \ /  \             /  \
    u  v w  y             v  b4
                            /  \
                            w  y
<bx,u,v值1黑;stwy值0黑>
(1,w1,2) => (1,w1,2) => 繼續處理bx

3-4.黑弟弟+與弟弟同一邊的姪子紅+另一邊不重要:爸爸往你的方向轉下來,紅爸爸變黑,
紅姪子變爸爸原本的顏色,黑弟弟變紅
    w1                w3
   /  \              /  \
 bx    b3          b1    b2
/  \  /  \        /  \  /  \
s  t  u   r2     bx  u  v  w
         /  \   /  \
         v  w   s  t
<bx,u,v,w值1黑;st值0黑>
(1,w1,2) => (1,b1,1),(2,w3,2) => 終於adjust完了!!Q____Q
=============
範例: http://web.ncyu.edu.tw/~wangch/course/991/al/noterb2.pdf


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.30.143
→ jenny2921:如果推文超過10,我就把我所有紅黑樹的整裡都貼上來!!!
推 rod13824:先推一下
推 LesMiserable:http://gauss.ececs.uc.edu/RedBlack/redblack.html
→ LesMiserable:可以用這個網頁的applet試著加node減node,看怎麼變化
推 andy74139:整理好多噢!!推推!!
→ LesMiserable:不過還是要推一下,Jennya超認真! (大拇指)
推 peteranny:雖然是單班 但推jennya人超好!!XDD
推 ilovejun:推囉XD
推 mikein125:人真好XDD
推 rock1246:謝謝!
→ k1923456:雖然我是單班得可以我還想看~~推一下
推 s864372002:布魯斯推推~