BinarySearchTree-二叉搜索樹

一、二叉搜索樹的定義及性質

二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

1. 每個節點都有一個作為搜索依據的關鍵碼（ key） ， 所有節點的關鍵碼互不相同。

2. 左子樹上所有節點的關鍵碼（ key） 都小於根節點的關鍵碼（ key） 。

3. 右子樹上所有節點的關鍵碼（ key） 都大於根節點的關鍵碼（ key） 。

4. 左右子樹都是二叉搜索樹。

在實現中，由它的性質可以初步簡單的定義出節點信息，我們需要定義一個內部類BinarySearchTreeNode，它包含兩個分別指向左右節點的Node->_left和Node->_right，一個保存鍵值信息的Key。

1 template
2 struct BinarySearchTreeNode
3 {
4 BinarySearchTreeNode* _left; //指向左子樹
5 BinarySearchTreeNode* _right; //指向右子樹
6 K _key; //關鍵碼
7 BinarySearchTreeNode(const K& key)
8 :_left(NULL)
9 ,_right(NULL)
10 ,_key(key)
11 {}
12 };

如下圖，這個是普通的二叉樹，它具有普通二叉樹的所有性質。

在此基礎上，加上上面所述節點之間的大小關係，就是二叉查找樹：

下面這個是二叉搜索樹，可以很清晰的看出節點之間的大小關係：

而二叉搜索樹裡面真正有意義的是對其節點的增、刪、查找等操作，下面我分別來介紹這幾種演算法原理。

由內部節點構建二叉搜索樹如下：

1 template
2 class BinarySearchTree
3 {
4 typedef BinarySearchTreeNode Node;
5 public:
6 BinarySearchTree
7 :_root(NULL)
8 {}
9 ~BinarySearchTree
10 {
11 _Delete(_root);
12 }
13 //非遞歸
14 bool Insert(const K& key) //插入
15 {
16 return _Insert(_root, key);
17 }
18 bool Remove(const K& key) //刪除
19 {
20 return _Remove(_root, key);
21 }
22 const Node* Find(const K& key) //查找
23 {
24 return _Find(_root, key);
25 }
26 //遞歸
27 bool InsertR(const K& key)
28 {
29 return _InsertR(_root, key);
30 }
31 bool RemoveR(const K& key)
32 {
33 return _RemoveR(_root, key);
34 }
35 const Node* FindR(const K& key)
36 {
37 return _FindR(_root, key);
38 }
39 void Inorder //遍歷列印
40 {
41 _Inorder(_root);
42 cout << endl; 43 } 44 private: 45 void _Delete(Node*& root); 46 bool _Insert(Node* root, const K& key); 47 bool _Remove(Node* root, const K& key); 48 Node* _Find(Node* root, const K& key); 49 bool _InsertR(Node*& root, const K& key); 50 bool _RemoveR(Node* & root, const K& key); 51 const Node*_FindR(Node* root, const K& key); 52 void _Inorder(Node* root); 53 private: 54 Node* _root; 55 };

1.查找

查找操作和二分查找類似，從根節點開始，將root->_key和要找的節點的key比較，如果root->_key小於要找的節點的key，那麼就在左子樹 _root->_left節點中查找,如果root->_key大於要找的節點的key，則在右子樹_root->_right節點中查找，如果_root->_key和要找的節點的key相等，直接返回此節點。

查找操作圖示如下：

該方法實現有遞歸和非遞歸兩種。

非遞歸演算法程序如下：

1 const Node* Find(const K& key)
2 {
3 return _Find(_root, key);
4 }
5 Node* _Find(Node* root, const K& key)
6 {
7 while (root) {
8 if (root->_key > key) //向左查找
9 root = root->_left;
10 if (root->_key < key) //向右查找 11 root = root->_right;
12 else
13 return root; //找到節點
14 }
15 return NULL;
16 }

遞歸演算法：

1 const Node* FindR(const K& key)
2 {
3 return _FindR(_root, key);
4 }
5 const Node*_FindR(Node* root, const K& key)
6 {
7 if (root == NULL)
8 return NULL;
9 if (root->_key > key)
10 return _FindR(root->_left, key); //向左遞歸查找
11 if (root->_key < key) 12 return _FindR(root->_right, key); //向右遞歸查找
13 else
14 return root; //找到該節點
15 }

