二叉搜索樹（BST best search tree）：

右子節點的關鍵值總是大于或者等于此節點的關鍵值，左子節點的關鍵值總是小于該節點的關鍵值。

這樣在檢索的時候能實現二分法的檢索，時間復雜度log2(n)

可見BST樹的形成，使我們在存儲的時候，就選擇性的存儲，去塑造一個二叉搜索樹。可見數據有效能的檢索的前提是我們有意愿的塑造一個規整的數據結構！！這句話不僅僅體現在數據結構上，更是體現在我們的算法上，算法就是包含數據結構的。在數據庫系統中，如何塑造有效的查詢或者先關的條件查詢，這種思維認識也是體現的很明顯。

二叉平衡樹(AVL ?Adelson-Velskii和Landis于1962年首先提出的,所以又稱為AVL樹)：

定義：左右子樹的度的差值的絕對值不超過1. 且左右子樹也是一個平衡樹。且平衡樹具備BST的特性。

說白了平衡樹是嚴格上的BST樹，嚴格在于要求樹的度達到最小值。盡量在要求節點關鍵值右大左小的同時，要求根節點的關鍵值位于一堆數字的中間，而且依次類推。

這樣可以最大限度達到log2(n)的時間復雜度。

可見這里又再次體現我們如果實現有效快速的查詢檢索，就要盡量在保存數據的時候，做到數據的合理有序存儲化，也就是在存儲的時候我們需要耗費一定的時間。也就是將一定的時間復雜度分配給存儲的過程。

B-樹 ：是一種多路搜索樹（并不是二叉的）：（數據庫索引就是使用這類樹，如B-,B+,B*,說白了就是多路搜索）

?????? 1.定義任意非葉子結點最多只有M個兒子；且M>2；（這句話倒不如這么說：非葉子節點的兒子數可以是0,1,2......N，不包括根節點）

?????? 2.根結點的兒子數為[2, M]；（節點數可以是2,3,4......）（M是節點關鍵字數，那么子節點的數是小于或者等于或者是關鍵字數+1；這三種條件。為什么這樣，是因為這樣才能使得關鍵字數和子節點分支對應上，才能構成條件分支多路檢索，每一個關鍵字數值成為訪問具體的子節點的條件。當子節點數=關鍵字數+1，相當于n個模板造就n+1的分割空間）

?????? 3.除根結點以外的非葉子結點的兒子數為[M/2, M]；

?????? 4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字和最多M-1個關鍵字，那么總有節點數小于等于關鍵字數或者為關鍵字數+1）

?????? 5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；（嚴格要求的非葉子節點的關鍵字數必須飽和狀態）

?????? 6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；（關鍵字順序關系）

?????? 7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的

子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；

?????? 8.所有葉子結點位于同一層；

? ?M=3

B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經是葉子結點.

B-樹的特性：

? ? ? ?1.關鍵字集合分布在整顆樹中；
? ? ? ?2.任何一個關鍵字出現且只出現在一個結點中；
? ? ? ?3.搜索有可能在非葉子結點結束；
? ? ? ?4.其搜索性能等價于在關鍵字全集內做一次二分查找；
? ? ? ?5.自動層次控制；
? ? ? ?由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少

利用率，其最底搜索性能為：

其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；所以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題；?由于M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各占M/2的結點；刪除結點時，需將兩個不足M/2的兄弟結點合并.

B+樹：是B-樹的變體，也是一種多路搜索樹.

? ? ? ?1.其定義基本與B-樹同，除了：
? ? ? ?2.非葉子結點的子樹指針與關鍵字個數相同；
? ? ? ?3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹
（B-樹是開區間）；
? ? ? ?5.為所有葉子結點增加一個鏈指針；
? ? ? ?6.所有關鍵字都在葉子結點出現；

M=3

B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；
B+的特性：
1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的；
2.不可能在非葉子結點命中；
3.非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）數據的數據層；
4.更適合文件索引系統；

B*樹：是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針。

?B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2），?B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據
復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針；B*樹的分裂：當一個結點時，如果它的下一個兄弟結點未滿，那么將一部分數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針；?所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高。

M=3
?

總結

以上是生活随笔為你收集整理的对几种二叉树的简单理解的全部內容，希望文章能夠幫你解決所遇到的問題。

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