2-3查找樹

第一次接觸它是在刷數據結構那本書時，有它的介紹。而那時候只是單純的理解它的節點是如何分裂，以及整個構建過程，并不清楚它的實際用處，所以看了也就忘了。而當看完《算法》查找章節時，頓時有種頓悟，喔，原來如此啊。所以，提出來的這些有趣的結構千萬不能割裂來看，它的演變如此誘人，細節值得品味。

結構緣由

首先，搞清楚2-3查找樹為什么會出來，它要解決什么樣的問題？假設我們對它的基本已經有所了解了。先給它來個簡單的定義：

2-3查找樹： 一種保持有序結構的查找樹。 可以維持動態平衡的有序查找樹。

2-3查找樹：
一種保持有序結構的查找樹。
可以維持動態平衡的有序查找樹。
從上述定義就可以看出，它到底是為了解決什么問題，在上一篇文章中，介紹了【查找】的演變過程，詳細請參看博文這里。其中最后優化到了BST這種樹的結構。但我們都知道BST它對數據的輸入是敏感的，如最壞情況下，每次put()的key是有序的，那么構造出來的BST樹，就相當于一個鏈表，那么對于每個元素的查找，它的性能就相當糟糕。而2-3樹就是為了規避上述問題而設計發明出來的模型。現在請思考該如何設計它呢？

這里我們從BST遇到的實際問題出發，提出設計指標，再去思考利用些潛在的性質來構建2-3樹。這部分內容，沒有什么理論根據，而是我自己嘗試去抓些字典的性質來構建，而2-3樹的誕生過程并非真的如此，所以僅供參考。

構建2-3樹

字典的兩個主要操作為：查找和插入。而在前面一篇文章說到，作為有序表，查找性能和插入性能最理想的狀態為O(lgn)O(lg?n)，這點可以說明，BST作為樹形結構，已經完全符合字典的設計了，而如果從一個全新的結構去構建字典顯然已經沒有多大的必要了。

BST最大的問題在于，它對輸入敏感，針對有序的插入，它構建出來的結構相當于是鏈表。為什么會出現這種情況？

作為有序插入，每當有新節點加入時，樹沒有選擇【節點去向】的權力。（這好像是構建有序樹的特質，樹也無力改變，真慘！）
樹失去了分配【節點去向】的權力，自然就沒辦法動態改變它的高度。（出現極端情況的原因）
那么你會問了，難道就不能當輸入到一定量時，發現樹的深度太深，直接全局調整不行么？有了全局信息，不就能調控，分配每個節點了么。的確，我們要引出以下原因：

調控可以，但為了拿到這些全局信息，我們需要遍歷整個BST，而此時BST相當于鏈表，遍歷一次的代價已經高于查找的效率，何必呢。
在插入時動態調整是最佳的，而當樹已經生成時，再去做樹的大調整，顯然實際有點難以操作。（這兩條的認識都比較感性）
綜上，字典key的有序性影響了【節點去向】，樹失去了【分配權】，其次結構隨插入時，樹的【動態調整】優于【全局調整】。所以，我們需要設計一種結構能夠符合：

擁有分配權
可以動態調整
指標提出來了，但真的要設計出這樣的結構的確不是一般人能做的，好在，這世界有太多的大牛了，我們可以參考人家的思路。

分配權

為什么BST會失去分配權力？因為它沒有可以權衡的信息，在BST中，每個節點只能存儲了一個key，每當有新的節點插入時，進行比較后，就自動選擇路徑到它的子樹中去了，它無法停留。節點的去向我們是無法改變的，已由有序性決定，但我們是否可以決定它的【去】和【留】，它到這節點就一定要構建新的節點？不能停留在舊的節點上么？

從宏觀的角度來看這件事情的話，如果我么能做到key值插入節點的【停留】，是否能夠利用它來做樹結構調整呢？答案呼之欲出！

我就不賣關子了，直接給出2-3樹的其中一個基本定義：

