卷別

資料結構與演算法

選擇

國立臺灣大學 2026 · 考試 · 第 20 題

(4 points) Consider a red–black tree augmented for dynamic order statistics by storing, at each node $x$ , the attribute

$x.\texttt{size} = \text{number of nodes in the subtree rooted at } x, \text{ including } x \text{ itself.}$

Which of the following statements is correct?

(A)
During insertion, the size field needs to be updated only along the path from the root to the inserted node; rotations do not require any update to size.
(B)
During a left or right rotation, the size fields of exactly two nodes can be recomputed in $O(1)$ time using their children's sizes.
(C)
The $\textsc{Select}(i)$ operation (finding the $i$ -th smallest key) requires $O(\log n)$ extra space due to recursion.
(D)
Maintaining the size field may violate the red–black tree properties and thus requires additional recoloring rules.
(E)
The presence of duplicate keys makes it impossible to support $\textsc{Select}(i)$ correctly using subtree sizes.

標準解析

AI 已複查