[理工] red-black tree

[patabon (啪打嘣)]

Question:

In a red-black tree , the number of rotations for one insertion is Θ(1)

in the worst case. (T/F)


答案是寫True.

我是想問如果在worst case下旋轉數也只要常數次的話，那為什麼insetion的複雜度

會是O(logn)呢?



另外是想問關於red-black tree之定義，有些書上寫其leaf必為black，

因為它都將failure node納入考量，則leaf就必為black，但就我目前做過的題目

其解答大部分都是只以有key值之node做討論，也就是leaf可為red，這又與定義衝突，

關於這方面該如何抉擇解題方向呢?

又如果題目直接問是否leaf必為black又該如何答?


定義一套，解題又一套搞得我好亂啊....

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.104.40
※ 編輯: patabon         來自: 220.137.104.40       (01/01 18:04)
推 A4P8T6X9:log n是因為要從上面往下找到適合的位子 O(h)。
→ A4P8T6X9:如果是我，我會寫F，因為是NIL或是failure node才都是黑
→ patabon:瞭解了，感謝樓上