二叉樹

性質(zhì)：

第 n 層最多有 2n-1 個節(jié)點

深度為 k 的二叉樹最多有 2k - 1 個節(jié)點(滿二叉樹)

對于任何一顆二叉樹，如果其葉節(jié)點有 n0 個，度為2的非葉節(jié)點有 n2個，則有 n0 = n2 + 1

n個節(jié)點的完全二叉樹的深度為 ?log2n?+1

如果有一顆有n個節(jié)點的完全二叉樹的節(jié)點按層次序編號，對任一層的節(jié)點i(1

i

n)有

如果i=1，則節(jié)點i是二叉樹的根，無雙親，如果i>1，則其雙親節(jié)點為 ?i/2?

如果2i>n，則節(jié)點i沒有左孩子，否則其左孩子為2i

如果2i+1>n，則節(jié)點沒有右孩子，否則右孩子為2i+1

image

image

滿二叉樹

節(jié)點的度都是2且葉子節(jié)點都在同一層次上

是一種特殊的二叉樹

完全二叉樹

與滿二叉樹深度相同，并且編號一一對應(yīng)的二叉樹

性質(zhì)：

若 i

?n/2?，則結(jié)點i為分支結(jié)點，否則為葉子結(jié)點

最下面層的葉節(jié)點一定出現(xiàn)在左邊

深度為k的完全二叉樹，其最少的結(jié)點數(shù)=深度為 k-1 的滿二叉樹的結(jié)點數(shù)+1，即 2k-1個；其最多結(jié)點數(shù)=深度為k的滿二叉樹的結(jié)點數(shù)，即 2k-1

順序存儲完全二叉樹A[1,...,n]，當 i

(n-1)/2 時，結(jié)點A[i]的右孩子是結(jié)點 A[2i+1]

哈夫曼樹(最優(yōu)二叉樹)

性質(zhì)：

有n個葉子結(jié)點

沒有度為1的結(jié)點

總的結(jié)點數(shù)為2n-1

深度

n-1

形態(tài)不唯一

要使一棵二叉樹的帶權(quán)路徑長度最小，必須使權(quán)值越大的葉子節(jié)點越靠近根節(jié)點，權(quán)值越小的節(jié)點越遠離根節(jié)點

利用哈夫曼樹可構(gòu)造前綴編碼

最小生成樹

在連通網(wǎng)的所有生成樹中，所有邊的代價和最小的生成樹

看誰代價最小，來 PK 呀！P-prime, K-kruskal

prim算法

算法思想：從圖中任取一個頂點，把它當成一棵樹，然后從這棵樹的頂點相鄰的邊中選取權(quán)值最小的邊，并把這條邊相鄰的頂點并入樹中，此時得到一顆有兩個頂點的樹，然后繼續(xù)從這棵樹的兩個頂點相鄰的邊中選取一條最短的邊，將其和相鄰頂點再次并入樹中，重復(fù)操作直到所有頂點都被并入樹中。

prime算法圖解

kruskal算法

算法思想：每次從所有邊中選出權(quán)值最小的邊，將其并入樹中，重復(fù)操作直到所有頂點都被并入樹中。

kruskal算法圖解

圖片來源：https://blog.csdn.net/luoshixian099/article/details/51908175

二叉排序樹(二叉查找樹)

性質(zhì)：空樹/如果左子樹不為空，則左子樹的所有結(jié)點的值均小于根節(jié)點；如果右子樹不為空，則右子樹的所有結(jié)點均大于根節(jié)點；左右子樹分別也是二叉排序樹。中序遍歷會得到一個有序序列。

既擁有類似于折半查找的特性，又采用了鏈表做存儲結(jié)構(gòu)，它是動態(tài)查找表的一種適宜表示。其查詢效率高于鏈表結(jié)構(gòu)。

二叉排序樹

AVL樹(平衡二叉樹)

它是二叉排序樹的一種改進，由于樹的高度越小，查找效率越高，所以盡可能的保持左右子樹高度平衡，會使得樹的高度達到最小。

性質(zhì)：左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。即就是平衡因子只會取 -1，0 ，1，因此此處的重點不斷的執(zhí)行是平衡調(diào)整。

基于二分法的策咯提高數(shù)據(jù)查找速度的二叉樹的數(shù)據(jù)結(jié)構(gòu)。

【例】若平衡二叉樹的高度為6，且所有非葉結(jié)點的平衡因子均為 1，則該平衡二叉樹的結(jié)點總數(shù)為20

B樹(多路平衡查找樹)

B樹(B-tree)是在AVL樹基礎(chǔ)上的一種升級，它是各個節(jié)點平衡因子都為0的多路平衡查找樹。

B樹一開始是針對機械磁盤而設(shè)計的，因為機械磁盤的磁頭跳轉(zhuǎn)消耗的時間比較多，為了減少跳轉(zhuǎn)的次數(shù)，所以設(shè)計了B-Tree。B樹的目標是在 O(logn) 時間復(fù)雜度內(nèi)，完成一些動態(tài)操作。這種數(shù)據(jù)結(jié)構(gòu)多用于實現(xiàn)數(shù)據(jù)庫索引。紅黑二叉樹的時間復(fù)雜度也是 O(logn) ，但是B樹可以比紅黑二叉樹存儲更多的節(jié)點。屬于查找的應(yīng)用。

一顆3階B樹

一顆4階B樹

一顆 m 階的B樹，或為空樹，或為滿足下列特性的 m 叉樹：

(1)樹中的每個結(jié)點

；

(2)若

不是葉子結(jié)點，則

，

；

，

；

(3)除根結(jié)點外，

，

；

，

；

