勝者樹和敗者樹都是完全二叉樹，是樹形選擇排序的一種變型，
勝者樹和敗者樹
。每個(gè)葉子結(jié)點(diǎn)相當(dāng)于一個(gè)選手，每個(gè)中間結(jié)點(diǎn)相當(dāng)于一場比賽，每一層相當(dāng)于一輪比賽。 不同的是，勝者樹的中間結(jié)點(diǎn)記錄的是勝者的標(biāo)號；而敗者樹的中間結(jié)點(diǎn)記錄的敗者的標(biāo)號。 勝者樹與敗者樹可以在log(n)的時(shí)間內(nèi)找到最值。任何一個(gè)葉子結(jié)點(diǎn)的值改變后，利用中間結(jié)點(diǎn)的信息，還是能夠快速地找到最值。在k路歸并排序中經(jīng)常用到。勝者樹
勝者樹的一個(gè)優(yōu)點(diǎn)是，如果一個(gè)選手的值改變了，可以很容易地修改這棵勝者樹。只需要沿著從該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑修改這棵二叉樹，而不必改變其他比賽的結(jié)果。vcgLSDXz/2IhKYgLSDS0MzszfLA7w==" src="http://www.2cto.com/uploadfile/2015/0331/20150331103135125.jpg" />Fig. 1 Fig.1是一個(gè)勝者樹的示例。規(guī)定數(shù)值小者勝。b3 PK b4，b3勝b4負(fù)，內(nèi)部結(jié)點(diǎn)ls[4]的值為3；
b3 PK b0，b3勝b0負(fù)，內(nèi)部結(jié)點(diǎn)ls[2]的值為3；
b1 PK b2，b1勝b2負(fù)，內(nèi)部結(jié)點(diǎn)ls[3]的值為1；
b3 PK b1，b3勝b1負(fù)，內(nèi)部結(jié)點(diǎn)ls[1]的值為3。. 當(dāng)Fig. 1中葉子結(jié)點(diǎn)b3的值變?yōu)?1時(shí)，重構(gòu)的勝者樹如Fig. 2所示。
b3 PK b4，b3勝b4負(fù)，內(nèi)部結(jié)點(diǎn)ls[4]的值為3；
b3 PK b0，b0勝b3負(fù)，內(nèi)部結(jié)點(diǎn)ls[2]的值為0；
b1 PK b2，b1勝b2負(fù)，內(nèi)部結(jié)點(diǎn)ls[3]的值為1；
b0 PK b1，b1勝b0負(fù)，內(nèi)部結(jié)點(diǎn)ls[1]的值為1，
電腦資料
《勝者樹和敗者樹》(http://m.dameics.com)。.Fig. 2敗者樹
敗者樹是勝者樹的一種變體。在敗者樹中，用父結(jié)點(diǎn)記錄其左右子結(jié)點(diǎn)進(jìn)行比賽的敗者，而讓勝者參加下一輪的比賽。敗者樹的根結(jié)點(diǎn)記錄的是敗者，需要加一個(gè)結(jié)點(diǎn)來記錄整個(gè)比賽的勝利者。采用敗者樹可以簡化重構(gòu)的過程。Fig. 3 Fig. 3是一棵敗者樹。規(guī)定數(shù)大者敗。b3 PK b4，b3勝b4負(fù)，內(nèi)部結(jié)點(diǎn)ls[4]的值為4；
b3 PK b0，b3勝b0負(fù)，內(nèi)部結(jié)點(diǎn)ls[2]的值為0；
b1 PK b2，b1勝b2負(fù)，內(nèi)部結(jié)點(diǎn)ls[3]的值為2；
b3 PK b1，b3勝b1負(fù)，內(nèi)部結(jié)點(diǎn)ls[1]的值為1；
在根結(jié)點(diǎn)ls[1]上又加了一個(gè)結(jié)點(diǎn)ls[0]=3，記錄的最后的勝者。 敗者樹重構(gòu)過程如下：
將新進(jìn)入選擇樹的結(jié)點(diǎn)與其父結(jié)點(diǎn)進(jìn)行比賽：將敗者存放在父結(jié)點(diǎn)中；而勝者再與上一級的父結(jié)點(diǎn)比較。
比賽沿著到根結(jié)點(diǎn)的路徑不斷進(jìn)行，直到ls[1]處。把敗者存放在結(jié)點(diǎn)ls[1]中，勝者存放在ls[0]中。Fig. 4 Fig. 4是當(dāng)b3變?yōu)?3時(shí)，敗者樹的重構(gòu)圖。 注意，敗者樹的重構(gòu)跟勝者樹是不一樣的，敗者樹的重構(gòu)只需要與其父結(jié)點(diǎn)比較。對照Fig. 3來看，b3與結(jié)點(diǎn)ls[4]的原值比較，ls[4]中存放的原值是結(jié)點(diǎn)4，即b3與b4比較，b3負(fù)b4勝，則修改ls[4]的值為結(jié)點(diǎn)3。同理，以此類推，沿著根結(jié)點(diǎn)不斷比賽，直至結(jié)束。 由上可知，敗者樹簡化了重構(gòu)。敗者樹的重構(gòu)只是與該結(jié)點(diǎn)的父結(jié)點(diǎn)的記錄有關(guān)，而勝者樹的重構(gòu)還與該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)有關(guān)。