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)