C++二叉搜刮树

c++ 二叉搜刮树

1、二叉搜刮树的概念

二叉搜刮树又被称为二叉排序树，他是一颗空树，大概是具有以下的性质：

• 如果他的左子树不是空的，则他的左子树节点的值小于等于根节点的值
  
• 若它的右子树节点不为空，则它的右子树上全部的节点的值都大于根节点的值。
  
• 他的左右子树也分别为二叉搜刮树
  
• 二叉搜刮树中可以支持插入相同值的节点，也可以不支持插入·相同节点的值，详细的情况要看详细的场景，后后续我们就会学习到map/set/multimap/mulset系列的容器，他们的底层实在就是热茶搜刮树，，此中map/set不支持等值的插入，另外两个就是支持等值插入的。
  

   下面就是一颗二叉搜刮树：
      2.二叉搜刮树的性能分析

最有情况下，二叉搜刮树为完全二叉树（大概是接近完全二叉树），其高度是                                                        log                               ⁡                                      2                                  N                              \log_2N                  log2​N
在最差的情况下，二叉搜刮树会退化为单枝树，其高度为                                   N                              N                  N
所以在综合情况下二叉树的增删查改就是                                   O                         (                         N                         )                              O(N)                  O(N)
那么如许的服从显是无法满足我们的需求的，我们后续还会解说二叉搜刮树的变形AVL树和红黑树，才气实用于我们表现中的需求。
另外必要进行说明的是，二分查找也可以是现在                                                        log                               ⁡                                      2                                  N                              \log_2N                  log2​N的级别的查找服从，到当时二分查找会有两个致命的缺陷：

• 必要储存在你呢挂钩进行你那个随机访问的结构中，且数据必须有序。
  
• 2.插入和删除数据的服从非常底下，由于存储在下标随机访问的数据结构中，插入和
  
• 删除数据的时候一样平常必要挪动数据。
  这里也就表现了二叉平衡树的价值。
  

3.二叉搜刮的插入

插入的详细过程如下：

• 数为空的时候，则直接新增节点，赋值给root指针
  
• 树不为空的时候，按照二叉搜刮树的性质，插入这个值的结果就是直接问题的表现！！！
  
• 如果支持插入相等的值，插入值更当前的节点的值相等那就将节点插到左边也行右边也可以。找到空位置就直接站位，插入新的节点。注意要保持逻辑的连贯性，一致性，插入相等的值不要一会往右一会往左
  

4.二叉搜刮树的查找

• 从跟开始查找x, x比节点的值大，则往右边找，反之往左边
  
• 最多查找树的高度次，走到空还没有找到，则就表现这棵树中没有要找的这个值。
  
• 如果不支持插入相等的值，找到x返回即可。
  
• 如果支持插入相等的值，意味着多个x存在，一样平常在如许的情况下，我们就被要求查找中序的x如下面的图，查找3我们就直接1的右孩子返回那个3
  
  
  
  

5. 二叉搜刮树的删除

首先查找元素是否存在二叉搜刮树中，如果不存在则返回false.
如果查找的元素存在则分为一下四种情况进行分别处理：（假设删除的节点为N）

• 要删除的节点N的左右孩子全为空。
  
• 要删除的节点的N左节点为空，右不为空
  
• 要删除的节点N右孩子为为空，左孩子不为空
  
• 要删除的节点的N的左右孩子均不为空
  

---

对应以上四种情况的办理方案：

• 把N节点的父亲对应的孩子指针指向空，直接删除N节点（情况1可以当成2大概是3处理，结果是一样的）
  
• 把N节点的父亲节点对应的孩子指针指向N的有孩子，直接删除N节点。
  
• 把N节点的父亲对应的孩子指针指向N的左孩子，直接删除N节点。
  
• 无法直接删除N节点，由于N的两个孩子无处安放，只能使用替换法进行删除。找到左子树的的值最大的节点R(最右节点)或则是N右子树的值最小的节点R(最左节点)代替这个N的节点，由于这两个节点中的任意一个，放到N的位置，都是，妈祖二叉搜刮树的规则的。代替N的节点的意思就是N和R的两个节点进行互换，然后再删除R节点位置的值，R节点符合情况2大概是情况3都可以直接删除！！！
  

6. 二叉搜刮树的代码实现

首先我们必要搭建叉搜刮树的基本结构
   节点的构建

1. template<class k>
2. // 先来定义二叉搜索树的基本结构，这个就是他们的节点设置！！！
3. struct bstNode
4. {
5.     K _key;
6.     bstNode<k>* _left;
7.     bstNode<k>* _right;
9.     bstNode(const k& key)
10.     :_left(nullptr), _right(nullptr), _key(key)
11.     {}
12. };

