2-3树的由来
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?
版權聲明:本文為博主原創文章,轉載請附上博文鏈接!
總結
- 上一篇: go 关闭通道的必要性
- 下一篇: go 分段锁ConcurrentMap,