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 [紅黑樹] *是棵平衡的樹: 保證從root到某個leaf的simple path一定不會超過從root到任何其他 leaf的兩倍長 *operation可以都在O(log n)內完成 *operations: 1. 找 2. 插入某element 3. 殺掉某element 4. 找最大or找最小 element *使用extended binary tree: 沒有children的地方都補上external node, 又叫nil *規則們: 1.每個node不是黑就是紅 2.root是黑色的 3.每個leaf (external node, or nil)都是黑色 4.如果一個node是紅的, 則它的children都是黑的 5.對每個node來說, 從它到他的所有子孫葉子node的路徑上含有一樣數目的黑色node *Black height: bh(x) = 從x到任何一個它的子孫葉子node遇到的black node個數 (因為 都一樣, 所以可以是任何一個) / 不包含node x自己 / external node或nil(葉子node) 的black height為0 *一個有n個node的紅黑樹，最高為2log(n+1) 1.IN(x) >= 2^(bh(x))-1 (IN = internal node, IN(x)為x底下的IN,含x) (1)when h(x)=0, x is a leaf, bh(x)=0, IN(x)=2^0-1=0 (2)when h(x)>0, x has two children and x is an internal node, bh(x's child) = bh(x) <when child is red> or bh(x)-1 <when child is black>, 設IN(x's child) >= 2^(bh(x)-1)-1 (3)則IN(x) >= 2*{2^(bh(x)-1)-1}+1=2^(bh(x))-1 成立, 故得證 2.紅node的children必為黑 => 從任一node到leaf，至少有一半以上的node為黑 => bh(root) >= h/2 3.n=IN(root) >= 2^(bh(root))-1 >= 2^(h/2)-1 => 2log(底2)(n+1) >= h => h <= 2log(n+1) =>operation <1.找 4.找最大or找最小element> 可以在O(log n)內完成 * / / y left rotate(T,x) x / \ <= / \ x C => A y / \ right rotate(T,y) / \ A B B C *Insertion 1.用原本的binary search tree插入的方法 2.z的兩個children都指到nil node(nil is black) 3.z為紅色 4.處理不符合紅黑樹規則的部分: (1)不會違反規則們1.3.5.(不違反5.因為插入的是紅的取代掉一個黑nil,但紅點下又各 有2個黑nil) (2)若違反2.則表示整棵tree只有此node,將此node變黑即可. (3)若違反4.則表示此node's parent is red(紅爸爸) ===紅叔叔=== 叔叔和爸爸由紅變黑,爺爺由黑變紅,&繼續往上處理 ===黑叔叔=== <1>你跟你爸同一邊: 爸爸和爺爺轉,爸爸由紅變黑,爺爺由黑變紅,你還是紅的 <2>你跟你爸不同邊: 你跟你爸轉,你跟你爸還是一樣都紅色,再你跟你爺爺轉,你變黑 色,爺爺變紅色 5.最糟的狀況:紅叔叔一直重複發生,每次紅node往上移兩層, 執行時間最糟要花跟高度成 正比的時間= O(log n) 6.如果是黑叔叔的話: O(1) (因為最多只要rotate2次,不會重複發生) *Deletion ========= delete(n) 1.沒有手/沒有child/degree=0/是leaf => 直接拿掉n (1)n=r: color-OK, bh-OK (2)n=b: n=root: OK (tree will be empty) else: color-OK, bh-NOK, 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(x): [x: x現在是b但x處還缺一個b / x現在是r但x處還缺一個b ] 1.x=r: x直接由r變b,return //因為這邊少1個b的話,r變b剛剛好 //以下x皆為b,故以bx代稱 2.bx=root: return //因為在root地方b少1的話也沒差了 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 複雜度: O(3-2)=O(log n) / O(其他)=O(1) => O(log n) ※ 編輯: jenny2921 來自: 140.112.221.4 (01/14 03:05)