※ 引述《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