B樹、B-樹、B+樹與紅黑樹

二叉查找樹（BST）：

二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
（4）沒有鍵值相等的節點（因此，插入的時候一定是葉子節點）。
插入有序節點，退化成單支樹
1.查找效率最好O(logn)，最壞O(n)
2.插入效率和查找效率相同（只插入葉子節點）
3.刪除效率最好O(logn)+O(1)->只有左子樹或者右子樹
最差O(logn)+O(logn)->左子樹和右子樹同時存在
1
2
3
4
5
6
7
8
9
10
11

插入刪除演算法

插入演算法

首先執行查找演算法，找出被插結點的父親結點。

判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。

若二叉樹為空。則首先單獨生成根結點。

注意：新插入的結點總是葉子結點。

刪除演算法

1. 若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構，則可以直接刪除此子結點。
2. 若*p結點只有左子樹PL或右子樹PR，此時只要令PL或PR直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。
3. 若*p結點的左子樹和右子樹均不空。在刪去*p之後，為保持其它元素之間的相對位置不變，可按中序遍歷保持有序進行調整，可以有兩種做法：
4. 其一是令*p的左子樹為*f的左/右(依*p是*f的左子樹還是右子樹而定)子樹，*s為*p左子樹的最右下的結點，而*p的右子樹為*s的右子樹；
5. 其二是令*p的直接前驅（或直接後繼）替代*p，然後再從二叉排序樹中刪去它的直接前驅（或直接後繼）－即讓*f的左子樹(如果有的話)成為*p左子樹的最左下結點(如果有的話)，再讓*f成為*p的左右結點的父結點。
6. 在二叉排序樹上刪除一個結點的演算法如下：

