40
二叉搜索、 B- 、B+、 紅黑 、AVL 樹
二叉搜索樹
1.所有非葉子結點至多擁有兩個兒子（Left和Right）；
2.所有結點存儲一個關鍵字；
3.非葉子結點的左指針指向小於其關鍵字的子樹，右指針指向大於其關鍵字的子樹。
搜索：從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那麼就命中；否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字。
B-樹
1. M階B-樹是一種多路平衡搜索樹（並不是二叉的）：
2. 根結點的兒子數為[2, M]；
3. 除根結點以外的非葉子結點的兒子數為[M/2, M]；
4. 所有葉結點都為空且位於同一層；
5. 若一個非葉結點有n個孩子，那麼它有n-1個關鍵字，結構見下：
|
n-1 |
P0 |
K1 |
P1 |
K2 |
P2 |
... |
Kn-1 |
Pn-1 |
表一：非葉結點存放的數據
K[1], K[2], …, K[n-1]為非葉子結點的關鍵字且K[i] < K[i+1]；
P[i]為指向孩子節點的指針。其中P[i-1]所指結點的關鍵字全小於K[i],P[i]所指結點的關鍵字全大於K[i]。
B-樹的搜索：從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複，直到所對應的兒子指針為空，或已經是葉子結點。
B-樹的插入：找到待插入結點並插入。若所在結點關鍵字個數等於孩子數，進行分裂。若分裂後導致父節點關鍵字個數等於孩子數，再進行父節點的分裂。
B-樹的刪除：若刪除後導致所在結點關鍵字個數等於M/2(向上取整)-2，需要對節點進行合並。
B-樹舉例：
B+樹
B+樹也是多路平衡查找樹，與B-樹的區別在於：
1.含有n個關鍵字的結點有n個孩子。
2.B+樹中所有非葉結點僅起到索引作用，不含待查元素的存儲地址。
3.葉結點包含了全部元素的關鍵字和存儲地址。
4.非葉結點的存儲結構見下：
|
n |
k1 |
p1 |
k2 |
p2 |
... |
kn |
pn |
Ki為關鍵字，pi指向的孩子結點，其關鍵字的最大值為Ki。
舉例：
紅黑樹
紅黑樹是一種二叉查找樹。因結點帶有顏色屬性而得名。
在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。
性質：
1.每個節點都有顏色屬性，非紅即黑。
2.根節點和每個葉節點（NIL節點，空節點）是黑色的。
3.每個紅色節點的兩個孩子節點都是黑色。
4.對於任意一節點，它到其所有後代葉子節點的簡單路徑，均包含相同數目的黑色節點。
4.左孩子<根結點<右孩子。
這些約束強製了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。
舉例：
AVL 樹
自平衡二叉查找樹。
紅黑樹與AVL的比較
AVL是嚴格平衡樹，因此在增加或者刪除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多；紅黑是用非嚴格的平衡來換取增刪節點時候旋轉次數的降低；
所以簡單說，如果你的應用中，搜索的次數遠遠大於插入和刪除，那麼選擇AVL，如果搜索，插入刪除次數幾乎差不多，應該選擇RB。
最後更新：2017-04-03 12:55:58