[理工] red-black tree
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)
推
01/01 18:24, , 1F
01/01 18:24, 1F
→
01/01 18:25, , 2F
01/01 18:25, 2F
→
01/01 19:09, , 3F
01/01 19:09, 3F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：