數(shù)據(jù)結(jié)構(gòu)之樹

數(shù)據(jù)結(jié)構(gòu)之樹劉千源2019.04.18目錄Content和樹初次相識更進一步的了解交一些樹朋友和樹的初次相識什么是樹？生活中的樹計算機科學中的樹計算機科學中的樹有序樹無序樹多叉樹二叉樹無序樹和有序樹有序樹：樹中每個結(jié)點的各子樹從左到右有序且不能相互替換。無序樹：沒有滿足上述要求就是一棵無序樹無序樹有序樹二叉樹和多叉樹二叉樹：樹中每個結(jié)點最多只有兩個子結(jié)點。多叉樹：樹中每個結(jié)點可以擁有兩個及以上的結(jié)點。多叉樹二叉樹滿二叉樹和完全二叉樹滿二叉樹：除最后一層無任何子節(jié)點外，每一層上的所有結(jié)點都有兩個子結(jié)點二叉樹。

完全二叉樹：完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應時稱之為完全二叉樹。滿二叉樹完全二叉樹最優(yōu)二叉樹(霍夫曼樹)

最優(yōu)二叉樹：給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹。WPL：樹的所有葉結(jié)點的帶權(quán)路徑長度之和，稱為樹的帶權(quán)路徑長度表示為WPL。WPL=2*5+5*5+6*4+8*3+13*3+19*3+25*2+36*2=301樹的相關術(shù)語結(jié)點的度（Degree）：結(jié)點的子樹個數(shù)；樹的度：樹的所有結(jié)點中最大的度數(shù)；葉結(jié)點（Leaf）：度為0的結(jié)點；父結(jié)點（Parent）：有子樹的結(jié)點是其子樹的根節(jié)點的父結(jié)點；子結(jié)點/孩子結(jié)點（Child）：若A結(jié)點是B結(jié)點的父結(jié)點，則稱B結(jié)點是A結(jié)點的子結(jié)點；兄弟結(jié)點（Sibling）：具有同一個父結(jié)點的各結(jié)點彼此是兄弟結(jié)點；

路徑和路徑長度：從結(jié)點n1到nk的路徑為一個結(jié)點序列n1，n2，...，nk。ni是ni+1的父結(jié)點。路徑所包含邊的個數(shù)為路徑的長度；祖先結(jié)點（Ancestor）：沿樹根到某一結(jié)點路徑上的所有結(jié)點都是這個結(jié)點的祖先結(jié)點；子孫結(jié)點（Descendant）：某一結(jié)點的子樹中的所有結(jié)點是這個結(jié)點的子孫；結(jié)點的層次（Level）：規(guī)定根結(jié)點在1層，其他任一結(jié)點的層數(shù)是其父結(jié)點的層數(shù)加1；樹的深度（Depth）：樹中所有結(jié)點中的最大層次是這棵樹的深度；’結(jié)點的高度（Node

Height）：節(jié)點的高度是該節(jié)點與后代葉之間最長路徑上的邊數(shù)；結(jié)點的深度（Node

Depth）：節(jié)點的深度定義為：節(jié)點和根之間的邊數(shù)；更進一步的了解樹解決了什么問題？如何遍歷一顆樹?樹有哪些運用場景？樹的家族成員都有哪些？樹到底解決了什么問題？降低搜索時間復雜度列表的遍歷搜索過程假如我們要在1000w條數(shù)據(jù)中尋找我們想要的那一條，我們可以通過foreach去遍歷，此時最壞的情況為O(n)。但是樹卻可以保證他們的平均時間復雜度為O(logN)。同時，相比于搜索時間復雜度為O(1)的散列表(HashMap)來說，雖然速度上與之相比略有不足，但是樹能保證有序，省去了擴容的開銷，并且可以做范圍搜索。Find