复制代码

完成节点的定义时，我们就必要对树型结构的搭建，现在我们就按照树形结构的定义来实现规则。
   6.1 树形结构的搭建

1. template<class k>
2. class bstree  
3. {
4.   typedef bstNode<k> node;
5. public:
7. private:
8.   node<k>* _root;
9. };

复制代码

按照我们之前的习惯我们还是先来创建二叉树的基本结构，从前在学习二叉树的时候我们已经打仗了很多了，所以我们这里就不再进行详细的解说了。
   6.2 二叉搜刮树的插入实现

  根据前面的分析现在我们就按照前面的理论基础进行相应的树形结构建立。
在插入节点的过程中我们必要注意这三种情况：
   

• 插入时_root为空节点，直接新增节点，赋值给root指针
  
• 不为空的时候就按照二叉搜刮树的性质直接按照大右小左的规则直接往下走就好了。
  
• 如果支持插入相等的值，我们就要统一规则，往右插入节点还是往左插入节点。
  

  

• 首先我们就来办理这个当插入节点时，_root为空节点的情况
  

1. bool insert(const k key)
2. {
3.   // zdl:: 此时_root == nullptr
4.     if (!_root)
5.     {
6.         auto x = node(key);
7.         _root->_left = new node(key);
8.         return true;
9.     }
10.     else
11.     {
12.         
13.     }
14. }

复制代码

否则我们就直接按照规则往下插入节点

1. bool insert(const k& key)
2.         {
3.             if (!_root)
4.             {
5.                 _root = new node(key);
6.                 return true;
7.             }
8.             else
9.             {
10.                 node* cur = _root, *parent = nullptr;
11.                 while (cur)
12.                 {
13.                     if (cur->_key > key)
14.                     {
15.                         parent = cur;
16.                         cur = cur->_left;
17.                     }
18.                     else if (cur->_key < key)
19.                     {
20.                         parent = cur;
21.                         cur = cur->_right;
22.                     }
23.                     else return false;
24.                 }
25.                 cur = new node(key);
26.                 if (key > parent->_key)
27.                 {
28.                     parent->_right = cur;
29.                 }
30.                 else
31.                 {
32.                     parent->_left = cur;
33.                 }
34.             }
36.             return true;
37.         }

复制代码

二叉树的插入节点代码非常的简单，我们按照节点的插入规则，直接就完成了现在的操作。
按照二叉树的插入规则，在进行二叉搜刮树的中序遍历时，我们得到的将会是一个有序的数组。

1. void _InOrder(node* root)
2. {
3.     if (root)
4.     {
5.         _InOrder(root->_left);
6.         cout << root->_key << " ";
7.         _InOrder(root->_right);
8.     }
9. }

复制代码

现在我们就来验证一下我们实现的代码有没有问题：

从上面的代码来看，我们的插入操作没有问题。

2. #include"BST.h"
3. using namespace zdl;
4. int main()
5. {
6.     int a[] = {2,43,4,5,7,2,4,5,2,9,0};
7.     zdl::bstree<int> bst;
8.     for (auto& x : a) bst.insert(x);
9.     bst.InOrder();
10.     return 0;
11. }

复制代码

  6.3 二叉搜刮树的特定值的查找

  查找的逻辑就看看就很简单，我们就是按照规则向下查找特定的值，找到就返回真，否则返回假。

1. bool find(const k& key)
2. {
3.     node* cur = _root;
4.     while (cur)
5.     {
6.         if (cur->_key > key)
7.         {
8.             cur = cur->_left;
9.         }
10.         else if (cur->_key < key)
11.         {
12.             cur = cur->_right;
13.         }
14.         else return true;
15.     }
16.     return false;
17. }

复制代码

  6.4 二叉搜刮树的删除

  

• 想要删除相应值的节点我们就必须要找到这个指定的节点并且在还要知道他的父节点。
  

