查找算法之平衡查找樹

前面介紹的算法在最壞的情況下還是很糟糕。這次會介紹一種二分查找樹並能保證無論如何構造它，他的運行時間都是對數級別的。理想情況下我們希望能夠保持二分查找樹的平衡性。但是，在動態插入中保證樹的完美平衡的代價太高了。

2-3查找樹

我們將一棵標準的二叉查找樹中的節點成爲2-節點（含有一個鍵和兩條鏈接），現在我們引入3-節點，它含有兩個鍵和三條鏈接。

查找

要判斷一個鍵是否在樹中，我們先將它和根節點中的鍵比較。如果它和其中任意一個相等，查找命中；否則我們就根據比較的結果找到指向相應區間的鏈接，並在其指向的子樹中遞歸的遞歸查找。如果這個是空鏈接，查找未命中。

插入

樹的平衡：
任何節點的左子樹和右子樹之間的高度差不能超過1。

上圖中（a）是平衡的，（b）是不平衡的，很顯然，一個完全不平衡的樹，在做查找時，它就是線性級別的性能，而平衡的二叉樹，同樣的數據量，但有效利用了平衡性，它的查找性能則能降到對數級別。

而動態平衡要求的是要在插入是，時刻保持樹的平衡性。

分爲幾種情況：

向2-節點中插入新鍵

若未命中的查找結束於一個2-節點，我們只要把這個2節點替換爲一個3節點就可以了。

向一棵只有3-節點的樹中插入新鍵

爲了新鍵的插入，首先臨時將新鍵存入該節點中，使之成爲一個4-節點。然後很容易就將他轉化爲一棵由3個2-節點組成的2-3樹。

向一棵父節點爲2-節點的3-節點中插入新鍵

假設未命中的查找結束於3-節點，而他的父節點是2-節點。我們先像剛纔一樣構造一個臨時的4-節點並將其分解，但此時我們不會爲中鍵創造一個新的節點，而是將其移動至原來的父節點中。

向一棵父節點爲3-節點的3-節點中插入新鍵

假設未命中的查找結束於一個父節點爲3-節點的節點，我們再次和剛纔一樣構造一個臨時的4-節點並分解它，然後將他的中鍵插入它的父節點中，但父節點也是一個3-節點，因此我們再用這個中鍵構造一個臨時的4-節點，然後在這個節點上進行相同的變換，就這樣一直向上不斷分解臨時4-節點並將中鍵插入到更高層的父節點。

分解根節點

構造二叉樹

總結

儘管我們可以用不同的數據類型表示2-節點和3-節點，但是這種直白的表示方法實現大多數操作並不方便，因爲需要處理的情況太多。我們需要維護兩種不同類型的節點，將被查找的鍵和節點中的每個鍵進行比較，將鏈接和其他信息從一種節點複製到另一種節點，將節點從一種數據類型轉換到另一種類型，等等。不僅需要大量的代碼，而且產生的額外開銷可能會使算法比標準二叉樹更慢。