0. 導論

比賽在我們生活中無時無刻都存在. 在學生時代, 不論是小學, 中學還是大學, 大家可能在學校中或者在社會上都會參加甚至組織一些比賽. 在一個國家或者在整個世界上, 也有不少的比賽, 例如奧運會, 世界盃或者一些聯賽. 我們首先來看一張關於比賽的圖 :

這是一張取自於 Google 的 2018 年世界盃足球賽四分之一決賽至決賽的對戰表, 最終的冠軍是法國. 我們簡化一下上面這張圖 :

以上對戰表中的顏色僅用於區分, 沒有其它意義.

我們發現, 這個對戰表實際上是一棵滿二元樹, 或者說是一棵完全二元樹. 更一般地, 如果有若干個選手, 每一組至少一人, 至多兩個人, 這些選手通過比賽決出一個勝者進入下一輪, 直到最後剩下一個勝者, 我們就得到了這一場比賽的冠軍. 以此為例, 我們可以畫處一棵樹, 而這棵樹也被稱為贏者樹.

1. 定義

定義 1. (競賽函數) 設有一函數 f, 對於任意 k 個變數 x_{1}, x_{2}, ..., x_{k}, f 可以從這 k 個變數中選中一個變數 x_{i}, 使得這 k 個變數中有且唯有 x_{i} 滿足某一條件 C, 即 \displaystyle {f(x_{1}, x_{2}, ..., x_{k}) = x_{i}\ (x_{i}\ \text {滿足條件}\ C, x_{j}\ \text {不滿足條件}\ C, i \neq j)} 其中, i = 1, 2, ..., k, j = 1, 2, ..., k, i\neq j. 那麼我們稱函數 f競賽函數.

定義 2. 設有一棵 k 元樹 T, f 是某一競賽函數, 記 e(n) 表示節點 n 中的元素, 來自 T 的非葉子節點 x 的子節點表示為 x_{1}, x_{2}, ..., x_{j}\ (j \leq k). 若對於任意 x, 總有 e(x) = e(x_{i}) =  f \left (e(x_{1}), e(x_{2}), ..., e(x_{j}) \right )\ (i = 1, 2, ..., j), 那麼我們稱這棵 k 元樹為受限於競賽函數 fk 元贏者樹, 簡稱為 k 元贏者樹. 其中, k \geq 2. 我們稱這棵樹的根節點為冠軍.

一般來說, 我們用得比較多的是 k = 2 的情形, 即二元贏者樹. 因此, 通常我們將二元贏者樹也簡稱為贏者樹.

例題 1. 設競賽函數 f 滿足 \displaystyle {f(x_{1}, x_{2}) = \begin {cases} x_{1} & {x_{1} \geq x_{2}} \\ x_{2} & {x_{1} < x_{2}} \end {cases}\ \text {且}\ f(x) = x}, 判斷下面的二元樹是否為贏者樹.

:

為了方便區分, 我們記 E(N) 表示節點 N 中的元素. 例如 E(a) = 20.

對於 j 節點, 有 E(j) = E(b) = f \left (E(a), E(b) \right ); 對於 k 節點, 有 E(k) = E(d) = f \left (E(c), E(d) \right ); 對於 l 節點, 有 E(l) = E(e) = f \left (E(e), E(f) \right ); 對於 m 節點, 有 E(m) = E(h) = f \left (E(g), E(h) \right ); 對於 l 節點, 有 E(n) = E(i) = f \left (E(i) \right ); 對於 o 節點, 有 E(o) = E(j) = f \left (E(j), E(k) \right ); 對於 p 節點, 有 E(p) = E(m) = f \left (E(l), E(m) \right ); 對於 q 節點, 有 E(q) = E(n) = f \left (E(n) \right ); 對於 l 節點, 有 E(r) = E(o) = f \left (E(o), E(p) \right ); 對於 s 節點, 有 E(s) = E(q) = f \left (E(q) \right ); 對於根節點 t, 有 E(t) = E(r) = f \left (E(r), E(s) \right ).