一棵2-3查找樹或為一顆空樹，或由以下節點組成： 2-節點：含有一個鍵和兩條鏈接，左鏈接指向的2-3樹中的鍵都小于該節點，右鏈接指向的2-3樹中的鍵都大于該節點。 3-節點：含有兩個鍵和三條鏈接，左鏈接指向的2-3樹中的鍵都小于該節點，中鏈接指向的2-3樹中的鍵都位于該節點的兩個鍵之間，右鏈接指向的2-3樹中的鍵都大于該節點。

一棵2-3查找樹或為一顆空樹，或由以下節點組成：
2-節點：含有一個鍵和兩條鏈接，左鏈接指向的2-3樹中的鍵都小于該節點，右鏈接指向的2-3樹中的鍵都大于該節點。
3-節點：含有兩個鍵和三條鏈接，左鏈接指向的2-3樹中的鍵都小于該節點，中鏈接指向的2-3樹中的鍵都位于該節點的兩個鍵之間，右鏈接指向的2-3樹中的鍵都大于該節點。
！！！傳統的樹定義即為2-節點，但2-3樹查找樹的定義多了個3-節點，而3-節點，也就是為了讓節點能夠停留，而設計出來的新結構，它具有緩存能力？哈哈，可以這么理解。意思就是說，現在樹多了一條權力，不再是節點說了算，你不是老大！樹可以選擇我把你【放在這】還是【找你的子樹去】。對樹來說是件好事，起碼可以分配你了吧！所以分配這件事需要資源累積。

數據結構有了，我們先來看看它的查找，暫且忽略它是怎么構建的。我們只需要知道兩個事實，每個節點最多可以存儲兩個鍵，三個分叉。比較選擇子樹和BST是一樣的，對每個節點比較，然后選擇合適的子樹，進行下一步的遞歸比較。

?
左圖是命中情況，右圖是未命中，跟著圖一步步走，就能理解整個查找過程了，這里我就不廢話了。

動態平衡

要知道什么是動態平衡，就必須知道什么是平衡，這也是我第一次思考平衡這個概念，我們就拿樹中對平衡的定義，粗略解釋下。

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

所以很明顯（a）圖是平衡的，而（b）圖是不平衡的。其實還要思考一個問題，平衡這個概念為何而出？定義樹的平衡有它的必要性么？很顯然，一個完全不平衡的樹，在做查找時，它就是線性級別的性能，而平衡的二叉樹，同樣的數據量，但有效利用了平衡性，它的查找性能則能降到對數級別，這些都可以在數學上證明，此處只做感性認識。

那什么是動態平衡呢？定義如下：

樹的動態平衡： 在對樹進行插入操作時，每個動態的狀態都能滿足靜態的平衡條件。

動態平衡是時時刻刻的，在新數據插入前，它是平衡的，而一旦當數據插入導致樹結構不平衡時則立馬進行調整。這思想很重要，因為后續的平衡二叉樹算法都是基于這個原則實現的。原因也說了，如果不去時刻維護，要獲得全局信息代價高昂且全局調整難度大于局部調整。

有上述性質，我們不難判斷BST不是一個能夠自平衡的結構，在最壞情況下它的缺陷很明顯，對于有序key的插入，樹的深度+1。那么問題來了，假設我現在要插入三個有序的key值如A E S。

BST的做法已經很明顯了，生成如下結構A -> E -> S。我們來看看2-3樹，剛才定義了3節點，我們就嘗試性的讓最開始的兩個節點停留在根節點，于是有如下所示：

?
很明顯，在插入第三個節點時，我們就只剩下一個選擇了，讓它去子樹上找位置去，這意味著它和BST的插入本質上是一樣的，并沒有利用緩存的能力。但其實這緩存有個很好的性質，它有了兩個節點的信息（大于1節點的局部信息），可以對三個key值在插入時刻進行比較，而一旦能達到這能力，此樹就可以做自我調整了。如：我找三個樹的中間值，把它變成三個節點的BST樹！相比于直接把下一節點插入到子樹中去，它利用了兩個元素的信息做了些調整，而調整后的樹，是個平衡的二叉樹。