1. bool Erase(const K &key)
2. {
3.     Node *parent = nullptr;
4.     Node *cur = _root;
5.     while (cur)
6.     {
7.         if (cur->_key < key)
8.         {
9.             parent = cur;
10.             cur = cur->_right;
11.         }
12.         else if (cur->_key > key)
13.         {
14.             parent = cur;
15.             cur = cur->_left;
16.         }
17.         else
18.         {
19.             // 0-1个孩⼦的情况
20.             // 删除情况1 2 3均可以直接删除，改变⽗亲对应孩⼦指针指向即可
21.             if (cur->_left == nullptr)
22.             {
23.                 if (parent == nullptr)
24.                 {
25.                     _root = cur->_right;
26.                 }
27.                 else
28.                 {
29.                     if (parent->_left == cur)
30.                         parent->_left = cur->_right;
31.                     else
32.                         parent->_right = cur->_right;
33.                 }
34.                 delete cur;
35.                 return true;
36.             }
37.             else if (cur->_right == nullptr)
38.             {
39.                 if (parent == nullptr)
40.                 {
41.                     _root = cur->_left;
42.                 }
43.                 else
44.                 {
45.                     if (parent->_left == cur)
46.                         parent->_left = cur->_left;
47.                     else
48.                         parent->_right = cur->_left;
49.                 }
50.                 delete cur;
51.                 return true;
52.             }
53.             else
54.             {
55.                 // 2个孩⼦的情况
56.                 // 删除情况4，替换法删除
57.                 // 假设这⾥我们取右⼦树的最⼩结点作为替代结点去删除
58.                 // 这⾥尤其要注意右⼦树的根就是最⼩情况的情况的处理，对应课件图中删
59.                 除8的情况
60.                 // ⼀定要把cur给rightMinP，否会报错。
61.                 Node *rightMinP = cur;
62.                 Node *rightMin = cur->_right;
63.                 while (rightMin->_left)
64.                 {
65.                     rightMinP = rightMin;
66.                     rightMin = rightMin->_left;
67.                 }
68.                 cur->_key = rightMin->_key;
69.                 if (rightMinP->_left == rightMin)
70.                     rightMinP->_left = rightMin->_right;
71.                 else
72.                     rightMinP->_right = rightMin->_right;
73.                 delete rightMin;
74.                 return true;
75.             }
76.         }
77.     }
78.     return false;
79. }
80. void InOrder()
81. {
82.     _InOrder(_root);
83.     cout << endl;
84. }

复制代码

根据上面的定义，我们很轻松就可以直接得到，删除的逻辑，在进行删除时，我们必要考虑到的无非就是这几种情况，考虑到孩子的安放，并且考虑如果删除时，删除的恰好是根节点又该怎么办，只必要将上面的问题搞清楚，这个问题就算是办理了！！！
7. key/vaule 的场景应用

每⼀个关键码key，都有与之对应的值value，value可以任意范例对象。树的结构中(结点)除了必要存储key还要存储对应的value，增/删/查还是以key为关键字⾛⼆叉搜刮树的规则进⾏⽐较，可以快速查找到key对应的value。key/value的搜刮场景实现的⼆叉树搜刮树⽀持修改，但是不⽀持修改key，修改key粉碎搜刮树性质了，可以修改value。场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜刮时输⼊英⽂，则同时查找到了英⽂对应的中⽂。场景2：阛阓⽆⼈值守⻋库，⼊⼝进场时扫描⻋牌，记录⻋牌和⼊场时间，出⼝离场时，扫描⻋牌，查找⼊场时间，⽤当前时间-⼊场时间计算出停⻋时⻓，计算出停⻋费⽤，缴费后抬杆，⻋辆离场。场景3：统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。
所以基于上面的代码，我们就是已经这个二叉搜刮树的基本代码都已经实现，现在我们就是基于pair范例将这个代码进行进一步的加工。