對於任意非葉子節點 x, 都滿足定義 2, 因此上面這棵樹是贏者樹.

\blacksquare

還有一種關於贏者樹的定義要求更加嚴格一些, 這個定義不但要求這棵樹滿足定義 2, 而且要求這棵樹必須是完全二元樹. 此時, 關於定義 2 中的 j \neq k 的情況就只有最後一個節點的父節點才有可能滿足, 對於剩餘的非葉子節點是不可能出現這種情況的, 否則這棵樹就不是一棵完全二元樹. 而這一種定義除了增加了贏者樹的複雜性之外, 我還沒有找到任何其它意義.

2. 比賽

為了建構一棵贏者樹, 所有元素必須進行比賽, 直到最後決出一個冠軍才結束. 而比賽非常簡單, 就是對於任意的 f, 給定 n 個元素, 以 k 個元素為一組, 判斷 f \left (e(x_{p}), e(x_{p + 1}), ..., e(x_{p + j}) \right ) 的值, 然後讓以 f \left (e(x_{1}), e(x_{2}), ..., e(x_{j}) \right ) 為元素的節點作為節點 x_{1}, x_{2}, ..., x_{j} 的父節點即可. 其中, j \leq kp \div k \in \mathbb {Z}. 當這 n 個元素比賽完畢形成了新的一層父節點之後, 這新一層的父節點繼續以 k 個一組進行比賽, 直到父節點只有一個, 也就是只剩下根節點一個為止.

定理 1. 給定 n 個元素進行受限於函數 f 的比賽, 若函數 f 的計算時間是常數的, 那麼由這 n 個元素建構一棵贏者樹的時間複雜度為 \Theta(n).

證明 :

如果這棵贏者樹同時是滿二元樹, 根據《【資料結構】樹 – 二元樹》中的定義 2, 若它有 k 層, 那麼總共有 2^{k} - 1 個節點, 最後一層葉子節點的數量為 2^{k - 1} 個. 也就是說, 如果給定 n 個元素並建構了一棵贏者樹, 這棵贏者樹同時還是滿二元樹, 那麼其共有 \log_{2} {n} + 1 層, 贏者樹也就總共有 2n - 1 個節點. 由於函數 f 的計算時間是常數 \Theta(1) 的, 換句話說, 建構的時間複雜度為 O(2n - 1) = O(n). 而非滿二元樹的節點數量只會比滿二元樹中的節點數量少, 因此它的時間複雜度不會比 O(n) 高. 但是, 建構至少要尋訪所有給定的 n 個元素, 因此它的時間複雜度同時為 \Omega(n). 綜上所述, 給定 n 個元素建構二元贏者樹的時間複雜度為 \Theta(n).

\blacksquare

3. 更換選手

更換選手在贏者樹中是比較常見的, 我們很可能因為某些原因需要更換某個節點中元素的值. 然而, 更換之後, 我們不需要重新建構贏者樹, 只需要對更換元素所在的組重新進行比賽, 比賽至根節點就可以了. 當然, 有些時候不需要比賽到根節點, 例如在某一次比賽中, 新的元素比不過父節點導致輸掉比賽, 那麼從這一層開始, 上面所有節點的不再需要更新. 因此, 一次更換選手的時間複雜度為 \Theta(\log {n}).

4. 輸者樹

我們很容易可以想到, 和贏者樹相互對應的是輸者樹, 確實存在這樣的樹. 輸者樹是二元樹, 父節點中的元素記錄的是子節點比賽之後輸的那一個. 相比於贏者樹來說, 在輸者樹中更換作為贏者的選手, 更換的時間複雜度是 \Theta(1) 的. 因為父節點記錄的是輸者, 因此根本不需要在更換選手所在組重新進行比賽.

現在我們要講述為什麼輸者樹都是二元樹的原因. 如果有一個函數 f, 它可以從 k 個節點中選取輸者, 以函數 f 作為競賽函數的輸者樹根據定義 2, 同時也是一棵贏者樹, 只是函數 f 計算方向不同罷了. 因此, 為了區分贏者和輸者的區別, 我們特別認為二元的樹才能體現輸者這一特性, 故輸者樹也都是二元樹.

