勝者樹和敗者樹都是完全二叉樹，是樹形選擇排序的一種變型，

勝者樹和敗者樹

。每個葉子結點相當于一個選手，每個中間結點相當于一場比賽，每一層相當于一輪比賽。 不同的是，勝者樹的中間結點記錄的是勝者的標號；而敗者樹的中間結點記錄的敗者的標號。 勝者樹與敗者樹可以在log(n)的時間內(nèi)找到最值。任何一個葉子結點的值改變后，利用中間結點的信息，還是能夠快速地找到最值。在k路歸并排序中經(jīng)常用到。

勝者樹

勝者樹的一個優(yōu)點是，如果一個選手的值改變了，可以很容易地修改這棵勝者樹。只需要沿著從該結點到根結點的路徑修改這棵二叉樹，而不必改變其他比賽的結果。vcgLSDXz/2IhKYgLSDS0MzszfLA7w==" src="http://www.2cto.com/uploadfile/2015/0331/20150331103135125.jpg" />Fig. 1 Fig.1是一個勝者樹的示例。規(guī)定數(shù)值小者勝。

b3 PK b4，b3勝b4負，內(nèi)部結點ls[4]的值為3；

b3 PK b0，b3勝b0負，內(nèi)部結點ls[2]的值為3；

b1 PK b2，b1勝b2負，內(nèi)部結點ls[3]的值為1；

b3 PK b1，b3勝b1負，內(nèi)部結點ls[1]的值為3。. 當Fig. 1中葉子結點b3的值變?yōu)?1時，重構的勝者樹如Fig. 2所示。

b3 PK b4，b3勝b4負，內(nèi)部結點ls[4]的值為3；

b3 PK b0，b0勝b3負，內(nèi)部結點ls[2]的值為0；

b1 PK b2，b1勝b2負，內(nèi)部結點ls[3]的值為1；

b0 PK b1，b1勝b0負，內(nèi)部結點ls[1]的值為1，

電腦資料

《勝者樹和敗者樹》(http://www.msguai.com)。.Fig. 2

敗者樹

敗者樹是勝者樹的一種變體。在敗者樹中，用父結點記錄其左右子結點進行比賽的敗者，而讓勝者參加下一輪的比賽。敗者樹的根結點記錄的是敗者，需要加一個結點來記錄整個比賽的勝利者。采用敗者樹可以簡化重構的過程。Fig. 3 Fig. 3是一棵敗者樹。規(guī)定數(shù)大者敗。

b3 PK b4，b3勝b4負，內(nèi)部結點ls[4]的值為4；

b3 PK b0，b3勝b0負，內(nèi)部結點ls[2]的值為0；

b1 PK b2，b1勝b2負，內(nèi)部結點ls[3]的值為2；

b3 PK b1，b3勝b1負，內(nèi)部結點ls[1]的值為1；

在根結點ls[1]上又加了一個結點ls[0]=3，記錄的最后的勝者。 敗者樹重構過程如下：

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

比賽沿著到根結點的路徑不斷進行，直到ls[1]處。把敗者存放在結點ls[1]中，勝者存放在ls[0]中。Fig. 4 Fig. 4是當b3變?yōu)?3時，敗者樹的重構圖。 注意，敗者樹的重構跟勝者樹是不一樣的，敗者樹的重構只需要與其父結點比較。對照Fig. 3來看，b3與結點ls[4]的原值比較，ls[4]中存放的原值是結點4，即b3與b4比較，b3負b4勝，則修改ls[4]的值為結點3。同理，以此類推，沿著根結點不斷比賽，直至結束。 由上可知，敗者樹簡化了重構。敗者樹的重構只是與該結點的父結點的記錄有關，而勝者樹的重構還與該結點的兄弟結點有關。