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 <class K>
 2 struct BinarySearchTreeNode
 3 {
 4     BinarySearchTreeNode<K>* _left;  //指向左子树
 5     BinarySearchTreeNode<K>* _right;  //指向右子树
 6     K _key;  //关键码
 7     BinarySearchTreeNode(const K& key) 
 8         :_left(NULL)
 9         ,_right(NULL)
10         ,_key(key)
11     {}
12 };

如下图，这个是普通的二叉树，它具有普通二叉树的所有性质。

在此基础上，加上上面所述节点之间的大小关系，就是二叉查找树：

下面这个是二叉搜索树，可以很清晰的看出节点之间的大小关系：

而二叉搜索树里面真正有意义的是对其节点的增、删、查找等操作，下面我分别来介绍这几种算法原理。

二、算法操作

由内部节点构建二叉搜索树如下：

 1 template<class K>
 2 class     BinarySearchTree
 3 {
 4     typedef BinarySearchTreeNode<K> 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<iostream>
  2 using namespace std;
  3 
  4 template <class K>
  5 struct BinarySearchTreeNode
  6 {
  7     BinarySearchTreeNode<K>* _left;
  8     BinarySearchTreeNode<K>* _right;
  9     K _key;
 10     BinarySearchTreeNode(const K& key) 
 11         :_left(NULL)
 12         ,_right(NULL)
 13         ,_key(key)
 14     {}
 15 };
 16 
 17 template<class K>
 18 class     BinarySearchTree
 19 {
 20     typedef BinarySearchTreeNode<K> 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<int> 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 }

部分测试代码的输出结果：

本文部分图示来自于：http://www.cnblogs.com/yangecnu/p/Introduce-Binary-Search-Tree.htm