什么是Garsia-Wachs算法？很多人都覺得這個(gè)算法比較陌生，Garsia-Wachs 算法（Garsia-Wachs Algorithm）是計(jì)算機(jī)用來在線性時(shí)間內(nèi)構(gòu)建最優(yōu)二叉查找樹和字母霍夫曼碼的有效算法。

● 過程：

Garsia-Wachs 算法一般包括三個(gè)階段：

1. 構(gòu)建一個(gè)值位于葉子的二叉樹，注意順序可能錯(cuò)誤。

2. 計(jì)算樹中根到每個(gè)葉子的距離。

3. 構(gòu)建另一個(gè)二叉樹，葉子的距離相同，但順序正確。

如上圖所示，在算法的第一階段，通過查找合并輸入序列的無序三元組構(gòu)建的二叉樹（左側(cè)），和算法輸出的正確排序的二叉樹，其中葉子高度與另一棵樹一樣。

如果輸入在序列的開始和結(jié)束處增加了兩個(gè)標(biāo)記值（或任何足夠大的有限值），則算法的第一階段更容易描述。所以在競賽題解中使用 Garsia-Wachs 算法時(shí)，對(duì)于一個(gè)長度為n的數(shù)組，我們一般定義。

第一階段維護(hù)了一個(gè)由最初為每個(gè)非標(biāo)志（non-sentinel）輸入權(quán)重創(chuàng)建的單節(jié)點(diǎn)樹組成的森林。每棵樹都與一個(gè)值相關(guān)聯(lián)，其葉子的權(quán)重之和為每個(gè)非標(biāo)志輸入權(quán)重構(gòu)成一個(gè)樹節(jié)點(diǎn)。為了維護(hù)這些值的序列，每端會(huì)有兩個(gè)標(biāo)記值。初始序列只是葉權(quán)重作為輸入的順序。然后重復(fù)執(zhí)行以下步驟，每一步都減少輸入序列的長度，直到只有一棵樹包含了所有葉子：

（1）在序列中找到前三個(gè)連續(xù)的權(quán)重值x,y,z使得x≤z 。因?yàn)樾蛄薪Y(jié)尾的標(biāo)志值大于之前的任意兩個(gè)有限值，所以總是存在這樣的三元組。

（2）從序列中移除x和y，并創(chuàng)建一個(gè)新的樹節(jié)點(diǎn)作為x和y節(jié)點(diǎn)的父節(jié)點(diǎn)，值為x+y。

（3）在原來x的位置以前大于或等于x+y且距x最近的值的右邊重新插入新節(jié)點(diǎn)。因?yàn)樽髽?biāo)志值的存在，所以總是存在這樣的位置。

為了有效地實(shí)現(xiàn)這一階段，該算法可以在任何平衡二叉查找樹結(jié)構(gòu)中維護(hù)當(dāng)前值序列。這樣的結(jié)構(gòu)允許我們在對(duì)數(shù)時(shí)間內(nèi)移除x和y，并重新插入它們的新父節(jié)點(diǎn)。在每一步中，數(shù)組中位于偶數(shù)索引上直到y(tǒng)值的權(quán)重形成了一個(gè)遞減序列，位于奇數(shù)索引位的權(quán)重形成另一個(gè)遞減序列。因此，重新插入x+y的位置可以通過在對(duì)數(shù)時(shí)間內(nèi)對(duì)這兩個(gè)遞減序列使用平衡樹執(zhí)行兩次二分查找找到。通過從前一個(gè)三元組z值開始的線性順序搜索，我們可以在總線性時(shí)間復(fù)雜度內(nèi)執(zhí)行對(duì)滿足x≤z的第一個(gè)位置的搜索。

Garsia-Wachs 算法的第三階段的證明，即存在另一棵具有相同距離的樹并且這棵樹提供了問題的最優(yōu)解，是很重要的。但是由于其證明方式有多種且過于復(fù)雜，此處略去。在第三階段為正確的前提下，第二和第三階段很容易在線性時(shí)間內(nèi)實(shí)現(xiàn)。因此，在長度為n的輸入序列上，Garsia-Wachs 算法的總時(shí)間復(fù)雜度為。