[資演] 紅黑樹 deletion
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
→
01/13 21:57, , 1F
01/13 21:57, 1F
推
01/13 22:05, , 2F
01/13 22:05, 2F
推
01/13 22:09, , 3F
01/13 22:09, 3F
→
01/13 22:10, , 4F
01/13 22:10, 4F
推
01/13 22:10, , 5F
01/13 22:10, 5F
→
01/13 22:10, , 6F
01/13 22:10, 6F
推
01/13 22:23, , 7F
01/13 22:23, 7F
推
01/13 22:35, , 8F
01/13 22:35, 8F
推
01/13 22:36, , 9F
01/13 22:36, 9F
推
01/13 22:43, , 10F
01/13 22:43, 10F
→
01/13 22:46, , 11F
01/13 22:46, 11F
推
01/13 23:10, , 12F
01/13 23:10, 12F
推
01/14 01:07, , 13F
01/14 01:07, 13F
推
01/14 01:13, , 14F
01/14 01:13, 14F
推
01/14 01:15, , 15F
01/14 01:15, 15F
[紅黑樹]
*是棵平衡的樹: 保證從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)
推
01/14 08:22, , 16F
01/14 08:22, 16F
推
01/14 08:56, , 17F
01/14 08:56, 17F
推
01/14 13:20, , 18F
01/14 13:20, 18F