關於 個節點的二元紅黑樹，下列敘述，何者正確？
A與 n 對左右括號的合法括法的總數一樣多
Bn 個節點的二元紅黑樹其高度最高為 $2\log_{2}n + 2$正確答案
Cn 個節點的二元紅黑樹其高度最少為 $\log_{2} n + 2$
Dn 個節點的二元紅黑樹總數為 $O(n^{2})$
答案與詳解
逐選項解析
A與 n 對左右括號的合法括法的總數一樣多✕ 錯誤
n 對左右括號的合法括法總數為第 n 個卡特蘭數（Catalan number），這對應的是 n 個節點所能構成的「不同結構的二元樹」總數，而非受顏色規則限制的紅黑樹總數。
Bn 個節點的二元紅黑樹其高度最高為 $2\log_{2}n + 2$✓ 正確
根據紅黑樹性質，其黑高（black-height）$bh \le \log_{2}(n+1)$，且紅色節點不相鄰，故樹高 $h \le 2bh \le 2\log_{2}(n+1)$。選項給出的 $2\log_{2}n + 2$ 為數學上正確的放寬上界，故敘述正確。
Cn 個節點的二元紅黑樹其高度最少為 $\log_{2} n + 2$✕ 錯誤
Dn 個節點的二元紅黑樹總數為 $O(n^{2})$✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
