五、K模型和KV模型搜索树
1.K模型搜索树
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。K模型不存在重复值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
（1）以单词集合中的每个单词作为key，构建一棵二叉搜索树
（2）在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
1. #pragma once 2. #include<iostream> 3. using namespace std; 4. 5. namespace K 6. { 7. //树的节点可以支持多种类型 8. template<class K> 9. //树节点结构 10. struct BSTreeNode 11. { 12. BSTreeNode<K>* _left;//左指针 13. BSTreeNode<K>* _right;//右指针 14. K _key;//值 15. 16. //构造函数 17. BSTreeNode(const K& key) 18. :_left(nullptr) 19. , _right(nullptr) 20. , _key(key) 21. {} 22. }; 23. 24. template<class K> 25. class BStree//树结构 26. { 27. typedef BSTreeNode<K> Node; 28. private: 29. //查找 30. Node* _FindR(Node* root, const K& key) 31. { 32. if (root == nullptr)//没找到 33. { 34. return nullptr; 35. } 36. 37. if (key < root->_key)//到左子树去找 38. { 39. FindR(root->_left, key); 40. } 41. else if (key > root->_key)//到右子树去找 42. { 43. FindR(root->_right, key); 44. } 45. else//找到了 46. { 47. return root; 48. } 49. } 50. 51. //插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲 52. bool _InsertR(Node*& root, const K& key) 53. { 54. if (root == nullptr)//找到位置了 55. { 56. root = new Node(key); 57. return true; 58. } 59. if (key < root->_key)//到左子树去找位置 60. { 61. _InsertR(root->_left, key); 62. } 63. else if (key > root->_key)//到右子树去找位置 64. { 65. _InsertR(root->_right, key); 66. } 67. else//已存在，无需插入 68. { 69. return false; 70. } 71. } 72. 73. bool _EraseR(Node*& root, const K& key) 74. { 75. if (root == nullptr)//没找到 76. { 77. return false; 78. } 79. if (key < root->_key)//到左子树去找 80. { 81. _EraseR(root->_left, key); 82. } 83. else if (key > root->_key)//到右子树去找 84. { 85. _EraseR(root->_right, key); 86. } 87. else 88. { 89. //找到了，root就是要删除的节点 90. if (root->_left == nullptr)//root左为空 91. { 92. Node* del = root; 93. root = root->_right; 94. delete del; 95. } 96. else if (root->_right == nullptr)//root右为空 97. { 98. Node* del = root; 99. root = root->_left; 100. delete del; 101. } 102. else//root左右都不为空 103. { 104. //找右子树最左节点 105. Node* minRight = root->_right; 106. while (minRight->_left) 107. { 108. minRight = minRight->_left; 109. } 110. 111. //保存右子树最左节点的值 112. K min = minRight->_key; 113. 114. //使用递归方法删除右子树最左节点 115. _Erase(root->_right, min); 116. } 117. return true; 118. } 119. } 120. 121. Node* _copy(Node* root) 122. { 123. if (root == nullptr)//如果根为空，直接返回 124. { 125. return; 126. } 127. 128. Node* copyNode = new Node(root->_key);//创建根节点 129. copyNode->_left = _copy(root->_left);//递归拷贝左子树节点 130. copyNode->_right = _copy(root->_right);//递归拷贝右子树节点 131. 132. return copyNode;//返回根 133. } 134. 135. _Destroy(root) 136. { 137. if (root == nullptr) 138. { 139. return; 140. } 141. _Destroy(root->_left); 142. _Destroy(root->_right); 143. delete root; 144. } 145. public: 146. //构造函数需要将根初始化为空就行了 147. BSTree() 148. :_root(nullptr) 149. {} 150. 151. //拷贝构造 152. BSTree(const BSTree<K>& t) 153. { 154. _root = t.copy(t._root); 155. } 156. 157. //赋值运算符重载(现代写法) 158. BSTree& operator=(const BSTree<K>& t) 159. { 160. swap(_root, t._root); 161. return *this; 162. } 163. 164. //析构 165. ~BSTree() 166. { 167. _Destroy(_root); 168. _root = nullptr; 169. } 170. 171. //中序遍历 172. void _Inorder(Node* root) 173. { 174. if (root == nullptr) 175. { 176. return; 177. } 178. _Inorder(root->_left);//递归调用自己 179. cout << root->_key << " "; 180. _Inorder(root->_right);//递归调用自己 181. } 182. 183. //先调不传参数的InOrder 184. void InOrder() 185. { 186. //把_root传给子函数，让子函数去使用_root 187. _InOrder(_root); 188. cout << endl; 189. } 190. public: 191. //递归查找 192. Node* FindR(const K& key) 193. { 194. return _FindR(_root, key); 195. } 196. 197. //递归插入 198. bool InsertR(const K& key) 199. { 200. return _InsertR(_root, key); 201. } 202. 203. //递归删除 204. bool EraseR(const K& key) 205. { 206. return _EraseR(_root, key); 207. } 208. private: 209. Node* _root; 210. }; 211. }
2.KV模型搜索树
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：
（1）<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key。
（2）查询英文单词时，只需给出英文单词，就可快速找到与其对应的key。
KV模型可以插入重复值，在K模型的基础上，节点增加了_value成员，用来_key去查找_value，_value的类型不确定，再增加一个模板参数即可：
1. namespace KV 2. { 3. //树的节点可以支持多种类型 4. template<class K, class V> 5. //树节点结构 6. struct BSTreeNode 7. { 8. BSTreeNode<K,V>* _left;//左指针 9. BSTreeNode<K,V>* _right;//右指针 10. K _key; 11. V _value;//增加了_value成员 12. 13. //构造函数 14. BSTreeNode(const K& key) 15. :_left(nullptr) 16. , _right(nullptr) 17. , _key(key) 18. ,_value(value)//初始化_value成员 19. {} 20. }; 21. 22. template<class K, class V>//模板类型从K变成了KV 23. class BStree//树结构 24. { 25. typedef BSTreeNode<K,V> Node;//模板类型从K变成了KV 26. private: 27. //查找 28. Node* _FindR(Node* root, const K& key) 29. { 30. if (root == nullptr)//没找到 31. { 32. return nullptr; 33. } 34. 35. if (key < root->_key)//到左子树去找 36. { 37. FindR(root->_left, key); 38. } 39. else if (key > root->_key)//到右子树去找 40. { 41. FindR(root->_right, key); 42. } 43. else//找到了 44. { 45. return root; 46. } 47. } 48. 49. //插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲 50. bool _InsertR(Node*& root, const K& key, const V& value)//增加了_value成员 51. { 52. if (root == nullptr)//找到位置了 53. { 54. root = new Node(key, value); 55. return true; 56. } 57. if (key < root->_key)//到左子树去找位置 58. { 59. _InsertR(root->_left, key, value); 60. } 61. else if (key > root->_key)//到右子树去找位置 62. { 63. _InsertR(root->_right, key, value); 64. } 65. else//已存在，无需插入 66. { 67. return false; 68. } 69. } 70. 71. bool _EraseR(Node*& root, const K& key,const V& value)//增加了_value成员 72. { 73. if (root == nullptr)//没找到 74. { 75. return false; 76. } 77. if (key < root->_key)//到左子树去找 78. { 79. _EraseR(root->_left, key, value); 80. } 81. else if (key > root->_key)//到右子树去找 82. { 83. _EraseR(root->_right, key, value); 84. } 85. else 86. { 87. //找到了，root就是要删除的节点 88. if (root->_left == nullptr)//root左为空 89. { 90. Node* del = root; 91. root = root->_right; 92. delete del; 93. } 94. else if (root->_right == nullptr)//root右为空 95. { 96. Node* del = root; 97. root = root->_left; 98. delete del; 99. } 100. else//root左右都不为空 101. { 102. //找右子树最左节点 103. Node* minRight = root->_right; 104. while (minRight->_left) 105. { 106. minRight = minRight->_left; 107. } 108. 109. //保存右子树最左节点的值 110. K kMin = minRight->_key; 111. V vMin = minRight->value;//增加了_value成员 112. 113. //使用递归方法删除右子树最左节点 114. _Erase(root->_right, kMin); 115. root->_key = kMin; 116. root->_value = vMin;//增加了_value成员 117. } 118. return true; 119. } 120. } 121. 122. Node* _copy(Node* root) 123. { 124. if (root == nullptr)//如果根为空，直接返回 125. { 126. return nullptr; 127. } 128. 129. Node* copyNode = new Node(root->_key,root->_value);//创建根节点，增加了_value成员 130. copyNode->_left = _copy(root->_left);//递归拷贝左子树节点 131. copyNode->_right = _copy(root->_right);//递归拷贝右子树节点 132. 133. return copyNode;//返回根 134. } 135. 136. _Destroy(root) 137. { 138. if (root == nullptr) 139. { 140. return; 141. } 142. _Destroy(root->_left); 143. _Destroy(root->_right); 144. delete root; 145. } 146. public: 147. //构造函数需要将根初始化为空就行了 148. BSTree() 149. :_root(nullptr) 150. {} 151. 152. //拷贝构造 153. BSTree(const BSTree<K>& t) 154. { 155. _root = t.copy(t._root); 156. } 157. 158. //赋值运算符重载(现代写法) 159. BSTree& operator=(const BSTree<K>& t) 160. { 161. swap(_root, t._root); 162. return *this; 163. } 164. 165. //析构 166. ~BSTree() 167. { 168. _Destroy(_root); 169. _root = nullptr; 170. } 171. 172. //中序遍历 173. void _Inorder(Node* root) 174. { 175. if (root == nullptr) 176. { 177. return; 178. } 179. _Inorder(root->_left);//递归调用自己 180. cout << root->_key << ":" << root->_value<<endl;//增加了_value成员 181. _Inorder(root->_right);//递归调用自己 182. } 183. 184. //先调不传参数的InOrder 185. void InOrder() 186. { 187. //把_root传给子函数，让子函数去使用_root 188. _InOrder(_root); 189. cout << endl; 190. } 191. public: 192. //递归查找 193. Node* FindR(const K& key) 194. { 195. return _FindR(_root, key); 196. } 197. 198. //递归插入 199. bool InsertR(const K& key,const V& value)//增加了_value成员 200. { 201. return _InsertR(_root, key, value); 202. } 203. 204. //递归删除 205. bool EraseR(const K& key) 206. { 207. return _EraseR(_root, key); 208. } 209. private: 210. Node* _root; 211. }; 212. }
六、二叉搜索树性能分析
（1）查找效率代表了二叉搜索树中各个操作的性能，插入和删除操作都必须先查找。
（2）对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
（3）但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
例如按照序列{1,4,5,6,8,9,13,15,20,27}，构建二叉树：
元素相同，但是次序不同的序列{27,20,15,13,9,8,6,5,4,1}，构建二叉树:
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：