package 二叉查找樹;
public class Main {
private static class BinnarySearchTree {
private class Node {
private Node left = null;
private Node right = null;
private Node parent = null;
private Integer value = null;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node(Node left, Node right, Node parent, Integer value) {
super();
this.left = left;
this.right = right;
this.parent = parent;
this.value = value;
}
}
private Node root = null;
public void insert(Integer value) throws Exception {
insertNode(new Node(null, null, null, value));
}
private void insertNode(Node node) throws Exception {
Node pre = null;
Node x = this.root;
while (x != null) {
pre = x;
if (x.getValue() > node.getValue()) {
x = x.getLeft();
} else if (x.getValue() < node.getValue()) {
x = x.getRight();
} else {
throw new Exception("value is existed");
}
}
if (pre != null) {
if (node.getValue() < pre.getValue()) {
pre.setLeft(node);
} else {
pre.setRight(node);
}
node.setParent(pre);
} else {
// 根節點
this.root = node;
}
}
public Node find(Integer value) {
Node x = root;
while (x != null && x.getValue() != value) {
if (x.getValue() > value) {
x = x.getLeft();
} else if (x.getValue() < value) {
x = x.getRight();
}
}
return x;
}
public void delete(Integer value) throws Exception {
Node x = find(value);
if (x != null) {
if (x.getLeft() == null && x.getRight() == null) {
// 葉子節點
x.setLeft(null);
x.setRight(null);
} else if (x.getLeft() != null) {
// 左子樹不為空
Node y = x.getLeft();
while (y.getRight() != null) {
y = y.getRight();
}
x.setValue(y.getValue());
System.out.println(y.getParent());
y.getParent().setRight(null);
} else {
// 右子樹不為空
Node y = x.getRight();
if (x.getParent() != null) {
y.setLeft(x.getLeft());
if (x.getParent().getValue() > x.getValue()) {
x.getParent().setLeft(y);
} else {
x.getParent().setRight(y);
}
} else {
// 根節點
this.root = y;
}
}
} else {
throw new Exception("value is not exists");
}
}
public void inOrder(Node node) {
if (node != null && node.getValue() != null) {
inOrder(node.getLeft());
System.out.println(node.getValue());
inOrder(node.getRight());
}
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
}
public static void main(String[] args) throws Exception {
BinnarySearchTree bt = new BinnarySearchTree();
bt.insert(7);
bt.insert(11);
bt.insert(8);
bt.insert(12);
bt.insert(9);
bt.insert(13);
bt.insert(10);
bt.inOrder(bt.getRoot());
System.out.println("----------------------");
bt.delete(11);
bt.inOrder(bt.getRoot());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

平衡二叉查找樹

平衡二叉樹參考1

平衡二叉樹參考2

平衡二叉搜索樹：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O（log2n），大大降低了操作的時間複雜度。

調整平衡的基本思想：

當在二叉排序樹中插入一個節點時，首先檢查是否因插入而破壞了平衡，若破壞，則找出其中的最小不平衡二叉樹，在保持二叉排序樹特性的情況下，調整最小不平衡子樹中節點之間的關係，以達到新的平衡。

所謂最小不平衡子樹，指離插入節點最近且以平衡因子的絕對值大於1的節點作為根的子樹。

先插入指定節點，記錄下當前節點的信息，LH，EH或者RH。

1. 若左子樹高LH，查看其左子樹根節點的信息，若是LH，則一次右旋；若是RH，則一次左旋+一次右旋

2. 若右子樹高RH，查看右子樹根節點的信息，若是RH，則一次左旋；若是LH，則一次右旋+一次左旋

3. 調整改變的節點信息

追求絕對的高度平衡，隨著樹的高度的增加，動態插入和刪除的代價也隨之增加

紅黑樹

紅黑樹參考

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹

紅黑樹和AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。

二叉平衡樹的嚴格平衡策略以犧牲建立查找結構(插入，刪除操作)的代價，換來了穩定的O(logN) 的查找時間複雜度

它雖然是複雜的，但它的最壞情況運行時間也是非常良好的，並且在實踐中是高效的： 它可以在O(log n)時間內做查找，插入和刪除，這裡的n 是樹中元素的數目。

(1) 每個節點或者是黑色，或者是紅色。
(2) 根節點是黑色。
(3) 每個葉子節點是黑色。 [注意：這裡葉子節點，是指為空的葉子節點！]
(4) 如果一個節點是紅色的，則它的子節點必須是黑色的。
(5) 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
1
2
3
4
5

RBT 的操作代價分析：

(1) 查找代價：由於紅黑樹的性質(最長路徑長度不超過最短路徑長度的2倍)，可以說明紅黑樹雖然不像AVL一樣是嚴格平衡的，但平衡性能還是要比BST要好。其查找代價基本維持在O(logN)左右，但在最差情況下(最長路徑是最短路徑的2倍少1)，比AVL要略遜色一點。

(2) 插入代價：RBT插入結點時，需要旋轉操作和變色操作。但由於只需要保證RBT基本平衡就可以了。因此插入結點最多只需要2次旋轉，這一點和AVL的插入操作一樣。雖然變色操作需要O(logN)，但是變色操作十分簡單，代價很小。

(3) 刪除代價：RBT的刪除操作代價要比AVL要好的多，刪除一個結點最多只需要3次旋轉操作。

RBT 效率總結 : 查找 效率最好情況下時間複雜度為O(logN)，但在最壞情況下比AVL要差一些，但也遠遠好於BST。

插入和刪除操作改變樹的平衡性的概率要遠遠小於AVL（RBT不是高度平衡的）。因此需要的旋轉操作的可能性要小，而且一旦需要旋轉，插入一個結點最多只需要旋轉2次，刪除最多只需要旋轉3次(小於AVL的刪除操作所需要的旋轉次數)。雖然變色操作的時間複雜度在O(logN)，但是實際上，這種操作由於簡單所需要的代價很小。

紅黑樹能夠以O(log2(N))的時間複雜度進行搜索、插入、刪除操作。此外,任何不平衡都會在3次旋轉之內解決。這一點是AVL所不具備的。

插入操作：
1.插入根節點（不需要操作）
2.父節點為黑色(不需要操作)
3.父節點和兄弟節點為紅色，祖父節點為黑色，只需要變色，將祖父節點遞歸檢查（原本檢查自己）
4.父節點為紅色，兄弟節點為黑色，祖父節點為紅色，先兩次旋轉再調整顏色（左旋+右旋）
1
2
3
4
5
刪除操作：
1.刪除只有一個新的根節點（直接刪除）
2.父節點為黑色，兄弟節點為紅色（先旋轉成左左，再刪除）
3.父節點為黑色，兄弟節點為黑色（先將兄弟節點換成紅色，變成情況2）
4.父節點為紅色，自己和兄弟節點為黑色（將父節點變成黑色，兄弟節點變成紅色，變成情況2）
5.兄弟節點為黑色，兄弟節點左子樹根節點為紅色（交換顏色，旋轉成為左左）
6.情況2和情況5，調整性質5（將N刪掉，用子節點頂替，若子節點為紅色，則重繪為黑色）
1
2
3
4
5
6
7

參考

B樹（多叉查找樹）：

1、根結點至少有兩個子女；

2、每個非根節點所包含的關鍵字個數 j 滿足：m/2 - 1 <= j <= m - 1；

3、除根結點以外的所有結點（不包括葉子結點）的度數正好是關鍵字總數加1，故內部子樹個數 k 滿足：m/2<= k <= m ；

4、所有的葉子結點都位於同一層。

B-樹

1、關鍵字集合分布在整棵樹中；

2、任何一個關鍵字出現且只出現在一個結點中；

3、搜索有可能在非葉子結點結束；

4、其搜索性能等價於在關鍵字全集內做一次二分查找；

5、自動層次控制；

m階B-樹

1) 樹中每個結點至多有m個孩子；

2) 除根結點和葉子結點外，其它每個結點至少有[m/2]個孩子；

3) 若根結點不是葉子結點，則至少有2個孩子；

4) 所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結點不存在，指向這些結點的指針都為null)；

