敗者樹

敗者樹是計算機科學學科里的一種數據結構，可用於外部排序中提高效率。 敗者樹實際上是一棵完全二叉樹，可以看做是勝者樹的一種變體。敗者樹簡化了重構。敗者樹的重構只是與該結點的父結點的記錄有關，而勝者樹的重構還與該結點的兄弟結點有關。敗者樹中每個葉節點存放各歸併段在歸併過程中當前參加比較的記錄，每個非葉結點記憶其兩個子女結點中記錄排序碼小的結點（即敗者）。

注意，敗者樹的重構跟勝者樹是不一樣的，敗者樹的重構只需要與其父結點比較。對照右圖來看，b3與結點ls[4]的原值比較，ls[4]中存放的原值是結點4，即b3與b4比較，b3負b4勝，則修改ls[4]的值為結點3。同理，以此類推，沿著根結點不斷比賽，直至結束。

敗者樹重構過程如下：

將新進入選擇樹的結點與其父結點進行比賽：將敗者存放在父結點中；而勝者再與上一級的父結點比較。

比賽沿著到根結點的路徑不斷進行，直到ls[1]處。把敗者存放在結點ls[1]中，勝者存放在ls[0]中。