6解決分組問題因為樹總是從一個根結(jié)點自上而下的延申，每個結(jié)點至少有一個或以上的結(jié)點，那么作為兄弟的結(jié)點們都將會有公共的父親結(jié)點以及父親結(jié)點之上的結(jié)點。利用這個特性，我們使用樹對一些數(shù)據(jù)做特定的屬性分類便非常方便。操作系統(tǒng)的目錄就是一棵樹。Trie樹，解決字典查找公共前綴問題笛卡爾樹，解決尋找最低公共祖先(代替數(shù)列求RMQ的問題的解決方案)如何遍歷一顆樹?深度優(yōu)先深度優(yōu)先遍歷分為前/中/后序遍歷：前序遍歷：指先訪問根，然后訪問子樹的遍歷方式。中序遍歷：指先訪問左（右）子樹，然后訪問根，最后訪問右（左）子樹的遍歷方式。后序遍歷：指先訪問子樹，然后訪問根的遍歷方式。前序：F,B,A,D,C,E,G,I,

H.中序：A,B,C,D,E,F,G,H,

I.后序：A,C,E,D,B,H,I,G,

F.廣度優(yōu)先樹的廣度優(yōu)先遍歷也就是層序遍歷。層序：F,B,G,A,D,I,C,E,H.樹有哪些運用場景？程序員日常中，樹的一些運用場景在計算機科學領域，樹的運用隨處可見，這里舉幾個簡單的例子：計算機目錄系統(tǒng)。JSON,XML等文本描述語言。Zookeeper。Jdk8以上的HashMap的Entry鏈過長會優(yōu)化為紅黑樹。大多數(shù)的存儲引擎都使用了B+Tree，結(jié)構(gòu)對于磁盤搜索相當友好。算數(shù)表達式解析可以使用樹來解決。哈夫曼樹尋找最短路徑。笛卡爾樹解決求空間最大面積。后臺管理的目錄。產(chǎn)品功能樹狀圖。計算機目錄產(chǎn)品功能樹狀圖樹的家族成員都有哪些？樹的大部分成員來自維基百科：/wiki/Category:Trees_(data_structures)最熟悉的一些樹二叉搜索樹二叉平衡搜索樹（AVL）伸展樹紅黑樹霍夫曼樹笛卡爾樹B-TreeB+TreeB*Tree交一些樹朋友在認識這些朋友之前，首先科普以下樹的左右旋，這個之后會幫助我們更容易理解樹枝的變換：左旋右旋二叉搜索樹二叉搜索樹二叉搜索樹是一顆二叉樹，性質(zhì)如下：有序：一個結(jié)點的左孩子小于（大于）自己，那么右孩子一定大于（小于）自己。二叉搜索樹的添加很簡單，從root結(jié)點開始：如果root為空，則待插入結(jié)點作為root結(jié)點。

如果root結(jié)點不為空，判斷待插入結(jié)點于root結(jié)點的大小，如果大于，則取root右孩子重復1的操作，如果小于，取root左孩子重復1的操作。二叉搜索樹二叉搜索樹的搜索：

從root結(jié)點開始，判斷當前結(jié)點（root）結(jié)點的值是否等于待尋找的目標索引值。如果1判斷等于，則返回目標結(jié)點，如果大于，則對當前結(jié)點的右孩子做同樣操作，如果小于，則對當前結(jié)點的左孩子做同樣操作。如果在2的步驟中，當前結(jié)點的索引值不等于待尋找的目標索引值時，要迭代的左孩子或者右孩子恰好為空，則表示待尋找的目標于當前樹中不存在，退出迭代。以上其實就是一個DFS場景。查找4二叉搜索樹二叉搜索樹的刪除：使用之前寫好的方法來查詢待刪除的結(jié)點。如果不存在，則退出刪除，如果存在，進入步驟3

如果當前結(jié)點時葉子結(jié)點，直接移除，否則，進入步驟4如果待刪除結(jié)點左孩子為空，則右孩子代替當前結(jié)點；如果待刪除結(jié)點右孩子為空，則左孩子代替當前結(jié)點；如果左右孩子都不為空，進入步驟5獲取該結(jié)點的中序前驅(qū)，代替當前結(jié)點。刪除4二叉平衡搜索樹二叉平衡搜索樹二叉平衡搜索樹又名AVL，彌補了二叉搜索樹在某些情況下會退化到線性搜索的不足，AVL在此之上增加了平衡性：有序：一個結(jié)點的左孩子小于（大于）自己，那么右孩子一定大于（小于）自己。平衡性：它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹二叉搜索樹退化為線性AVL防止退化二叉平衡搜索樹AVL插入：如果root為空，則待插入結(jié)點作為root結(jié)點。如果root結(jié)點不為空，則仿照二叉搜索樹的插入來做。

