資料結構›Ch9 進階樹第 3 題／共 88 題
3. Red-Black Tree、Order Statistics、Augmented Data Structure
#DS-09-003易Red-Black TreeOrder StatisticsAugmented Data Structure
Consider a red-black tree augmented for dynamic order statistics by storing, at each node , the attribute = number of nodes in the subtree rooted at , including itself. Which of the following statements is correct?
參考答案與解析
答案 (B)：旋轉時，只有牽涉旋轉的那兩個節點的子樹關係改變了，用「原本的兩個子節點大小」就能在 O(1) 內重新算出這兩個節點各自的新 size，這是增強型紅黑樹旋轉更新 size 欄位的標準做法。(A) 錯：旋轉也需要更新 size（不只插入路徑）。(C) 錯：SELECT(i) 可以用迭代（非遞迴）方式實作，額外空間 O(1) 即可。(D) 錯：size 欄位是獨立附加資訊，不會影響紅黑樹本身的著色規則。(E) 錯：重複鍵值只要有一致的排序慣例，仍可以正確支援 SELECT(i)。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch9 進階樹