2.插入

插入一個節點第一步與與查找類似，首先要找到應該插入節點的位置，因為插入節點後不能破壞二叉搜索樹的性質。首先判斷如果樹為空，則直接動態開闢節點並初始化為key插入即可，插入的節點即為根節點。然後再向下查找應該插入節點的位置，查找方法與上一個查找演算法類似，不同的是在查找的過程中要將應該插入的位置的父節點記錄下來。找到該位置後，將parent->_key與插入的key進行比較，判斷應該插入到父節點的左子樹還是右子樹。如果parent->_key小於要插入節點的key，那麼就插入為父節點的右子樹parent->_right = new Node(key); //插入右子樹；如果parent->_key大於要插入節點的key，那麼就插入為父節點的左子樹parent->_left = new Node(key); //插入左子樹。

插入操作圖示如下：

同樣，插入操作的實現也有遞歸和非遞歸兩種方法。

非遞歸法實現如下：

1 bool Insert(const K& key)
2 {
3 return _Insert(_root, key);
4 }
5 bool Insert(Node*& root， const K& key) {
6 if (root == NULL){ //當樹為空時，直接插入
7 root = new Node(key);
8 return true;
9 }
10 Node* cur = root;
11 Node* parent = cur;
12 while (cur) { //找到要插入的位置
13 if (cur->_key > key) {
14 parent = cur;
15 cur = cur->_left;
16 }
17 else if (cur->_key < key) { 18 parent = cur; 19 cur = cur->_right;
20 }
21 else
22 return false;
23 }
24 if (parent->_key < key) //找到插入位置的父節點，判斷應該是父節點的左子樹還是右子樹右 25 parent->_right = new Node(key); //插入右子樹
26 else
27 parent->_left = new Node(key); //插入左子樹
28 return true;
29 }

遞歸法實現如下：

1 bool InsertR(const K& key)
2 {
3 return _InsertR(_root, key);
4 }
5 bool _InsertR(Node*& root, const K& key) //注意：這裡參數傳遞方法是傳引用
6 {
7 if (root == NULL){
8 root = new Node(key);
9 return true;
10 }
11 if (root->_key > key)
12 return _InsertR(root->_left, key);
13 if (root->_key < key) 14 return _InsertR(root->_right, key);
15 else
16 return false;
17 }

3.刪除

刪除元素操作在二叉樹的操作中應該是比較複雜的。但是只要一步一步分析的話其實也是比較容易實現的。首先判斷該樹是否為空，為空的話直接返回刪除失敗；該是不為空時，第一步是找到需要刪除的節點，方法與前面的查找演算法類似，不同的是也需要將刪除的節點的父節點記錄下來，以判斷該節點刪除以後需要調整父節點的哪一個子樹。找到該節點後，複雜的地方才剛開始。

（1）當要刪除的節點的左子樹為空時，判斷是否為該節點是否為根節點，若是，則直接刪除，其右子樹的根節點成為新的根節點；若不是則再次判斷該節點在其父節點的哪個子樹上。若該節點在其父節點的左子樹上，則將該節點的右子樹連到該節點的父節點的左子樹上，然後將該節點刪除；若該節點在其父節點的右子樹上，則將該節點的右子樹連到該節點的父節點的右子樹上，然後將該節點刪除。

（2）當要刪除的節點的右子樹為空時，判斷是否為該節點是否為根節點，若是，則直接刪除，其左子樹的根節點成為新的根節點；若不是則再次判斷該節點在其父節點的哪個子樹上。若該節點在其父節點的左子樹上，則將該節點的左子樹連到該節點的父節點的左子樹上，然後將該節點刪除；若該節點在其父節點的右子樹上，則將該節點的左子樹連到該節點的父節點的右子樹上，然後將該節點刪除。（類似於（1））。