從插入點依次訪問parent結(jié)點，如果parent的左子樹高度和右子樹高度的差的絕對值大于1，說明當前parent結(jié)點為失衡點，進入步驟4進行rebalance操作，否則結(jié)束。這個步驟主要為了保證AVL樹的平衡特性，對于失衡點，分以下幾種場景：左子樹比右子樹高，且插入點為左子樹的左邊：左子樹比右子樹高，且插入點為左子樹的右邊：右子樹比左子樹高，且插入點為右子樹的右邊：右子樹比左子樹高，且插入點為右子樹的左邊：失衡點右旋左子樹左旋，失衡點右旋失衡點左旋右子樹右旋，失衡點左旋二叉平衡搜索樹插入4二叉平衡搜索樹插入9二叉平衡搜索樹插入11二叉平衡搜索樹插入4二叉平衡搜索樹AVL搜索：同二叉搜索樹二叉平衡搜索樹AVL刪除：同二叉搜索樹刪除對實際刪除點（要刪除點的中序前驅(qū)）開始向上做rebalance刪除7伸展樹伸展樹伸展樹不是平衡樹，但是操作它的平均時間復雜度仍然是O（n），相比普通的二叉搜索樹，它多了一個新特性：有序：一個結(jié)點的左孩子小于（大于）自己，那么右孩子一定大于（小于）自己。伸展：在每次查找之后對樹進行重構(gòu)，把被查找的條目搬移到離樹根近一些的地方。二叉搜索樹退化為線性對結(jié)點5做一次訪問伸展樹伸展樹的插入和普通二叉樹的插入略有不同，伸展樹插入的點始終會成為根結(jié)點:如果root為空，插入點成為root結(jié)點。

如果root不為空，插入點如果大于root結(jié)點，則root結(jié)點成為插入點的右孩子，插入點成為root結(jié)點。否則，root結(jié)點成為插入點的左孩子，插入點成為root結(jié)點。伸展樹的構(gòu)造過程伸展樹伸展樹的查詢將會引發(fā)整棵樹的調(diào)整，因為被訪問的結(jié)點要更接近于根：1.像二叉搜索樹一樣查詢，如果查詢結(jié)果不為空，則進入步驟2，開始伸展2.如果訪問結(jié)點位于左邊，且parent也位于左邊：grandParent右旋，parent右旋3.如果訪問結(jié)點位于左邊，parent位于右邊：parent右旋，grandParent左旋4.如果訪問結(jié)點位于右邊，且parent也位于右邊：grandParent左旋，parent左旋5.如果訪問結(jié)點位于右邊，parent位于左邊：parent左旋，grandParent右旋對1結(jié)點進行一次訪問伸展樹伸展樹的刪除：1.同二叉搜索樹，先訪問待刪除的點，此時會導致該點被推到根，之后再做刪除。刪除結(jié)點3紅黑樹紅黑樹紅黑樹是可以二叉搜索樹，但不是嚴格意義上的平衡樹，因為它的左右子樹高度差的絕對值可能會大于1，但是它需要滿足以下特性：每個節(jié)點或者是黑色，或者是紅色。根節(jié)點是黑色。每個葉子節(jié)點（NIL）是黑色。[注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！]如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。1.2.3.4.5.從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。[這里指到葉子節(jié)點的路徑]如果一顆樹滿足上述特性，那么它就是一顆紅黑樹紅黑樹紅黑樹的插入結(jié)點始終是紅色，具體原因請看上一頁第5個特性：從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。[這里指到葉子節(jié)點的路徑]如果新增的結(jié)點是紅色，不會導致該路徑上的黑色結(jié)點數(shù)量變化，也就不需要進行變換，但是插入點的parent結(jié)點是紅色，那么很明顯違背了特性4：如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。這個時候就需要進行一系列的調(diào)整：如果插入點的parent是黑色，不需要調(diào)整，結(jié)束。否則，進入步驟2如果插入點的parent是紅色，則需要根據(jù)插入的叔叔結(jié)點的顏色來進行下一步的決策！3.如果叔叔是紅色，變換祖父結(jié)點為紅色，父親結(jié)點和叔叔結(jié)點為黑色（翻頁）紅黑樹4.如果叔叔是黑色，又要分情況討論：1.parent在左，叔叔在右，插入結(jié)點在左：grandParent右旋，變色2.parent在左，叔叔在右，插入結(jié)點在右：parent左旋，grandParent右旋，變色3.parent在右，叔叔在左，插入結(jié)點在右：grandParent左旋，變色4.parent在右，叔叔在左，插入結(jié)點在左：parent右旋，grandParent左旋，變色叔父都為紅叔為黑-1紅黑樹叔為黑-2叔為黑-3叔為黑-4紅黑樹紅黑樹的刪除相比插入更加復雜，借博客地址一用：