【例】在一棵高度為2的5階B樹中，所含關(guān)鍵字的個數(shù)最少是5。因為根結(jié)點關(guān)鍵字是5個的時候會產(chǎn)生分裂，高度正好變?yōu)?

(4)n個結(jié)點的m階B樹的

范圍：

(5)n個非葉結(jié)點的m階B樹

包含的關(guān)鍵字個數(shù)：

(6)所有葉節(jié)點都在同一層

B樹中的葉結(jié)點又叫外部結(jié)點，類似于查找判定樹的查找失敗結(jié)點，實際上這些點并不存在。

結(jié)合下例理解：

一棵5階B樹

一棵5階B樹特點總結(jié)

B樹的關(guān)鍵字插入和刪除操作：

插入操作涉及到結(jié)點分裂的問題

image.png

刪除操作涉及到結(jié)點合并的問題

情況一： 被刪關(guān)鍵字是非終端結(jié)點，則先用其前驅(qū)或后繼結(jié)點替代它，使得被刪結(jié)點落到終端結(jié)點，然后走情況二；

先用前驅(qū)結(jié)點替代被刪結(jié)點

情況二： 被刪關(guān)鍵字在終端結(jié)點

step1. 結(jié)點關(guān)鍵字個數(shù)

?m/2?，直接刪除，否則走step2

step2. 兄弟夠借：被刪關(guān)鍵字所在的結(jié)點關(guān)鍵字個數(shù)為?m/2?-1 ，其左/右兄弟結(jié)點關(guān)鍵字個數(shù)

?m/2?，此時采用“父子換位法“執(zhí)行刪除操作；否則走step3

step3. 兄弟不夠借，被刪關(guān)鍵字所在的結(jié)點關(guān)鍵字個數(shù)為?m/2?-1 ，其左/右兄弟結(jié)點關(guān)鍵字個數(shù)也是?m/2?-1，則需將左/右兄弟結(jié)點關(guān)鍵字與父級結(jié)點關(guān)鍵字進行合并

image.png

B+樹

B+樹是應(yīng)數(shù)據(jù)庫所需而生的一種B樹的變形樹，相對于B樹來說B+樹更充分的利用了節(jié)點的空間，磁盤讀寫代價更低，查詢速度更加穩(wěn)定，其速度完全接近于二分法查找。適應(yīng)于操作系統(tǒng)中的文件索引和數(shù)據(jù)庫索引。B+樹既能順序查找，也能索引查找。

一顆4階B+樹

一棵m階的B+樹需滿足下列條件：

(1)每個分支結(jié)點最多有 m 顆子樹(孩子結(jié)點)；

(2)根結(jié)點(若不是葉結(jié)點)至少有1個關(guān)鍵字，2顆子樹，至多m個關(guān)鍵字，m顆子樹；其它非葉結(jié)點至少有?m/2?個關(guān)鍵字，?m/2?顆子樹，至多有m個關(guān)鍵字，m顆子樹；

(3)結(jié)點的子樹個數(shù)與關(guān)鍵字個數(shù)相等；

(4)所有葉結(jié)點包含全部關(guān)鍵字以及指向相應(yīng)記錄的指針，葉結(jié)點中將關(guān)鍵字按大小順序排列，并且相鄰葉結(jié)點按大小順序相互鏈接起來。

(5)所有分支結(jié)點(可視為索引的索引)中僅包含它的各個子結(jié)點(即下一級的索引塊)中關(guān)鍵字的最大值及指向其子結(jié)點的指針；

一顆m階的B+樹與B樹的差異在于：

(1)在B+樹中，具有n個關(guān)鍵字的結(jié)點只含有n棵子樹，即每個關(guān)鍵字對應(yīng)一顆子樹；在B樹中，具有n個關(guān)鍵字的結(jié)點含有n+1顆子樹

(2)在B+樹中，每個結(jié)點(非根內(nèi)部結(jié)點)的關(guān)鍵字個數(shù) n 的范圍是?m/2?

n

m(根節(jié)點：1

n

m)；在B樹，每個結(jié)點(非根內(nèi)部結(jié)點)的關(guān)鍵字個數(shù)n的范圍是?m/2?-1

n

m - 1(根節(jié)點：1

n

m - 1)

(3)在B+樹中，葉結(jié)點包含信息，所有非葉結(jié)點僅起索引作用，非葉結(jié)點中的每個索引項只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針，不含有該關(guān)鍵字對應(yīng)記錄的存儲地址。

(4)在B+樹中，所有葉子結(jié)點中包含了全部關(guān)鍵字的信息，以及指向這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接；即在非葉結(jié)點中出現(xiàn)的關(guān)鍵字也會出現(xiàn)在葉節(jié)點；而在B樹中，葉結(jié)點包含的關(guān)鍵字和其它結(jié)點包含的關(guān)鍵字是不重復(fù)的。

紅黑樹

紅黑樹(Red Black Tree) 是一種自平衡二叉查找樹，它是一種特化的AVL樹，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。若一棵二叉查找樹是紅黑樹，則它的任一子樹必為紅黑樹。

性質(zhì)：

(1)節(jié)點是紅色或黑色；

(2)根節(jié)點是黑色；

(3)所有葉子都是黑色；

(4)每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)

(5)從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點；

應(yīng)用：紅黑樹已廣泛應(yīng)用Linux 的進程管理、內(nèi)存管理，設(shè)備驅(qū)動及虛擬內(nèi)存跟蹤等一系列場景中。

鍵樹(數(shù)字查找樹)

是一顆度

2的樹，樹中的每個結(jié)點中不是包含一個或幾個關(guān)鍵字，而是只含有組成關(guān)鍵字的符號。

總結(jié)

以上是生活随笔為你收集整理的k叉树的性质_相关树及性质的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。