（3）當要刪除的節點的左右子樹都不為為空時，首先查找該節點的右子樹的最小節點，即找該節點的右子樹的最左節點，讓這個最小節點代替該節點的位置，然後將此最小節點刪除，這樣調整之後才能使此樹依然為搜索二叉樹，另外在查找最左節點時應將它的父節點記錄下來（原理同（1）和（2））。找到該節點的右子樹的最左節點後，將最左節點的值賦給要刪除的節點，作為新的該節點，其原值被覆蓋，後面再刪除的就是找到的最左節點。刪除之前判斷若此最左節點在其父節點的左子樹上，則將該節點的右子樹連到該節點的父節點的左子樹上，然後將該節點刪除；若該節點在其父節點的右子樹上（即右子樹最左節點為右子樹的根節點），則將該節點的右子樹連到該節點的父節點的右子樹上，然後將該節點刪除。（還有另一種方法，就是找到該節點的右子樹的最大節點，即最右節點，與該節點替換後再刪除，原理相同，此處不在贅述）。

此原理敘述起來較複雜，下面請看圖示情況分類：

當刪除的節點只有1個子節點時，在左邊和在右邊原理類似：

當刪除的節點有2個子節點時：

用具體的二叉查找樹舉例如下：

非遞歸法代碼如下：

1 bool Remove(const K& key) {
2 if (_root == NULL)
3 return false;
4 Node* del = _root;
5 Node* parent = del;
6 while (del) {
7 if (del->_key < key) { //向右搜索 8 parent = del; 9 del = del->_right;
10 }
11 if (del->_key > key) { //向左搜索
12 parent = del;
13 del = del->_left;
14 }
15 if (del->_key == key) { //要刪除的節點找到
16 Node* cur = del;
17 if (cur->_left == NULL) { //當此節點左子樹為空
18 if (_root->_key == key) //刪除根節點
19 _root = _root->_right;
20 else{
21 if(parent->_left == cur)
22 parent->_left = cur->_right; //當找到的節點在其父節點的左子樹上
23 else
24 parent->_right = cur->_right; //當找到的節點在其父節點的右子樹上
25 }
26 }
27 else if (cur->_right == NULL) { //當此節點右子樹為空
28 if (_root->_key == key)
29 _root = _root->_left;
30 else {
31 if (parent->_left == cur)
32 parent->_left = cur->_left;
33 else
34 parent->_right = cur->_left;
35 }
36 }
37 else{ //左右子樹都不為空
38 cur = cur->_right;
39 while (cur->_left) { //找右子樹的最左節點
40 parent = cur;
41 cur = cur->_left;
42 }
43 del->_key = cur->_key; //將最左節點的值給要刪除的節點，作為新的該節點，其原值被覆蓋
44 del = cur; //後面刪除的就是找到的最左節點
45 if (parent->_left == cur) //此時的cur是最左節點
46 parent->_left = cur->_right;
47 else
48 parent->_right = cur->_right; //右子樹最左節點為右子樹的根節點
49 }
50 delete del;
51 del = NULL;
52 return true;
53 }
54 }
55 return false;
56 }

遞歸法刪除節點代碼如下：

1 bool RemoveR(const K& key)
2 {
3 return _RemoveR(_root, key);
4 }
5 bool _RemoveR(Node* & root, const K& key) //注意此處傳引用
6 {
7 if (root == NULL)
8 return false;
9 if (root->_key > key)
10 return _RemoveR(root->_left, key); //向左遞歸搜索
11 if (root->_key < key) 12 return _RemoveR(root->_right, key); //向右遞歸搜索
13 else{ //要刪除的節點找到
14 Node* del = root;
15 if (root->_left == NULL)
16 root = root->_right;
17 if (root->_right == NULL)
18 root = root->_left;
19 else{
20 Node* cur = root;
21 Node* parent = cur;
22 cur = cur->_right;
23 while (cur->_left) {
24 parent = cur;
25 cur = cur->_left;
26 }
27 del->_key = cur->_key;
28 del = cur;
29 if (parent->_left = cur)
30 parent->_left = cur->_right;
31 else
32 parent->_right = cur->_right;
33 }
34 delete del;
35 del = NULL;
36 return true;
37 }
38 }

三、演算法分析與總結

二叉查找樹的運行時間和樹的形狀有關，樹的形狀又和插入元素的順序有關。在最好的情況下，節點完全平衡，從根節點到最底層葉子節點只有lgN個節點。在最差的情況下，根節點到最底層葉子節點會有N各節點。在一般情況下，樹的形狀和最好的情況接近。