/goodluckwhh/article/details/12718233霍夫曼樹霍夫曼樹霍夫曼樹，也成為最優(yōu)二叉樹，它的帶權(quán)路徑長度是最小的，也就是WPL（樹的所有葉結(jié)點的帶權(quán)路徑長度之和）最小。哈夫曼編碼是哈夫曼樹的一個應用。在數(shù)字通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的二進制串，這一過程被稱為編碼。在傳送電文時，總是希望電文代碼盡可能短，采用哈夫曼編碼構(gòu)造的電文的總長最短。由常識可知，電文中每個字符出現(xiàn)的概率是不同的。假定在一份電文中，A，B，C，D四種字符出現(xiàn)的概率是

4/10，1/10，3/10，2/10，若采用不等長編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣就有可能縮短傳送電文的總長度。采用不等長編碼時要避免譯碼的二義性和多義性。假設用0表示C，用01表示D，則當接收到編碼串01，并譯碼到0時，是立即譯出C，還是接著下一個字符1一起譯為對應的字符D，這樣就產(chǎn)生了二義性。因此，若對某一字符集進行不等長編碼，則要求字符集中任一字符的編碼都不能是其他字符編碼的前綴，符合此要求的編碼叫做前綴編碼?？梢愿鶕?jù)哈夫曼算法構(gòu)造哈夫曼樹T。設需要編碼的上述電文字符集d={A,B,C,D},在電文中出現(xiàn)的頻率集合

p={4/10,1/10,3/10,2/10}我們以字符集中的字符作為葉子結(jié)點、頻率作為權(quán)值，構(gòu)造一棵哈夫曼樹?；舴蚵鼧淦渲?，每個結(jié)點分別對應一個字符，對T中的邊做標記，把左分支記為“0”，右分支標記為“1”。定義字符的編碼是從根結(jié)點到該字符所對應的葉子結(jié)點的路徑