所以接下來的事情，就是當有更多元素插入時，如何讓這個2-3樹在做調整時，時刻保持動態平衡。唉，令人遺憾的是這想法直接就由上面那種最簡單的情況得到了，如上，我們沒理由把節點往下插。用個形象的比喻，樹根在生長時，有它的隨意性，因為扎根沒給它任何限制。而現在我們做了一件可怕的事情，我們在樹根生長的土壤中給它加了一層隔板，限制它的向下發展，而不去約束它的向上勢頭，但我們都知道，不管向上怎么發展，它始終是頭部為一個根節點，而底部為大量葉子節點的終極形態。

是不是很形象，所以2-3樹就形成了一個基本插入原則，每當有新的元素插入時，追根溯源到最底層（也就是那層隔板），當有存放它的位置時，2-節點還尚有一個存儲空間，它就存放。而當沒有存放位置時，3-節點都被塞滿了，那它開始【分裂】，分裂操作是不能破環【不準向下插入】原則的，所以它只能向上影響【父結點】。

所以有了上述原則，也就有了書中的對一些插入情況的討論。

向一棵只含有一個3-節點的樹中插入新鍵。（樹的初始態）
向一個父節點為2-節點的3-節點中插入新鍵。（子樹的分裂1）
向一個父節點為3-節點的3-節點中插入新建。（子樹的分類2）
分解根節點。（樹的向上生長態）
在前文中，我們已經圖解了樹的初始態，此處就不在解釋了。操作2和操作3是在子樹中最基本的兩個操作，它們唯一的區別在于父結點一種是【2節點狀態】而操作3的父結點是【3節點狀態】。

父節點：2-節點，子節點：3-節點?
?
很明顯，元素一定是先沉底的，此處元素沉底在最左邊，但由于超過了3-節點的存儲能力，所以它必須分裂，不能向下分裂，所以只能往上了，影響它的父節點，但父節點可以再容納一個元素，所以只需要把X元素放入父節點即可。

父節點：3-節點，子節點：3-節點?

?
此處和操作2唯一的區別在于，子節點分裂后，把一個元素加入到了它的父節點，但也超過了父節點的存儲能力，所以還要繼續向上分裂，直到有容下它的父節點。它和操作2本質上是一回事，但是為了表示分裂的傳遞性，所以被拎出來重點討論了下。

接著就剩下最后一個問題了，上述兩操作是不會影響樹的深度的，不信你自己模擬操作一遍，而真正影響樹的深度在于操作4，只有當根節點為3-節點時，此時有元素插入沉底后，不斷向上裂變，很不幸如果影響到根節點，那么就執行操作4，我冒個頭出來，哈哈，是不是形象。?

我們再來看看一個23樹的整體構建軌跡加深理解。

好了，整體的23樹的構建已經闡述完畢了，原本想看看書上是怎么實現的，讓我繼續加深理解，結果卻在書中找到這樣一段話，也是讓我很無語，但它所提出的思想值得學習。

《算法》

但是，我們和真正實現還有一段距離。盡管我們可以用不同的數據類型表示2-節點和3-節點并寫出變換所需的代碼，但用這種直白的表示方法實現大多數操作并不方便，因為需要處理的情況實在太多。我們需要維護兩種不同類型的節點，將被查找的鍵和節點中的每個鍵進行比較，將鏈接和其他信息從一種節點復制到另一種節點，將節點從一種數據類型轉換到另一種數據類型，等等。實現這些不僅需要大量的代碼，而且它們所產生的額外開銷可能會使算法比標準的二叉查找樹更慢。平衡一棵樹的初衷是為了消除最壞情況，但我們希望這種保障所需的代碼能夠越來越好。幸運的是你將看到，我們只需要一點點代價就能用一種統一的方式完成所有變換。
欲言又止，但很有愛，起碼它有進一步的實現版本了，具體是什么，我也賣個關子，下回分解。

參考文獻

Robert Sedgewick. 算法 第四版[M]. 北京：人民郵電出版社，2012.10
Cormen. 算法導論[M].北京：機械工業出版社，2013
算法原理系列：查找
---------------------?
作者：Demon的黑與白?
來源：CSDN?
原文：https://blog.csdn.net/u014688145/article/details/67636509?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

總結

以上是生活随笔為你收集整理的2-3树的由来的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。