5) 每個非終端結點中包含有n個關鍵字信息： (n，A0，K1，A1，K2，A2，……，Kn，An)。其中，

a) Ki (i=1…n)為關鍵字，且關鍵字按順序排序Ki < K(i-1)。

b) Ai為指向子樹根的接點，且指針A(i-1)指向子樹種所有結點的關鍵字均小於Ki，但都大於K(i-1)。

c) 關鍵字的個數n必須滿足： [m/2]-1 <= n <= m-1

建立

由於B~樹結點中的關鍵字個數必須>=[m/2]-1。因此和平衡二叉樹不同，每一次插入一個關鍵字並不是在樹中添加一個結點，而是首先在最低層的某個非終端結點中添加一個關鍵字，若該結點的關鍵字個數不超過m-1，則插入完成。否則，要產生結點的」分裂」 。

外存

我們現在把整棵樹構造在磁碟中，假如每個盤塊可以正好存放一個B~樹的結點（正好存放2個文件名）。那麼一個BTNode結點就代表一個盤塊，而子樹指針就是存放另外一個盤塊 （詳細見《外部存儲器—磁碟 》）的地址。

現在我們模擬查找文件29的過程：

(1) 根據根結點指針找到文件目錄的根磁碟塊1，將其中的信息導入內存。【磁碟IO操作1次】

(2) 此時內存中有兩個文件名17，35和三個存儲其他磁碟頁面地址的數據。根據演算法我們發現17<29<35，因此我們找到指針p2。

(3) 根據p2指針，我們定位到磁碟塊3，並將其中的信息導入內存。【磁碟IO操作2次】

(4) 此時內存中有兩個文件名26，30和三個存儲其他磁碟頁面地址的數據。根據演算法我們發現26<29<30，因此我們找到指針p2。

(5) 根據p2指針，我們定位到磁碟塊8，並將其中的信息導入內存。【磁碟IO操作3次】

(6) 此時內存中有兩個文件名28，29。根據演算法我們查找到文件29，並定位了該文件內存的磁碟地址。

分析一下上面的過程，我們發現需要3次磁碟IO操作和3次內存查找操作。關於內存中的文件名查找，由於是一個有序表結構，可以利用折半查找提高效率。至於3次磁碟IO操作時影響整個B~樹查找效率的決定因素。
當然，如果我們使用平衡二叉樹的磁碟存儲結構來進行查找，磁碟IO操作最少4次，最多5次。而且文件越多，B~樹比平衡二叉樹所用的磁碟IO操作次數將越少，效率也越高。
1
2

B+樹：

B+ 樹是一種樹數據結構，是一個n叉樹，每個節點通常有多個孩子，一顆B+樹包含根節點、內部節點和葉子節點。根節點可能是一個葉子節點，也可能是一個包含兩個或兩個以上孩子節點的節點。

B+ 樹通常用於資料庫和操作系統的文件系統中。

NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系統都在使用B+樹作為元數據索引。

B+ 樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間複雜度。

B+ 樹元素自底向上插入。

所有的葉子結點中包含了全部關鍵字的信息，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序鏈接。(而B 樹的葉子節點並沒有包括全部需要查找的信息)

所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。(而B 樹的非終節點也包含需要查找的有效信息)

1) 有n棵子樹的結點中含有n個關鍵字； (B~樹是n棵子樹有n+1個關鍵字)
2) 所有的葉子結點中包含了全部關鍵字的信息，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序鏈接。 (B~樹的葉子節點並沒有包括全部需要查找的信息)
3) 所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。 (B~樹的非終節點也包含需要查找的有效信息)
B+樹的有效內容均在葉子節點，B-樹的有效內容不全在葉子節點上
B+樹的頭指針有兩個，一個指向根節點，另一個指向關鍵字最小的元素，因此B+樹有兩種遍歷的方式：
1.從根節點開始隨機查詢
2.從最小關鍵詞順序查詢
1
2
3
4
5
6
7
8

B*樹

為什麼說B+樹比B 樹更適合實際應用中操作系統的文件索引和資料庫索引？

B+樹的磁碟讀寫代價更低

B+樹的內部結點並沒有指向關鍵字具體信息的指針。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。

舉個例子，假設磁碟中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體信息指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的內部結點需要2個盤快。而B+樹內部結點只需要1個盤快。當需要把內部結點讀入內存中的時候，B 樹就比B+樹多一次盤塊查找時間(在磁碟中就是碟片旋轉的時間)。

B+樹的查詢效率更加穩定

由於非終結點並不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

B+樹和B-樹的區別

B+樹

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

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

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.所有葉子結點位於同一層；
1
2
3
4
5
6
7
8

紅黑樹和平衡二叉樹區別如下：

1、紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間複雜度相差不大的情況下，保證每次插入最多只需要三次旋轉就能達到平衡，實現起來也更為簡單。

2、平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節點之後需要旋轉的次數不能預知。

小結

B-樹：多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字範圍的子結點；所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中；B+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；B*樹：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3；

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！