不過在實際應用中, 輸者樹只是更換選手中的贏者時, 時間複雜度低而已, 應用範圍並不多. 因此在程式碼編寫的時候, 若某個贏者樹的競賽函數為 f, 其反向計算 (也就是計算輸者) 的競賽函數為 f^{-1}, 我們也把受限於 f^{-1} 的贏者樹作為輸者樹來使用.

5. 插入與刪除

給定 n 個元素, 如果要插入一個元素, 那麼從插入位置所在的組開始, 接下來的組都要重新比賽. 以例題 1 中的贏者樹為例, 我們接下來使用灰色的節點表示需要重新比賽的節點. 向 08 之間插入 5 後, 0 所在的這一組開始, 都要重新比賽 :

如果從中刪除一個元素也是類似, 從刪除元素所在的這個組開始, 接下來的組都要重新比賽.

不過刪除還有另外一種方法, 對於 k 個節點 x_{1}, x_{2}, ..., x_{k}, 如果要刪除 x_{i}\ (i = 1, 2, ..., k), 我們只需要修改 x_{i} 中的元素為競賽函數 f 永遠不會選中的值即可. 例如競賽函數 fk 個節點中選出最小的數, 那麼我們只需要令 x_{i} = \infty 即可.

從 C++ 的角度來說, 給定 n 個元素, 建構一棵贏者樹, 我們有兩種方法 :

  • 一次性配置適應 n 個元素大小的記憶體 : 但是從程式碼效能的角度來說, 這種配置方法是不利於插入和刪除的. 即時一次性申請足夠多的記憶體, 我們需要額外的一個整數來標記目前使用了多少個元素, 以計算還剩下多少元素可以使用. 一旦配置的記憶體都被用完, 就需要重新申請記憶體, 從原記憶體中把選手都移動或者複製過來. 雖然部分路徑無序重新比賽, 其父節點仍然可以直接使用, 但是父節點如果也是採用一次性適應性配置的話, 這就導致原本可以復用的父節點也無法再復用;
  • 按照樹的配置方式, 單次配置 : 在這種配置方式下, 插入和刪除會比一次性適應性配置要快, 但是在建構的時候就比一次性適應性配置要慢了.

因此, 具體使用哪一種方法進行建構, 必須要考慮插入和刪除可能的此數.

6. 外部排序

我們之前已經說了不少排序演算法, 其中部分排序演算法的時間複雜度達到了排序複雜度的下限 \Omega(n\log {n}). 但是在現代電腦中, 所有的資料都要讀入記憶體 (包含暫存器以及 CPU 緩存) 之後才能配合 CPU 進行運算, 那麼在記憶體受限的裝置上, 我們可能無法一次性在記憶體中完成排序. 例如記憶體一次性可以讀入十萬個元素, 但是我們有一百萬個元素需要排序. 這個時候, 我們可以對這一百萬個元素進行劃分, 分成 10 部分, 每份十萬個元素. 然後對著十萬個元素使用類似於快速排序, 合併排序或者堆積排序進行排序, 將排序之後的資料儲存在記憶體之外 (外部儲存). 接下來, 我們建立選手為 10 個元素的贏者樹, 這些選手分別從 10 份已經排好序的十萬個元素中位於頭部的元素 (通常是最大的元素或者最小的元素). 建立贏者樹之後, 每次從頭部取出一個元素, 這個元素必定是這 10 個選手元素中最大或者最小的那一個, 假定這個元素來源於第 k 個部分, 接下來只需要從第 k 個部分再取出一個元素即可. 因為每一個部分的元素都是有序的, 因此當贏者樹某個元素被取出, 用於替補的元素只需要順序地從那個部分取出放入贏者樹對應的位置即可.

7. 實作

資料結構 winner_tree : GitHub 點擊直達

資料結構 loser_tree : GitHub 點擊直達