BST二叉搜尋樹
1.所有非葉子結點至多擁有兩個兒子（Left和Right）；
2.所有結點存儲一個關鍵字；
3.非葉子結點的左指針指向小于其關鍵字的子樹，右指針指向大于其關鍵字的子樹；
如：
二叉搜尋樹的搜尋，從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那麼就命中；
否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入
右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字；
如果二叉搜尋樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那麼二叉搜尋樹
的搜尋性能逼近二分查找；但它比連續記憶體空間的二分查找的優點是，改變BST樹結構
（插入與删除結點）不需要移動大段的記憶體資料，甚至通常是常數開銷；
如：
但BST樹在經過多次插入與删除後，有可能導緻不同的結構：
右邊也是一個BST樹，但它的搜尋性能已經是線性的了；同樣的關鍵字集合有可能導緻不同的
樹結構索引；是以，使用B樹還要考慮盡可能讓B樹保持左圖的結構，和避免右圖的結構，也就
是所謂的“平衡”問題；
實際使用的BST樹都是在原BST樹的基礎上加上平衡算法，即“平衡二叉樹”；如何保持BST樹
結點分布均勻的平衡算法是平衡二叉樹的關鍵；平衡算法是一種在B樹中插入和删除結點的
政策；
B樹，B-樹
是一種多路搜尋樹（并不是二叉的）：
1.定義任意非葉子結點最多隻有M個兒子；且M>2；
2.根結點的兒子數為[2, M]；
3.除根結點以外的非葉子結點的兒子數為[M/2, M]；
4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
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+樹是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+樹要低，空間使用率更高；
小結
B樹：二叉樹，每個結點隻存儲一個關鍵字，等于則命中，小于走左結點，大于
走右結點；
B-樹：多路搜尋樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵
字範圍的子結點；
所有關鍵字在整顆樹中出現，且隻出現一次，非葉子結點可以命中；
B+樹：在B-樹基礎上，為葉子結點增加連結清單指針，所有關鍵字都在葉子結點
中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；
B*樹：在B+樹基礎上，為非葉子結點也增加連結清單指針，将結點的最低使用率
從1/2提高到2/3；
紅黑樹：
紅黑樹雖然本質上是一棵二叉查找樹，但它在二叉查找樹的基礎上增加了着色和相關的性質使得紅黑樹相對平衡，進而保證了紅黑樹的查找、插入、删除的時間複雜度最壞為O(log n)。
但它是如何保證一棵n個結點的紅黑樹的高度始終保持在logn的呢？這就引出了紅黑樹的5個性質：
- 每個結點要麼是紅的要麼是黑的。
- 根結點是黑的。
- 每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）都是黑的。
- 如果一個結點是紅的，那麼它的兩個兒子都是黑的。
- 對于任意結點而言，其到葉結點樹尾端NIL指針的每條路徑都包含相同數目的黑結點。
正是紅黑樹的這5條性質，使一棵n個結點的紅黑樹始終保持了logn的高度，進而也就解釋了上面所說的“紅黑樹的查找、插入、删除的時間複雜度最壞為O(log n)”這一結論成立的原因。
（注：上述第3、5點性質中所說的NULL結點，包括wikipedia.算法導論上所認為的葉子結點即為樹尾端的NIL指針，或者說NULL結點。然百度百科以及網上一些其它博文直接說的葉結點，則易引起誤會，因，此葉結點非子結點）
如下圖所示，即是一顆紅黑樹(下圖引自wikipedia：http://t.cn/hgvH1l)：
此圖忽略了葉子和根部的父結點。同時，上文中我們所說的 "葉結點" 或"NULL結點"，如上圖所示，它不包含資料而隻充當樹在此結束的訓示，這些節點在繪圖中經常被省略，望看到此文後的讀者朋友注意。
備注：轉http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html