紅黑樹 Michael Tsai 200/2/3 200 最後一堂資料結構課
2 Happy New Year 作業六 ( 最後一個作業, 耶 ) 上線 期末考前 due ( 跟助教會再討論 ) 期末考方式討論 (close book, 2 A4 雙面大抄 ) 範圍 : 全部 ( 第一堂課到最後一堂課 )
3 紅黑樹 可以幹嘛? 是棵平衡的樹 : 保證從 root 到某個 leaf 的 simple path 一定不會超過從 root 到任何一條其他這樣的 path 的兩倍長 大概平衡 operation 可以都在 O(log n) 內完成. 耶. 那些 operation?. 找 2. 插入某 element 3. 殺掉某 element 4. 找最大 or 找最小 element
4 紅黑樹 每個 node 都分配一個顏色 : 紅或黑 使用 extended binary tree: 沒有 children 的地方都補上 external node, 又叫 規則們 :. 每個 node 不是黑就是紅 2. root 是黑色的 3. 每個 leaf (external node, or ) 都是黑色 4. 如果一個 node 是紅的, 則它的 children 都是黑的 5. 對每個 node 來說, 從它到他的所有子孫葉子 node 的路徑上含有一樣數目的黑色 node
5 黑高度 Black height: bh(x) = 從 x 到任何一個它的子孫葉子 node 遇到的 black node 個數 ( 因為都一樣, 所以可以是任何一個 ) 不包含 node x 自己 external node 或 ( 葉子 node) 的 black height 為 0
巨大的紅黑樹例子 26 7 4 47 30 35 39 38 28 4 2 0 6 9 23 20 5 2 7 3 2 2 3 2 3 2 2 bh(x) 們 6
7 巨大的紅黑樹例子 3 bh(x) 們 7 3 26 4 2 2 0 2 4 2 2 6 9 23 28 2 30 38 47 7 2 5 20 35 39 3
8 來點證明 定理 : 一個有 n 個 node 的紅黑樹, 最高為 2 log(n+) 第一步驟 : 證明 node x 底下的 subtree 最少有 2 個 internal node 歸納法證明 :. 當 x 的 height 為 0, 則 x 是個葉子. bh(x)=0. 2 0. 的確 subtree 有 0 個 internal node. 2. 假設當 x 的 height 為正整數, 且是一個有兩個 children 的 internal node. 每個小孩的 black height 為 bh(x) or bh(x). ( 看該小孩是黑是紅 ) 假設小孩的 subtree 都至少有 2 個 internal node 3. 則 x 底下的 subtree 應該有 2 2 2 ( 成功了!)
9 來點證明 4. 如果一個 node 是紅的, 則它的 children 都是黑的 另外一種解釋 : 從任一 node 到 leaf, 至少一半以上的 node 是黑的 假設 h 是 tree 的高度, 則 node x 底下的 subtree 最少有 2 個 internal node 第二步驟 : root 底下至少有多少個 node? root 底下最少有 2 2 個 node. 假設 node 個數為 n, 則 2 2log. 耶.
0 以上證明 說明為什麼. 找 4. 找最大 or 找最小 element 等 operation 可以在 O(log n) 內完成 那麼 insert 和 delete 呢? 問題 : 插入或殺掉之後, 可能不滿足紅黑樹的條件
Representation parent color data left right
2 Rotate 等一下會用到的 y left rotate(t,x) x x right rotate(t,y) y
3 Insertion 首先, 用原本的 binary search tree 插入的方法 insert(z) 不同的地方 :. z 的兩個 children 都指到 node 2. z 為紅色 3. 我們最後要處理不符合紅黑樹規則的部分 怎麼處理?
4 會違反那些規則呢? 7 規則們 :. 每個 node 不是黑就是紅 2. root 是黑色的 3. 每個 leaf (external node, or ) 都是黑色 4. 如果一個 node 是紅的, 則它的 children 都是黑的 5. 對每個 node 來說, 從它到他的所有子孫葉子 node 的路徑上 含有一樣數目的黑色 node 5. 不會違反因為 z 是紅的, z 取代掉一個, 而 z 的兩個 children 都是 如果違反 2, 則 z 是 root, 整棵樹只有 z: 很容易處理 來看違反 4 的情形 : z s parent is also red
5 情形一 : 你的叔叔是紅的 你是你爸右邊的小孩 繼續看新 z 爸爸是不是紅的 parent(z): 你爸 A C D y: 叔叔 A C D B z: 你 B z: 你
6 情形一 : 你的叔叔是紅的 你是你爸左邊的小孩 parent(z): 你爸 C y: 叔叔 C A B D z: 你 A B D z: 你 注意看每一個步驟是否有保持紅黑樹第五個條件
7 情形二與三 : 你的叔叔是黑的 parent(z): 你爸 A C y: 叔叔 left rotate(a) parent(z): 你爸 B C y: 叔叔 B z: 你 z: 你 A right rotate(c) 你是你爸右邊的小孩 你是你爸左邊的小孩 B 注意看每一個步驟是否有保持紅黑樹第五個條件 z: 你 A C 需要繼續往上層看嗎? 不用! 因為 B 還是黑的!
8 黑板練習時間 3 7 3 26 4 2 2 0 2 4 2 2 6 9 23 28 2 30 38 47 7 2 5 20 35 39 3. 加入 40? 2. 加入 4?
9 要花多少時間呢? 原本正常的 binary tree insert 要花 O(log n) 的時間 因為高度最高為 2 log(n+) 那麼花費在調整的時間呢? 最糟的狀況? 情形一一直重複發生, 每次 z 往上移兩層 執行時間最糟要花跟高度成正比的時間 也是 O(log n) 那如果發生情形二 or 三呢? 執行一次即完成. O(). ( 所以比 O(log n) 小 ) 另外, 最多 rotate 只需要執行兩次. ( 不會再發生第二次情形二 or 三 )
如何刪掉一個 node? (binary search tree 複習 ) 首先要先找到那個 node 接著, 有各種不同情形 : 20 20 如果沒有手 (degree=0) 直接拿掉 0 5 2 22 25
如何刪掉一個 node? (binary search tree 複習 ) 如果只有一隻手 (degree=) 則把那個唯一的 child 拿上來接到 parent 上 20 2 例如 : 拿掉 22 2 22 0 5 25 問題 : 要怎麼接? 怎麼記得 parent 是誰?
如何刪掉一個 node? (binary search tree 複習 ) 如果兩手都有東西呢? (degree=2) 20 22 例如刪掉 2 找左邊 child 底下最大的 ( 或者是右邊 child 底下最小的 ) 0 5 2 22 25 刪掉它並把它移到原本刪掉的位置 問題 : 那如果那個最大的底下還有 child 呢? 直接拿上來 ( 最多只會有左邊一隻手 ) 這時被移上去的 node 顏色改變成新位置原本 node 的顏色
23 拿掉一個 node, 什麼時候會違反規則? 假設前述三種情形中, 移動 ( 兩手都有 ) 或是刪除 ( 一隻手或沒有手 ) 的 node 為 y 當 y 為紅色 ( 原本的顏色 ), 移動或刪除會造成違反規則嗎?. black height 不會改變, 因為 y 是紅色 node 2. 會不會造成兩個紅色 node 是相鄰的呢? ( 父子 ) A. 如果 y 是被刪掉的, 因為它是紅的, 所以它的上下層都是黑的 不會有問題 20 y 2 22 0 5
24 拿掉一個 node, 什麼時候會違反規則? B. 如果 y 是被移動的, 假設 y 有 children 也是黑色的, 不會造成問題 3. y 如果是紅色, 它不會是 root. 所以也不會有造成違反 root 是黑色的規定 綜合以上三點, 只有當 y 為黑色時才會造成問題, 需要調整 20 2 22 0 5 25
25 可能違反規則的情形 當 y 是黑色的, 可能造成違反規則的有下列情形 :. y 是 root. y 刪掉以後, 它的一個 children 是紅色的, 變成了 root 2. y 原本的上下兩層都是紅色的, 移走或刪除以後變成兩個紅色相鄰 3. y 刪掉或移走以後, 造成 black height 不一致 ( 因為 y 是黑的 )
26 怎麼修正紅黑樹以符合規則呢? 假設 x 為移動到 y 位置的 node ( 如果忘記了的話, y 是被刪掉或被移動的 node) y 原本是黑的, 則 x 好像要 有兩個黑, 這樣 black height 才會正確 每次 x 都指到一個 兩個黑 的 node ( 或者也有可能是 紅與黑 ) 依序修正
27 情形一 : x 的弟弟是紅的 B change color of B and D and left rotate(b) D A x D w B E C E x A new w C 轉換成情形二 三 或四
28 情形二 : x 的弟弟是黑的 & 它的姪子們都是黑的 B new x B A x D w A D C E C E
29 情形三 :x 的弟弟是黑的 它的姪子們都是左紅右黑 變成 case 4 B C 和 D 顏色改變 right rotate(d) B A x D w A x C new w C E D E
30 情形四 : x 的弟弟是黑的 它的姪子右邊那一個是紅的 B B,D,E 顏色改變 left rotate(b) D A x D w B E C E A C new x=root
3 花費的時間 O(log n) 最糟的情形是情形二 每次往上移一層 最糟 O(log n) 其他情形都是 O()
32 Happy New Year 老師的叮嚀 不要爆肝 不要不睡覺 身體最重要 心情快樂最重要 明年再見 ~~~