摘要訊息 : 一種用於描述競賽結果的樹.

0. 前言

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

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

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

本文的目錄可能影響前面章節的排版, 故本篇文章的目錄預設為隱藏不展開狀態, 需要閣下手動展開.

更新紀錄 :

• 2022 年 6 月 17 日進行第一次更新和修正.

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 為競賽函數 (competitive function).

定義 2. 設 f 是某一競賽函數, e(x) 表示節點 x 中的元素. 若樹 \mathcal {T} 中任意非葉子節點 x, 其子節點為 x_{1}, x_{2}, ..., x_{n}, 且 x 滿足 \displaystyle {f \big ( e(x_{1}), e(x_{2}), ..., e(x_{n}) \big ) = e(x_{i}) = e(x)}, 那麼我們稱 \mathcal {T} 為受限於競賽函數 f 的贏者樹 (winner tree dominated by competitive function f), 簡稱為贏者樹 (winner tree). 其中, i = 1, 2, ..., n. 我們稱 \mathcal {T} 的根節點為冠軍 (winner).

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

解 :

為了不引起混淆, 我們將定義 2 中表示節點 x 中元素的記號改為 E(x).

對於節點 j, 其滿足 E(j) = 30 = f \big ( E(a), E(b) \big ) = f(20, 30); 對於節點 k 其滿足 E(k) = 15 = f \big ( E(c), E(d) \big ); 對於節點 l, 其滿足 E(l) = 6 = f \big ( E(e), E(f) \big ) = f(6, -3); 對於節點 m, 其滿足 E(m) = 8 = f \big ( E(g), E(h) \big ) = f(0, 8); 對於節點 n, 其滿足 E(n) = 30 = f \big ( E(i) \big ) = f(30).

對於節點 o, 其滿足 E(o) = 30 = f \big ( E(j), E(k) \big ) = f(30, 15); 對於節點 p, 其滿足 E(p) = 8 = f \big ( E(l), E(m) \big ) = f(6, 8); 對於節點 q, 其滿足 E(q) = 30 = f \big ( E(n) \big ) = f(30).

對於節點 r, 其滿足 E(r) = 30 = f \big ( E(o), E(p) \big ) = f(30, 8); 對於節點 s, 其滿足 E(s) = 30 = f \big ( E(q) \big ) = f(30).

對於冠軍, 即根節點 t, 其滿足 E(t) = 30 = f \big ( E(r), E(s) \big ) = f(30_{r}, 30_{s}).

綜上所述, 二元樹 \mathcal {T} 的每一個非葉子節點都受限於競賽函數 f, 因此 \mathcal {T} 是贏者樹.

\blacksquare

還有一種關於贏者樹的定義要求更加嚴格一些, 這個定義不但要求這棵樹滿足定義 2, 而且要求這棵樹必須是完全二元樹. 而這一種定義除了增加了贏者樹的複雜性之外, 我還沒有找到任何其它意義.

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 k 且 p \div k \in \mathbb {Z}. 當這 n 個元素比賽完畢形成了新的一層父節點之後, 這新一層的父節點繼續以 k 個一組進行比賽, 直到父節點只有一個, 也就是只剩下根節點一個為止. 對於 k 個一組中的 k 如何取, 取決於最大子節點數量 m. 即如果樹是一棵 m 元樹, 那麼 k = m.

定理 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. 輸者樹

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

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

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

5. 插入與移除

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

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

不過移除還有另外一種方法, 對於 k 個節點 x_{1}, x_{2}, ..., x_{k}, 如果要移除 x_{i} (i = 1, 2, …, k), 我們只需要修改 x_{i} 中的元素為競賽函數 f 永遠不會選中的值即可. 例如把節點中的元素修改為 -\infty 或者 +\infty. 在選擇最大元素的贏者樹中, -\infty 永遠不會成為冠軍. 這樣, 插入操作也要進行響應的修改. 插入到指定組的時候, 要先檢查組中是否存在元素為 +\infty 或者 -\infty 的節點. 如果有的話, 優先去替換這個節點中的元素.

6. 儲存

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

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

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

7. 外部排序

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

8. 實作

我自己用 C++ 實作了贏者樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/winner_tree.hpp 和輸者樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/loser_tree.hpp, 大家可以參考後自行實作.