上，各條邊上的標記所組成的序列就是哈夫曼編碼。A的編碼：0，C的編碼：10，D的編碼：110，B的編碼：111.顯然對于任意字符集，總能構(gòu)造出這樣的編碼二叉樹。由于在任何一條從根結(jié)點到一個葉子結(jié)點的路徑上一定不會出現(xiàn)其他葉子結(jié)點，所以通過這種方法得到的編碼一定是前綴編碼，通過遍歷二叉樹，可以求出每個字符的編碼霍夫曼樹霍夫曼樹的刪除沒什么意義，這里只講構(gòu)造過程，對于輸入集（1，2，3，4，5）：對輸入集排序（如果輸入集本身是有序的則不需要排序），總是取最小的兩個結(jié)點作為一棵樹的左右兩個結(jié)點構(gòu)建為樹，然后迭代，知道輸入集只剩余一個結(jié)點。笛卡爾樹笛卡爾樹笛卡爾樹是無序二叉樹，它有兩個特性：但是它的中序遍歷和它插入順序是一致的每個結(jié)點的子結(jié)點都比父結(jié)點大B-TreeB-Tree樹B-Tree是一個有序多叉樹，相比于二叉樹，多叉樹的優(yōu)勢在于深度的控制。如果僅僅在內(nèi)存中做查找，二叉樹和多叉樹的查詢效率差不了多少。但是內(nèi)存存取速度快，但容量小，價格昂貴，而且不能長期保存數(shù)據(jù)(在不通電情況下數(shù)據(jù)會消失)，所以很多場景下，我們需要將樹的結(jié)構(gòu)存儲在磁盤中，在其中做搜索的話，查樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導致詢效率低下。如果使用多叉樹的話，我們可以降低樹的深度，也就是說我們可以降低磁盤I/O次數(shù)，那么搜索效率受I/O的影響將會縮小很多，這也是大多數(shù)存儲引擎使用Btree/B+Tree作為存儲結(jié)構(gòu)的根本原因。當磁盤驅(qū)動器執(zhí)行讀/寫功能時。盤片裝在一個主軸上，并繞主軸高速旋轉(zhuǎn)，當磁道在讀/寫頭(又叫磁頭)下通過時，就可以進行數(shù)據(jù)的讀/寫了。一般磁盤分為固定頭盤(磁頭固定)和活動頭盤。固定頭盤的每一個磁道上都有獨立的磁頭，它是固定不動的，專門負責這一磁道上數(shù)據(jù)的讀/寫?；顒宇^盤(如上圖)的磁頭是可移動的。每一個盤面上只有一個磁頭(磁頭是雙向的，因此正反盤面都能讀寫)。它可以從該面的一個磁道移動到另一個磁道。所有磁頭都裝在同一個動臂上，因此不同盤面上的所有磁頭都是同時移動的(行動整齊劃一)。當盤片繞主軸旋轉(zhuǎn)的時候，磁頭與旋轉(zhuǎn)的盤片形成一個圓柱體。各個盤面上半徑相同的磁道組成了一個圓柱面，我們稱為柱面。因此，柱面的個數(shù)也就是盤面上的磁道數(shù).讀/寫磁盤上某一指定數(shù)據(jù)需要下面3個步驟：

首先移動臂根據(jù)柱面號使磁頭移動到所需要的柱面上，這一過程被稱為定位或查找。如上圖11.3中所示的6盤組示意圖中，所有磁頭都定位到了10個盤面的10條磁道上(磁頭都是雙向的)。這時根據(jù)盤面號來確定指定盤面上的磁道。盤面確定以后，盤片開始旋轉(zhuǎn)，將指定塊號的磁道段移動至磁頭下。經(jīng)過上面三個步驟，指定數(shù)據(jù)的存儲位置就被找到。這時就可以開始讀/寫操作了B-Tree樹B樹又叫平衡多路查找樹。一棵m階的B樹(m叉樹)的特性如下：樹中每個結(jié)點最多含有m個孩子（m>=2）；除根結(jié)點和葉子結(jié)點外，其它每個結(jié)點至少有[ceil(m/2)]個孩子（其中ceil(x)是一個取上限的函數(shù)）；

若根結(jié)點不是葉子結(jié)點，則至少有2個孩子（特殊情況：沒有孩子的根結(jié)點，即根結(jié)點為葉子結(jié)點，整棵樹只有一個根節(jié)點）；所有葉子結(jié)點都出現(xiàn)在同一層，葉子結(jié)點不包含任何關鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針都為null)；每個非終端結(jié)點中包含有n個關鍵字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：Ki(i=1...n)為關鍵字，且關鍵字按順序升序排序K(i-1)<Ki。Pi為指向子樹根的接點，且指針P(i-1)指向子樹種所有結(jié)點的關鍵字均小于Ki，但都大于K(i-1)。關鍵字的個數(shù)n必須滿足：[ceil(m/2)-1]<=n<=m-1。如下圖所示：B-Tree樹B樹一覽B-Tree樹向B樹添加元素時，parent結(jié)點都是被動產(chǎn)生的。對于一顆3階的Btree，它的第一個特性為：樹中每個結(jié)點最多含有m個孩子（m>=2）；那就意味著，當前結(jié)點