→ yesa315:謝謝! 10/01 09:45
※ 引述《yesa315 (XD)》之銘言：
: http://www.lib.ntu.edu.tw/exam/graduate/98/98404.pdf
: 附上台大考題
: 其中第4題的紅黑樹 把連續的紅節點稱為 red-red conflict
: 接下題目就有點混亂了 看不太懂 問說 紅節點的父點啥不存在
: 什麼的
: 請高手指導
: 謝謝
題目意思是說 在 RBT 的插入演算法中，我們每插入一個 node (Red)
就去檢查 會不會形成所謂的 "Red-Red conflict"
如果不幸發生了 此時新 node 的 grand parent 必存在(且為 Black)
要你解釋為什麼這個新 node 的 grand parent 一定會存在 ?
(一) 插入在 root : 不可能有 Red-Red conflict
(二) 插入在 Red Node Q : 則這個新 node 必有一個 grand parent
因為 Q 不為 root 故 Q 必有 parent P
則 P 即為新 node 的 grand parent
若 P 為 root 則 P 必為 Black(基本性質)
若 P 非 root 則 在插入新 node 以前 , 這棵 RBT 滿足基本性質 ,
P 與 Q 不可能同時為 Red 故 P 必為 Black
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.222.93