• C++ 二叉搜索树BinarySearchTree

    目录

    一.概念

    二.分部模拟实现（K模型）

    1.二叉树结点

    2.二叉搜索树构建

    3.查找（非递归）

    4.插入（非递归）

    5.删除（非递归）

    6.查找（递归）

     7.插入（递归）

    8.删除（递归）

    三.模拟实现总代码（K模型）

    四.模拟实现（KV模型）

    五.二叉搜索树的应用

    1.K模型

    2.KV模型

    六.二叉搜索树的性能

    前言：二叉搜索树是为学习map和set做的铺垫，了解了二叉搜索树的特性，有助于更好的理解map和set。

    一.概念

            二叉搜索树有称二叉排序树，它可以是一颗空树，或者是具有以下行者的二叉树：

    ① 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值

    ② 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值

    ③ 它的左右子树也分别为二叉搜索树

    二.分部模拟实现（K模型）

    1.二叉树结点

            _key为该二叉树值，_left为左结点，_right为右结点。

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6.  
    7. 	K _key;
    8.  
    9. 	BSTreeNode(const K& key)
    10. 		: _left(nullptr)
    11. 		, _right(nullptr)
    12. 		, _key(key)
    13. 	{}
    14. };

    2.二叉搜索树构建

            实现二叉搜索树的构造、拷贝构造、赋值重载、析构函数。

            拷贝构造是一定要实现的，通过子函数CopyTree通过前序遍历进行依次构造结点，而构造函数用编译器默认生成的就够了，但是因为实现了拷贝构造，编译器就不会生成默认的构造，因此使用C++11的关键字default来强制编译器生成构造。

            赋值重载是现代写法，析构函数也是通过子函数DestoryTree，通过递归依次释放结点。

    1. template<class K>
    2. class BSTree
    3. {
    4. 	typedef BSTreeNode Node;
    5. private:
    6. 	void DestroyTree(Node* root)
    7. 	{
    8. 		if (root == nullptr)
    9. 		{
    10. 			return;
    11. 		}
    12.  
    13. 		DestroyTree(root->_left);
    14. 		DestroyTree(root->_right);
    15. 		delete root;
    16. 	}
    17.  
    18. 	Node* CopyTree(Node* root)
    19. 	{
    20. 		if (root == nullptr)
    21. 		{
    22. 			return nullptr;
    23. 		}
    24.  
    25. 		Node* copyNode = new Node(root->_key);
    26. 		CopyTree(root->_left);
    27. 		CopyTree(root->_right);
    28.  
    29. 		return copyNode;
    30. 	}
    31. public:
    32. 	// C++11，强制让编译器自己生成构造
    33. 	BSTree() = default;
    34.  
    35. 	BSTree(const BSTree& t)
    36. 	{
    37. 		_root = CopyTree(t._root);
    38. 	}
    39.  
    40. 	BSTree& operator=(BSTree t)
    41. 	{
    42. 		swap(_root, t._root);
    43. 		return *this;
    44. 	}
    45.  
    46. 	~BSTree()
    47. 	{
    48. 		DestroyTree(_root);
    49. 		_root = nullptr;
    50. 	}
    51. private:
    52. 	Node* _root = nullptr;
    53. };

    3.查找（非递归）

            遍历寻找，如果要查找的key值大于该结点的key值，就往该结点的右子树走，如果要查找的key值小于该结点的key值，就往该结点的左子树走。

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

    4.插入（非递归）

            找到位置就插入进去。，如果是空树，直接插入作为根结点。

            需要定义一个parent变量，这样在找到插入的位置后，可以让该插入结点的父节点parent链接上该新插入的结点。

            前面与查找类似，如果要查找的key值大于该结点的key值，就往该结点的右子树走，如果要查找的key值小于该结点的key值，就往该结点的左子树走，如果相等了，就不能插入了，直接返回false。

            找到要插入的位置之后，new出要插入的新结点，然后判断这个结点的值是大于parent还是小于parent，如果大于就放在右边，如果小于就放在左边。

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

    5.删除（非递归）

            删除需要考虑的比较多。

            首先也是需要定义一个parent变量，这样删除掉结点后，可以让其parent连接到删除结点的孩子结点。

            接着也是与查找类似，在找到之后，就要分情况讨论。

            第一种情况是要删除的结点的左孩子为空：这种情况首先要注意要删除的结点是根结点的情况，因为是根结点，所有parent是空，因此要单独写，让新的根结点变为原根结点的右结点。另外就是正常情况，要判断删除的这个结点的值是parent的左孩子结点还是右孩子结点，如果是左孩子结点，就让其parent的左孩子结点链接上该结点的右孩子结点，如果是右孩子结点，就让parent的右孩子结点链接上该结点的右孩子结点。

            第二种情况是要删除的结点的右孩子为空：这种情况与第一种情况类似，也是要注意特殊情况，但是这种情况是让新的根结点变为原根结点的左结点。然后再判断删除的这个结点时parent的左孩子结点还是右孩子结点，如果是左孩子结点，就让parent的左孩子结点链接上该结点的左孩子结点，如果是右孩子结点，就让parent的右孩子结点链接上该结点的左孩子结点。

            第三种情况是要删除的结点的左右孩子都不为空：出现这种情况时，不能直接删除掉需要删除的结点，而是需要替代删除，保证二叉搜索树的特性。这种替代有两种方法（第一种是用该结点的左子树的最大结点替代，第二种是用该结点的右子树的最小结点替代），这里我们采用第二种方法。首先需要定义两个变量，一个是用来找到这个去替代的结点minRight，另一个是该替代的结点的父节点minParent，这里要注意定义minParent时，要让其等于cur，如果让其等于nullptr，那么如果该结点的左结点没有结点了就会导致minParent一直为空，出现野指针问题。定义了之后，通过while循环找到该结点右子树的最小结点（即该结点右子树的最左的结点），接下来可以交换要删除结点的值和替代结点的值，也可以直接赋值，因为替代结点即将被删除，是否交换并不重要。接下来再判断替代结点时minParent的左孩子结点还是右孩子结点，如果是左孩子结点，就让minParent的左孩子节点链接上替代结点的右孩子节点，如果是右孩子结点，就让minParent的右孩子结点链接上替代结点的右孩子结点。

    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. 		// 找到要删除的结点了
    18. 		else
    19. 		{
    20. 			// 左孩子为空
    21. 			if (cur->_left == nullptr)
    22. 			{
    23. 				if (cur == _root)
    24. 				{
    25. 					_root = cur->_right;
    26. 				}
    27. 				else
    28. 				{ 
    29. 					if (cur == parent->_left)
    30. 					{
    31. 						parent->_left = cur->_right;
    32. 					}
    33. 					else
    34. 					{
    35. 						parent->_right = cur->_right;
    36. 					}
    37. 				}
    38.  
    39. 				delete cur;
    40. 			}
    41. 			// 右孩子为空
    42. 			else if (cur->_right == nullptr)
    43. 			{
    44. 				if (cur == _root)
    45. 				{
    46. 					_root = cur->_left;
    47. 				}
    48. 				else
    49. 				{
    50. 					if (cur == parent->_left)
    51. 					{
    52. 						parent->_left = cur->_left;
    53. 					}
    54. 					else
    55. 					{
    56. 						parent->_right = cur->_left;
    57. 					}
    58. 				}
    59.  
    60. 				delete cur;
    61. 			}
    62. 			// 两个孩子都不为空
    63. 			else
    64. 			{
    65. 				// 用右子树的最小结点去替代
    66. 				Node* minParent = cur;
    67. 				Node* minRight = cur->_right;
    68. 				while (minRight->_left)
    69. 				{
    70. 					minParent = minRight;
    71. 					minRight = minRight->_left;
    72. 				}
    73.  
    74. 				swap(minRight->_key, cur->_key);
    75.  
    76. 				if (minParent->_left == minRight)
    77. 				{
    78. 					minParent->_left = minRight->_right;
    79. 				}
    80. 				else
    81. 				{
    82. 					minParent->_right = minRight->_right;
    83. 				}
    84.  
    85. 				delete minRight;
    86. 			}
    87.  
    88. 			return true;
    89. 		}
    90. 	}
    91.  
    92. 	return false;
    93. }

    6.查找（递归）

            递归写法就采用子函数的方法，查找、插入、删除都是如此。

             如果要查找的值比此结点大，就递归调用该结点的右子树结点，如果要查找的值比此结点小，就递归调用该结点的左子树结点，如果相等了就返回true，遇到空结点就返回false。

    1.     bool FindR(const K& key)
    2. 	{
    3. 		return _FindR(_root, key);
    4. 	}
    5.  
    6. private:
    7. 	bool _FindR(Node* root, const K& key)
    8. 	{
    9. 		if (root == nullptr)
    10. 		{
    11. 			return false;
    12. 		}
    13.  
    14. 		if (root->_key < key)
    15. 		{
    16. 			return _FindR(root->_right, key);
    17. 		}
    18. 		else if (root->_key > key)
    19. 		{
    20. 			return _FindR(root->_left, key);
    21. 		}
    22. 		else
    23. 		{
    24. 			return true;
    25. 		}
    26. 	}

     7.插入（递归）

            与递归查找法类似，只是插入是遇到空会创建插入结点，返回true，相等时返回false。

    1.     bool InsertR(const K& key)
    2. 	{
    3. 		return _InsertR(_root, key);
    4. 	}
    5.  
    6. private:
    7. 	bool _InsertR(Node* root, const K& key)
    8. 	{
    9. 		if (root == nullptr)
    10. 		{
    11. 			root = new Node(key);
    12. 			return true;
    13. 		}
    14.  
    15. 		if (root->_key < key)
    16. 		{
    17. 			return _InsertR(root->_right, key);
    18. 		}
    19. 		else if (root->_key > key)
    20. 		{
    21. 			return _InsertR(root->_left, key);
    22. 		}
    23. 		else
    24. 		{
    25. 			return false;
    26. 		}
    27. 	}

    8.删除（递归）

            前面就是查找，找到之后，也是要分三种情况讨论。

            这里我们注意形参root的变量类型是Node*&，是指针的引用。

            第一种左为空：因为是指针引用，因此直接让root等于root的右子树结点，因为是引用，所以如果上一个递归调用的是root->_right那么这个root就是上一个root->_right的别名，因此就相当于上一个的root->_right = 当前的root->_right，这样就相当于删除掉了这个root。

            第二种右为空：与第一种类似，root = root->_left，把_right改为_left即可。

            第三种左右都不为空：这个就只需要定义一个替代变量minRight即可，然后通过while找到这个变量，这个一定要交换，不能赋值更改，因为接下来是要使用递归的。要注意这里递归的是root的右子树结点（不能是当前结点，原因是在交换之后，该结点已经不满足二叉搜索树的特性了，用该结点就会出错），其右子树结点及其右子树所有结点都是满足二叉搜索树的特性的，这样递归之后，就满足上面两种情况之一，就可以完成删除了。

    1. 	bool EraseR(const K& key)
    2. 	{
    3. 		return _EraseR(_root, key);
    4. 	}
    5.  
    6. private:
    7. 	bool _EraseR(Node*& root, const K& key)
    8. 	{
    9. 		if (root == nullptr)
    10. 		{
    11. 			return false;
    12. 		}
    13.  
    14. 		if (root->_key < key)
    15. 		{
    16. 			return _EraseR(root->_right, key);
    17. 		}
    18. 		else if (root->_key > key)
    19. 		{
    20. 			return _EraseR(root->_left, key);
    21. 		}
    22. 		else
    23. 		{
    24. 			Node* del = root;
    25. 			// 删除
    26. 			// 左为空
    27. 			if (root->_left == nullptr)
    28. 			{
    29. 				root = root->_right;
    30. 			}
    31. 			// 右为空
    32. 			else if (root->_right == nullptr)
    33. 			{
    34. 				root = root->_left;
    35. 			}
    36. 			// 都不为空
    37. 			else
    38. 			{
    39. 				Node* minRight = root->_right;
    40. 				while (minRight->_left)
    41. 				{
    42. 					minRight = minRight->_left;
    43. 				}
    44.  
    45. 				swap(root->_key, minRight->_key);
    46.  
    47. 				return _EraseR(root->_right, key);
    48. 			}
    49.  
    50. 			delete del;
    51. 			return true;
    52. 		}
    53. 	}

    三.模拟实现总代码（K模型）

    1. namespace key
    2. {
    3. 	template<class K>
    4. 	struct BSTreeNode
    5. 	{
    6. 		BSTreeNode* _left;
    7. 		BSTreeNode* _right;
    8.  
    9. 		K _key;
    10.  
    11. 		BSTreeNode(const K& key)
    12. 			: _left(nullptr)
    13. 			, _right(nullptr)
    14. 			, _key(key)
    15. 		{}
    16. 	};
    17.  
    18. 	template<class K>
    19. 	class BSTree
    20. 	{
    21. 		typedef BSTreeNode Node;
    22. 	private:
    23. 		void DestroyTree(Node* root)
    24. 		{
    25. 			if (root == nullptr)
    26. 			{
    27. 				return;
    28. 			}
    29.  
    30. 			DestroyTree(root->_left);
    31. 			DestroyTree(root->_right);
    32. 			delete root;
    33. 		}
    34.  
    35. 		Node* CopyTree(Node* root)
    36. 		{
    37. 			if (root == nullptr)
    38. 			{
    39. 				return nullptr;
    40. 			}
    41.  
    42. 			Node* copyNode = new Node(root->_key);
    43. 			CopyTree(root->_left);
    44. 			CopyTree(root->_right);
    45.  
    46. 			return copyNode;
    47. 		}
    48. 	public:
    49. 		// C++11，强制让编译器自己生成构造
    50. 		BSTree() = default;
    51.  
    52. 		BSTree(const BSTree& t)
    53. 		{
    54. 			_root = CopyTree(t._root);
    55. 		}
    56.  
    57. 		BSTree& operator=(BSTree t)
    58. 		{
    59. 			swap(_root, t._root);
    60. 			return *this;
    61. 		}
    62.  
    63. 		~BSTree()
    64. 		{
    65. 			DestroyTree(_root);
    66. 			_root = nullptr;
    67. 		}
    68.  
    69. 		bool Insert(const K& key)
    70. 		{
    71. 			if (_root == nullptr)
    72. 			{
    73. 				_root = new Node(key);
    74. 				return true;
    75. 			}
    76.  
    77. 			Node* parent = nullptr;
    78. 			Node* cur = _root;
    79. 			while (cur)
    80. 			{
    81. 				if (cur->_key < key)
    82. 				{
    83. 					parent = cur;
    84. 					cur = cur->_right;
    85. 				}
    86. 				else if (cur->_key > key)
    87. 				{
    88. 					parent = cur;
    89. 					cur = cur->_left;
    90. 				}
    91. 				else
    92. 				{
    93. 					return false;
    94. 				}
    95. 			}
    96.  
    97. 			cur = new Node(key);
    98. 			if (parent->_key < key)
    99. 			{
    100. 				parent->_right = cur;
    101. 			}
    102. 			else
    103. 			{
    104. 				parent->_left = cur;
    105. 			}
    106.  
    107. 			return true;
    108. 		}
    109.  
    110. 		// const Node* Find(const K& key)
    111. 		bool Find(const K& key)
    112. 		{
    113. 			Node* cur = _root;
    114. 			while (cur)
    115. 			{
    116. 				if (cur->_key < key)
    117. 				{
    118. 					cur = cur->_right;
    119. 				}
    120. 				else if (cur->_key > key)
    121. 				{
    122. 					cur = cur->_left;
    123. 				}
    124. 				else
    125. 				{
    126. 					return true;
    127. 				}
    128. 			}
    129.  
    130. 			return false;
    131. 		}
    132.  
    133. 		bool Erase(const K& key)
    134. 		{
    135. 			Node* parent = nullptr;
    136. 			Node* cur = _root;
    137. 			while (cur)
    138. 			{
    139. 				if (cur->_key < key)
    140. 				{
    141. 					parent = cur;
    142. 					cur = cur->_right;
    143. 				}
    144. 				else if (cur->_key > key)
    145. 				{
    146. 					parent = cur;
    147. 					cur = cur->_left;
    148. 				}
    149. 				// 找到要删除的结点了
    150. 				else
    151. 				{
    152. 					// 左孩子为空
    153. 					if (cur->_left == nullptr)
    154. 					{
    155. 						if (cur == _root)
    156. 						{
    157. 							_root = cur->_right;
    158. 						}
    159. 						else
    160. 						{
    161. 							if (cur == parent->_left)
    162. 							{
    163. 								parent->_left = cur->_right;
    164. 							}
    165. 							else
    166. 							{
    167. 								parent->_right = cur->_right;
    168. 							}
    169. 						}
    170.  
    171. 						delete cur;
    172. 					}
    173. 					// 右孩子为空
    174. 					else if (cur->_right == nullptr)
    175. 					{
    176. 						if (cur == _root)
    177. 						{
    178. 							_root = cur->_left;
    179. 						}
    180. 						else
    181. 						{
    182. 							if (cur == parent->_left)
    183. 							{
    184. 								parent->_left = cur->_left;
    185. 							}
    186. 							else
    187. 							{
    188. 								parent->_right = cur->_left;
    189. 							}
    190. 						}
    191.  
    192. 						delete cur;
    193. 					}
    194. 					// 两个孩子都不为空
    195. 					else
    196. 					{
    197. 						// 用右子树的最小结点去替代
    198. 						Node* minParent = cur;
    199. 						Node* minRight = cur->_right;
    200. 						while (minRight->_left)
    201. 						{
    202. 							minParent = minRight;
    203. 							minRight = minRight->_left;
    204. 						}
    205.  
    206. 						swap(minRight->_key, cur->_key);
    207.  
    208. 						if (minParent->_left == minRight)
    209. 						{
    210. 							minParent->_left = minRight->_right;
    211. 						}
    212. 						else
    213. 						{
    214. 							minParent->_right = minRight->_right;
    215. 						}
    216.  
    217. 						delete minRight;
    218. 					}
    219.  
    220. 					return true;
    221. 				}
    222. 			}
    223.  
    224. 			return false;
    225. 		}
    226.  
    227. 		// 递归写法：
    228. 		bool FindR(const K& key)
    229. 		{
    230. 			return _FindR(_root, key);
    231. 		}
    232.  
    233. 		bool InsertR(const K& key)
    234. 		{
    235. 			return _InsertR(_root, key);
    236. 		}
    237.  
    238. 		bool EraseR(const K& key)
    239. 		{
    240. 			return _EraseR(_root, key);
    241. 		}
    242.  
    243. 		void InOrder()
    244. 		{
    245. 			_InOrder(_root);
    246. 		}
    247. 	private:
    248. 		bool _FindR(Node* root, const K& key)
    249. 		{
    250. 			if (root == nullptr)
    251. 			{
    252. 				return false;
    253. 			}
    254.  
    255. 			if (root->_key < key)
    256. 			{
    257. 				return _FindR(root->_right, key);
    258. 			}
    259. 			else if (root->_key > key)
    260. 			{
    261. 				return _FindR(root->_left, key);
    262. 			}
    263. 			else
    264. 			{
    265. 				return true;
    266. 			}
    267. 		}
    268.  
    269. 		bool _InsertR(Node* root, const K& key)
    270. 		{
    271. 			if (root == nullptr)
    272. 			{
    273. 				root = new Node(key);
    274. 				return true;
    275. 			}
    276.  
    277. 			if (root->_key < key)
    278. 			{
    279. 				return _InsertR(root->_right, key);
    280. 			}
    281. 			else if (root->_key > key)
    282. 			{
    283. 				return _InsertR(root->_left, key);
    284. 			}
    285. 			else
    286. 			{
    287. 				return false;
    288. 			}
    289. 		}
    290.  
    291. 		bool _EraseR(Node*& root, const K& key)
    292. 		{
    293. 			if (root == nullptr)
    294. 			{
    295. 				return false;
    296. 			}
    297.  
    298. 			if (root->_key < key)
    299. 			{
    300. 				return _EraseR(root->_right, key);
    301. 			}
    302. 			else if (root->_key > key)
    303. 			{
    304. 				return _EraseR(root->_left, key);
    305. 			}
    306. 			else
    307. 			{
    308. 				Node* del = root;
    309. 				// 删除
    310. 				// 左为空
    311. 				if (root->_left == nullptr)
    312. 				{
    313. 					root = root->_right;
    314. 				}
    315. 				// 右为空
    316. 				else if (root->_right == nullptr)
    317. 				{
    318. 					root = root->_left;
    319. 				}
    320. 				// 都不为空
    321. 				else
    322. 				{
    323. 					Node* minRight = root->_right;
    324. 					while (minRight->_left)
    325. 					{
    326. 						minRight = minRight->_left;
    327. 					}
    328.  
    329. 					swap(root->_key, minRight->_key);
    330.  
    331. 					return _EraseR(root->_right, key);
    332. 				}
    333.  
    334. 				delete del;
    335. 				return true;
    336. 			}
    337. 		}
    338.  
    339. 		Node* _root = nullptr;
    340.  
    341. 		void _InOrder(Node* root)
    342. 		{
    343. 			if (root == nullptr)
    344. 			{
    345. 				return;
    346. 			}
    347.  
    348. 			_InOrder(root->_left);
    349. 			cout << root->_key << " ";
    350. 			_InOrder(root->_right);
    351. 		}
    352. 	};
    353. }

    四.模拟实现（KV模型）

            这个和K模型的很类似，就大致实现一下，这里用修改的是递归版本的。

            只需要增加一下value变量，增加一下模板，注意key加const。

    1. namespace key_value
    2. {
    3. 	template<class K, class V>
    4. 	struct BSTreeNode
    5. 	{
    6. 		BSTreeNode* _left;
    7. 		BSTreeNode* _right;
    8.  
    9. 		const K _key;
    10. 		V _value;
    11.  
    12. 		BSTreeNode(const K& key, const V& value)
    13. 			:_left(nullptr)
    14. 			, _right(nullptr)
    15. 			, _key(key)
    16. 			, _value(value)
    17. 		{}
    18. 	};
    19.  
    20.  
    21. 	template<class K, class V>
    22. 	class BSTree
    23. 	{
    24. 		typedef BSTreeNode Node;
    25. 	public:
    26.  
    27. 		void InOrder()
    28. 		{
    29. 			_InOrder(_root);
    30. 			cout << endl;
    31. 		}
    32. 		Node* FindR(const K& key)
    33. 		{
    34. 			return _FindR(_root, key);
    35. 		}
    36.  
    37. 		bool InsertR(const K& key, const V& value)
    38. 		{
    39. 			return _InsertR(_root, key, value);
    40. 		}
    41.  
    42. 		bool EraseR(const K& key)
    43. 		{
    44. 			return _EraseR(_root, key);
    45. 		}
    46.  
    47. 	private:
    48. 		bool _EraseR(Node*& root, const K& key)
    49. 		{
    50. 			if (root == nullptr)
    51. 				return false;
    52.  
    53. 			if (root->_key < key)
    54. 			{
    55. 				return _EraseR(root->_right, key);
    56. 			}
    57. 			else if (root->_key > key)
    58. 			{
    59. 				return _EraseR(root->_left, key);
    60. 			}
    61. 			else
    62. 			{
    63. 				Node* del = root;
    64. 				// 删除
    65. 				if (root->_left == nullptr)
    66. 				{
    67. 					root = root->_right;
    68. 				}
    69. 				else if (root->_right == nullptr)
    70. 				{
    71. 					root = root->_left;
    72. 				}
    73. 				else
    74. 				{
    75. 					Node* minRight = root->_right;
    76. 					while (minRight->_left)
    77. 					{
    78. 						minRight = minRight->_left;
    79. 					}
    80.  
    81. 					swap(root->_key, minRight->_key);
    82.  
    83. 					return _EraseR(root->_right, key);
    84. 				}
    85.  
    86. 				delete del;
    87. 				return true;
    88. 			}
    89. 		}
    90.  
    91. 		bool _InsertR(Node*& root, const K& key, const V& value)
    92. 		{
    93. 			if (root == nullptr)
    94. 			{
    95. 				root = new Node(key, value);
    96. 				return true;
    97. 			}
    98.  
    99. 			if (root->_key < key)
    100. 				return _InsertR(root->_right, key, value);
    101. 			else if (root->_key > key)
    102. 				return _InsertR(root->_left, key, value);
    103. 			else
    104. 				return false;
    105. 		}
    106.  
    107. 		Node* _FindR(Node* root, const K& key)
    108. 		{
    109. 			if (root == nullptr)
    110. 				return nullptr;
    111.  
    112. 			if (root->_key < key)
    113. 			{
    114. 				return _FindR(root->_right, key);
    115. 			}
    116. 			else if (root->_key > key)
    117. 			{
    118. 				return _FindR(root->_left, key);
    119. 			}
    120. 			else
    121. 			{
    122. 				return root;
    123. 			}
    124. 		}
    125.  
    126. 		void _InOrder(Node* root)
    127. 		{
    128. 			if (root == nullptr)
    129. 				return;
    130.  
    131. 			_InOrder(root->_left);
    132. 			cout << root->_key << ":" << root->_value << endl;
    133. 			_InOrder(root->_right);
    134. 		}
    135. 	private:
    136. 		Node* _root = nullptr;
    137. 	};
    138. }

    五.二叉搜索树的应用

    1.K模型

            K模型只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。

    例子：判断单词是否拼写正确

            用词库中的单词集合中的每个单词作为key，构建二叉搜索树。

    2.KV模型

            每一个关键码key，都有与之对应的值value，即的键值对

    例子：①英汉词典，中英文的对应关系， 通过英文可以快速找到对应的中文。

               ②统计单词的次数，单词与其出现次数构成键值对。

    六.二叉搜索树的性能

    对于相同的元素，如果key插入的次序不同，可能会得到不同结果的二叉搜索树。

            这里要注意二叉搜索树的效率是O(logN)，而不是O(log2N)  。

            最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其比较次数是log2N。

            最差情况下，二叉搜索树退化为单支树（或者类似单支），其比较次数为logN

            因此，我们接下来要学习平衡二叉搜索树（AVL树、红黑树），这个就使二叉搜索树趋近于完全二叉树，尽可能保证搜索效率。

  • 相关阅读:
    【R包开发：入门】 简介+ 包的结构
    对数据进行切片操作slice()函数
    【负荷预测】布谷鸟(CS)算法优化BP神经网络的负荷及天气预测（Matlab代码实现）
    Uber：Java中的不稳定单元测试处理
    从应用访问Pod元数据-DownwardApi的应用
    第二证券：产业资本真金白银传递市场信心
    浅谈AI人体姿态识别技术的先进性及安防视频监控应用场景
    C Primer Plus(6) 中文版 第6章 C控制语句：循环 6.7 逗号运算符
    MockJs
    python-json校验-jsonpath
  • 原文地址：https://blog.csdn.net/qq_60750110/article/details/125968915