1. template<class K, class V>
2. struct BSTNode
3. {
4. // pair<K, V> _kv;
5. K _key;
6. V _value;
7. BSTNode<K, V>* _left;
8. BSTNode<K, V>* _right;
9. BSTNode(const K& key, const V& value)
10. :_key(key)
11. , _value(value)
12. , _left(nullptr)
13. , _right(nullptr)
14. {}
15. };
16. template<class K, class V>
17. class BSTree
18. {
19. typedef BSTNode<K, V> Node;
20. public:
21. BSTree() = default;
22. BSTree(const BSTree<K, V>& t)
23. {
24. _root = Copy(t._root);
25. }
26. BSTree<K, V>& operator=(BSTree<K, V> t)
27. {
28. swap(_root, t._root);
29. return *this;
30. }
31. ~BSTree()
32. {
33. Destroy(_root);
34. _root = nullptr;
35. }
36. bool Insert(const K& key, const V& value)
37. {
38. if (_root == nullptr)
39. {
40. _root = new Node(key, value);
41. return true;
42. }
43. Node* parent = nullptr;
44. Node* cur = _root;
45. while (cur)
46. {
47. if (cur->_key < key)
48. {
49. parent = cur;
50. cur = cur->_right;
51. }
52. else if (cur->_key > key)
53. {
54. parent = cur;
55. cur = cur->_left;
56. }
57. else
58. {
59. return false;
60. }
61. }
62. cur = new Node(key, value);
63. if (parent->_key < key)
64. {
65. parent->_right = cur;
66. }
67. else
68. {
69. parent->_left = cur;
70. }
71. return true;
72. }
73. Node* Find(const K& key)
74. {
75. Node* cur = _root;
76. while (cur)
77. {
78. if (cur->_key < key)
79. {
80. cur = cur->_right;
81. }
82. else if (cur->_key > key)
83. {
84. cur = cur->_left;
85. }
86. else
87. {
88. return cur;
89. }
90. }
91. return nullptr;
92. }
93.   bool Erase(const K& key)
94. {
95. Node* parent = nullptr;
96. Node* cur = _root;
97. while (cur)
98. {
99. if (cur->_key < key)
100. {
101. parent = cur;
102. cur = cur->_right;
103. }
104. else if (cur->_key > key)
105. {
106. parent = cur;
107. cur = cur->_left;
108. }
109. else
110. {
111. if (cur->_left == nullptr)
112. {
113. if (parent == nullptr)
114. {
115. _root = cur->_right;
116. }
117. else
118. {
119. if (parent->_left == cur)
120. parent->_left = cur->_right;
121. else
122. parent->_right = cur->_right;
123. }
124. delete cur;
125. return true;
126. }
127. else if (cur->_right == nullptr)
128. {
129. if (parent == nullptr)
130. {
131. _root = cur->_left;
132. }
133. else
134. {
135. if (parent->_left == cur)
136. parent->_left = cur->_left;
137. else
138. parent->_right = cur->_left;
139. }
140. delete cur;
141. return true;
142. }
143. else
144. {
145. Node* rightMinP = cur;
146. Node* rightMin = cur->_right;
147. while (rightMin->_left)
148. {
149. rightMinP = rightMin;
150. rightMin = rightMin->_left;
151. }
152. cur->_key = rightMin->_key;
153. if (rightMinP->_left == rightMin)
154. rightMinP->_left = rightMin->_right;
155. else
156. rightMinP->_right = rightMin->_right;
157. delete rightMin;
158. return true;
159. }
160. }
161. }
162. return false;
163. }
164. void InOrder()
165. {
166. _InOrder(_root);
167. cout << endl;
168. }
169. private:
170.     void _InOrder(Node* root)
171.     {
172.         if (root == nullptr)
173.         {
174.             return;
175.         }
176.         _InOrder(root->_left);
177.         cout << root->_key << ":" << root->_value << endl;
178.         _InOrder(root->_right);
179.         }
180.         void Destroy(Node* root)
181.         {
182.             if (root == nullptr)
183.             return;
184.             Destroy(root->_left);
185.             Destroy(root->_right);
186.             delete root;
187.         }
188.         Node* Copy(Node* root)
189.         {
190.             if (root == nullptr)
191.             return nullptr;
192.             Node* newRoot = new Node(root->_key, root->_value);
193.             newRoot->_left = Copy(root->_left);
194.             newRoot->_right = Copy(root->_right);
195.             return newRoot;
196.         }
197.     private:
198.     Node* _root = nullptr;
199. };
200. int main()
201. {
202.     BSTree<string, string> dict;
203.     //BSTree<string, string> copy = dict;
204.     dict.Insert("left", "左边");
205.     dict.Insert("right", "右边");
206.     dict.Insert("insert", "插⼊");
207.     dict.Insert("string", "字符串");
208.     string str;
209.     while (cin>>str)
210.     {
211.         auto ret = dict.Find(str);
212.         if (ret)
213.         {
214.             cout << "->" << ret->_value << endl;
215.         }
216.         else
217.         {
218.             cout << "⽆此单词，请重新输⼊" << endl;
219.         }
220.     }
221.     return 0;
222. }
223. // 测试二
224. int main()
225. {
226.     string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠", "苹
227.     果", "⾹蕉", "苹果", "⾹蕉" };
228.     BSTree<string, int> countTree;
229.     for (const auto& str : arr)
230.     {
231.         // 先查找⽔果在不在搜索树中
232.         // 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>
233.         // 2、在，则查找到的结点中⽔果对应的次数++
234.         //BSTreeNode<string, int>* ret = countTree.Find(str);
235.         auto ret = countTree.Find(str);
236.         if (ret == NULL)
237.         {
238.             countTree.Insert(str, 1);
239.         }
240.         else
241.         {
242.             ret->_value++;
243.         }
244.     }
245.     countTree.InOrder();
246.     return 0;
247. }

复制代码

好，今天关于二叉搜刮树的学习就到这里，我们下期再见，拜拜！！！