在分析二叉查找樹的時候，我們通常會假設插入的元素順序是隨機的。對於N個不同元素，隨機插入的二叉查找樹來說，其平均查找/插入的時間複雜度大約為2lnN。

前面有對二分查找時間複雜度的分析，對二叉查找樹的理解可以類比於此。它和二分查找一樣，插入和查找的時間複雜度均為lgN，但是在最壞的情況下仍然會有N的時間複雜度。原因在於插入和刪除元素的時候，樹沒有保持平衡。我們追求的是在最壞的情況下仍然有較好的時間複雜度，這就是後面要講的平衡查找樹的內容了。

下面是二叉查找樹的時間複雜度：

1 #include
2 using namespace std;
3
4 template
5 struct BinarySearchTreeNode
6 {
7 BinarySearchTreeNode* _left;
8 BinarySearchTreeNode* _right;
9 K _key;
10 BinarySearchTreeNode(const K& key)
11 :_left(NULL)
12 ,_right(NULL)
13 ,_key(key)
14 {}
15 };
16
17 template
18 class BinarySearchTree
19 {
20 typedef BinarySearchTreeNode Node;
21 public:
22 BinarySearchTree
23 :_root(NULL)
24 {}
25 ~BinarySearchTree
26 {
27 _Delete(_root);
28 }
29 //非遞歸
30 bool Insert(const K& key)
31 {
32 return _Insert(_root, key);
33 }
34 bool Remove(const K& key)
35 {
36 return _Remove(_root, key);
37 }
38 const Node* Find(const K& key)
39 {
40 return _Find(_root, key);
41 }
42 //遞歸
43 bool InsertR(const K& key)
44 {
45 return _InsertR(_root, key);
46 }
47 bool RemoveR(const K& key)
48 {
49 return _RemoveR(_root, key);
50 }
51 const Node* FindR(const K& key)
52 {
53 return _FindR(_root, key);
54 }
55 void Inorder
56 {
57 _Inorder(_root);
58 cout << endl; 59 } 60 private: 61 void _Delete(Node*& root) 62 { 63 if (root) 64 { 65 _Delete(root->_left);
66 _Delete(root->_right);
67 delete root;
68 root = NULL;
69 }
70 return;
71 }
72 bool Insert(const K& key) {
73 if (_root == NULL){ //當樹為空時，直接插入
74 _root = new Node(key);
75 return true;
76 }
77 Node* cur = _root;
78 Node* parent = cur;
79 while (cur) { //找到要插入的位置
80 if (cur->_key > key) {
81 parent = cur;
82 cur = cur->_left;
83 }
84 else if (cur->_key < key) { 85 parent = cur; 86 cur = cur->_right;
87 }
88 else
89 return false;
90 }
91 if (parent->_key < key) //找到插入位置的父節點，判斷應該是父節點的左子樹還是右子樹右 92 parent->_right = new Node(key); //插入右子樹
93 else
94 parent->_left = new Node(key); //插入左子樹
95 return true;
96 }
97
98 bool Remove(const K& key) {
99 if (_root == NULL)
100 return false;
101 Node* del = _root;
102 Node* parent = del;
103 while (del) {
104 if (del->_key < key) { //向右搜索 105 parent = del; 106 del = del->_right;
107 }
108 if (del->_key > key) { //向左搜索
109 parent = del;
110 del = del->_left;
111 }
112 if (del->_key == key) { //要刪除的節點找到
113 Node* cur = del;
114 if (cur->_left == NULL) { //當此節點左子樹為空
115 if (_root->_key == key) //刪除根節點
116 _root = _root->_right;
117 else{
118 if(parent->_left == cur)
119 parent->_left = cur->_right; //當找到的節點在其父節點的左子樹上
120 else
121 parent->_right = cur->_right; //當找到的節點在其父節點的右子樹上
122 }
123 }
124 else if (cur->_right == NULL) { //當此節點右子樹為空
125 if (_root->_key == key)
126 _root = _root->_left;
127 else {
128 if (parent->_left == cur)
129 parent->_left = cur->_left;
130 else
131 parent->_right = cur->_left;
132 }
133 }
134 else{ //左右子樹都不為空
135 cur = cur->_right;
136 while (cur->_left) { //找右子樹的最左節點
137 parent = cur;
138 cur = cur->_left;
139 }
140 del->_key = cur->_key; //將最左節點的值給要刪除的節點，作為新的該節點，其原值被覆蓋
141 del = cur; //後面刪除的就是找到的最左節點
142 if (parent->_left == cur) //此時的cur是最左節點
143 parent->_left = cur->_right;
144 else
145 parent->_right = cur->_right; //右子樹最左節點為右子樹的根節點
146 }
147 delete del;
148 del = NULL;
149 return true;
150 }
151 }
152 return false;
153 }
154 Node* _Find(Node* root, const K& key)
155 {
156 while (root) {
157 if (root->_key > key) //向左查找
158 root = root->_left;
159 if (root->_key < key) //向右查找 160 root = root->_right;
161 else
162 return root; //找到節點
163 }
164 return NULL;
165 }
166
167
168 bool _InsertR(Node*& root, const K& key)
169 {
170 if (root == NULL){
171 root = new Node(key);
172 return true;
173 }
174 if (root->_key > key)
175 return _InsertR(root->_left, key);
176 if (root->_key < key) 177 return _InsertR(root->_right, key);
178 else
179 return false;
180 }
181 bool _RemoveR(Node* & root, const K& key)
182 {
183 if (root == NULL)
184 return false;
185 if (root->_key > key)
186 return _RemoveR(root->_left, key); //向左遞歸搜索
187 if (root->_key < key) 188 return _RemoveR(root->_right, key); //向右遞歸搜索
189 else{ //要刪除的節點找到
190 Node* del = root;
191 if (root->_left == NULL)
192 root = root->_right;
193 if (root->_right == NULL)
194 root = root->_left;
195 else{
196 Node* cur = root;
197 Node* parent = cur;
198 cur = cur->_right;
199 while (cur->_left) {
200 parent = cur;
201 cur = cur->_left;
202 }
203 del->_key = cur->_key;
204 del = cur;
205 if (parent->_left = cur)
206 parent->_left = cur->_right;
207 else
208 parent->_right = cur->_right;
209 }
210 delete del;
211 del = NULL;
212 return true;
213 }
214
215 }
216 const Node*_FindR(Node* root, const K& key)
217 {
218 if (root == NULL)
219 return NULL;
220 if (root->_key > key)
221 return _FindR(root->_left, key);
222 if (root->_key < key) 223 return _FindR(root->_right, key);
224 else
225 return root;
226 }
227 void _Inorder(Node* root)
228 {
229 if (root)
230 {
231 _Inorder(root->_left);
232 cout << root->_key << " "; 233 _Inorder(root->_right);
234 }
235 }
236 private:
237 Node* _root;
238 };
239 //測試代碼：
240 #include"SearchTree.h"
241
242 void Test
243 {
244 BinarySearchTree tree;
245 tree.InsertR(5);
246 tree.InsertR(1);
247 tree.Insert(2);
248 tree.InsertR(3);
249 tree.Insert(4);
250 tree.InsertR(9);
251 tree.Insert(8);
252 tree.InsertR(6);
253 tree.Insert(7);
254
255 cout << tree.FindR(5) << endl; 256 cout << tree.FindR(5) << endl; 257 cout << tree.FindR(9) << endl; 258 cout << tree.FindR(9) << endl; 259 cout << tree.Find(5) << endl; 260 cout << tree.Find(5) << endl; 261 cout << tree.Find(9) << endl; 262 cout << tree.Find(9) << endl; 263 264 tree.Inorder; 265 266 tree.RemoveR(5); 267 tree.RemoveR(4); 268 tree.RemoveR(1); 269 tree.Remove(9); 270 tree.Remove(2); 271 tree.Remove(3); 272 tree.Remove(6); 273 tree.Remove(7); 274 tree.Remove(8); 275 276 tree.~BinarySearchTree; 277 278 } 279 int main 280 { 281 Test; 282 getchar; 283 return 0; 284 }

部分測試代碼的輸出結果：

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