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

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

完全二叉樹：完全二叉樹是由滿二叉樹而引出來的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。滿二叉樹完全二叉樹最優(yōu)二叉樹(霍夫曼樹)

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

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

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

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

6解決分組問題因?yàn)闃淇偸菑囊粋€(gè)根結(jié)點(diǎn)自上而下的延申，每個(gè)結(jié)點(diǎn)至少有一個(gè)或以上的結(jié)點(diǎn)，那么作為兄弟的結(jié)點(diǎn)們都將會(huì)有公共的父親結(jié)點(diǎn)以及父親結(jié)點(diǎn)之上的結(jié)點(diǎn)。利用這個(gè)特性，我們使用樹對(duì)一些數(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.樹有哪些運(yùn)用場景？程序員日常中，樹的一些運(yùn)用場景在計(jì)算機(jī)科學(xué)領(lǐng)域，樹的運(yùn)用隨處可見，這里舉幾個(gè)簡單的例子：計(jì)算機(jī)目錄系統(tǒng)。JSON,XML等文本描述語言。Zookeeper。Jdk8以上的HashMap的Entry鏈過長會(huì)優(yōu)化為紅黑樹。大多數(shù)的存儲(chǔ)引擎都使用了B+Tree，結(jié)構(gòu)對(duì)于磁盤搜索相當(dāng)友好。算數(shù)表達(dá)式解析可以使用樹來解決。哈夫曼樹尋找最短路徑。笛卡爾樹解決求空間最大面積。后臺(tái)管理的目錄。產(chǎn)品功能樹狀圖。計(jì)算機(jī)目錄產(chǎn)品功能樹狀圖樹的家族成員都有哪些？樹的大部分成員來自維基百科：/wiki/Category:Trees_(data_structures)最熟悉的一些樹二叉搜索樹二叉平衡搜索樹（AVL）伸展樹紅黑樹霍夫曼樹笛卡爾樹B-TreeB+TreeB*Tree交一些樹朋友在認(rèn)識(shí)這些朋友之前，首先科普以下樹的左右旋，這個(gè)之后會(huì)幫助我們更容易理解樹枝的變換：左旋右旋二叉搜索樹二叉搜索樹二叉搜索樹是一顆二叉樹，性質(zhì)如下：有序：一個(gè)結(jié)點(diǎn)的左孩子小于（大于）自己，那么右孩子一定大于（小于）自己。二叉搜索樹的添加很簡單，從root結(jié)點(diǎn)開始：如果root為空，則待插入結(jié)點(diǎn)作為root結(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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