資料結構›Ch5 樹狀結構
第 19 題/共 48 題
◀ DS 19/48
19. Order Statistic Tree、Augmented BST、OS-SELECT
#DS-05-019易Order Statistic TreeAugmented BSTOS-SELECT
  1. (4%) A binary search tree can be augmented for specialized applications such as an order statistic tree. The provided pseudo-code is an implementation of the OS-SELECT function, which retrieves the ii-th smallest element in the set represented by the binary search tree. The variable xx represents a node in the tree and initially points to the root when the function is called. As the function recurses, xx updates to reflect the current node being processed. Your task is to fill in the missing part of the pseudo-code in line 1.
OS-SELECT(x, i)
1   r ← ______
2   if i = r
3       then return x
4   else if i < r
5       then return OS-SELECT(left[x], i)
6   else return OS-SELECT(right[x], i - r)
📄 交大114
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch5 樹狀結構
本章題號 · 1–20 / 48