• C++ —— 二叉搜索树

    目录

    二叉搜索树概念

    二叉搜索树操作

    1. 二叉搜索树的查找

    2. 二叉搜索树的插入

    3. 二叉搜索树的删除 

    二叉搜索树的应用

    1. K模型

    2. KV模型

    二叉搜索树的性能分析

    二叉搜索树的实现（K&&KV）和测试（KV）

    C语言总结在这常见八大排序在这

    作者和朋友建立的社区：非科班转码社区-CSDN社区云💖💛💙

    期待hxd的支持哈🎉 🎉 🎉

    最后是打鸡血环节：你只管努力，剩下的交给天意🚀 🚀 🚀

    二叉搜索树概念

    二叉搜索树又称二叉排序树，它或者是一棵空树 ，或者是具有以下性质的二叉树 :
    1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
    2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
    3. 它的左右子树也分别为二叉搜索树

    二叉搜索树操作

     

    int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};  

    1. 二叉搜索树的查找

    a 、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
    b 、最多查找高度次，走到到空，还没找到，这个值不存在。

    2. 二叉搜索树的插入

    插入的具体过程如下：
    a. 树为空，则直接新增节点，赋值给 root 指针
    b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

    3. 二叉搜索树的删除 

    首先查找元素是否在二叉搜索树中，如果不存在，则返回 , 否则要删除的结点可能分下面四种情 况：
    a. 要删除的结点无孩子结点
    b. 要删除的结点只有左孩子结点
    c. 要删除的结点只有右孩子结点
    d. 要删除的结点有左、右孩子结点
    实际上a可以属于b或者c

    二叉搜索树的应用

    1. K模型

    K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到 的值 。
    比如： 给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下：
    以词库中所有单词集合中的每个单词作为 key ，构建一棵二叉搜索树。
    在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

    2. KV模型

    每一个关键码 key ，都有与之对应的值 Value ，即 的键值对 。该种方式在现实生活中非常常见：
    比如 英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英
    文单词与其对应的中文 就构成一种键值对；
    再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出
    现次数就是 就构成一种键值对。
    下面对于KV模型有对应的测试用例

    二叉搜索树的性能分析

    插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
    对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
    但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
    最优情况下，二叉搜索树为完全二叉树 ( 或者接近完全二叉树 ) ，其平均比较次数为： log2 N
    最差情况下，二叉搜索树退化为单支树 ( 或者类似单支 ) ，其平均比较次数为：N
    问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL 树和红黑树就可以上场了。
    二叉搜索树也就是为了后面的AVL树和红黑树做铺垫！

    二叉搜索树的实现（K&&KV）和测试（KV）

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include
    4. #include
    5.  
    6. using namespace std;
    7.  
    8.  
    9. /// //
    10. 				//		K模型
    11.  
    12. //template
    13. //struct BSTreeNode {
    14. //	BSTreeNode(const K& key)
    15. //		:_key(key)
    16. //		, _left(nullptr)
    17. //		, _right(nullptr)
    18. //	{};
    19. //
    20. //	BSTreeNode* _left;
    21. //	BSTreeNode* _right;
    22. //	K _key;
    23. //};
    24. //
    25. //template
    26. //class BSTree
    27. //{
    28. //	typedef BSTreeNode Node;
    29. //public:
    30. //	bool Insert(const K& key)
    31. //	{
    32. //		if (_root == nullptr)
    33. //		{
    34. //			_root = new Node(key);
    35. //			return true;
    36. //		}
    37. //
    38. //		Node* parent = nullptr;
    39. //		Node* cur = _root;
    40. //		while (cur)
    41. //		{
    42. //			if (key > cur->_key)
    43. //			{
    44. //				parent = cur;
    45. //				cur = cur->_right;
    46. //			}
    47. //			else if (key < cur->_key)
    48. //			{
    49. //				parent = cur;
    50. //				cur = cur->_left;
    51. //			}
    52. //			else
    53. //			{
    54. //				return false;
    55. //			}
    56. //		}
    57. //		cur = new Node(key);
    58. //		//这里别用nullptr去判断,问就是写的时候好像不对
    59. //		if (parent->_key > key)
    60. //		{
    61. //			parent->_left = cur;
    62. //		}
    63. //		else
    64. //		{
    65. //			parent->_right = cur;
    66. //		}
    67. //		return true;
    68. //	}
    69. //
    70. //	Node* Find(const K& key)
    71. //	{
    72. //		Node* cur = _root;
    73. //		while (cur)
    74. //		{
    75. //			if (cur->_key > key)
    76. //			{
    77. //				cur = cur->_left;
    78. //			}
    79. //			else if (cur->_key < key)
    80. //			{
    81. //				cur = cur->_right;
    82. //			}
    83. //			else
    84. //			{
    85. //				return cur;
    86. //			}
    87. //		}
    88. //		return false;
    89. //	}
    90. //
    91. //	//删除有三种情况
    92. //	//要删除的孩子有左节点（1）
    93. //	//要删除的孩子有右节点（2）
    94. //	//要删除的孩子有左，右节点（3）替换法删除
    95. //	//要删除的孩子无节点（属于1或2）
    96. //	bool Erase(const K& key)
    97. //	{
    98. //		Node* cur = _root;
    99. //		Node* parent = nullptr;
    100. //		while (cur)
    101. //		{
    102. //			if (key < cur->_key)
    103. //			{
    104. //				parent = cur;
    105. //				cur = cur->_left;
    106. //			}
    107. //			else if (key > cur->_right)
    108. //			{
    109. //				parent = cur;
    110. //				cur = cur->_right;
    111. //			}
    112. //			else//找到了要删除的节点
    113. //			{
    114. //				// 一个孩子--左为空 or 右为空
    115. //				// 两个孩子 -- 替换法
    116. //				if (cur->_left == nullptr)
    117. //				{
    118. //					if (cur == _root)
    119. //					{
    120. //						_root = cur->_right;
    121. //					}
    122. //					else
    123. //					{
    124. //						if (cur == parent->_left)
    125. //						{
    126. //							parent->_left = cur->_right;
    127. //						}
    128. //						else
    129. //						{
    130. //							parent->_right = cur->_right;
    131. //						}
    132. //					}
    133. //					delete cur;
    134. //				}
    135. //				else if (cur->_right == nullptr)
    136. //				{
    137. //					if (cur == _root)
    138. //					{
    139. //						_root = cur->_left;
    140. //					}
    141. //					else
    142. //					{
    143. //						if (cur == parent->_left)
    144. //						{
    145. //							parent->_left = cur->_left;
    146. //						}
    147. //						else
    148. //						{
    149. //							parent->_right = cur->_left;
    150. //						}
    151. //					}
    152. //					delete cur;
    153. //				}
    154. //				else // 两个孩子都不为空，替换法删除
    155. //					//找到左子树的最大节点或者右子树的最小节点替换
    156. //				{
    157. //					// 右子树的最小节点替代  且右子树最小节点，一定是左，右为空！
    158. //					Node* minRight = cur->_right;
    159. //					Node* minParent = cur;
    160. //					while (minRight->_left)
    161. //					{
    162. //						minParent = minRight;
    163. //						minRight = minRight->_left;
    164. //					}
    165. //
    166. //					std::swap(cur->_key, minRight->_key);
    167. //					if (minParent->_right == minRight)
    168. //					{
    169. //						minParent->_right = minRight->_right;
    170. //					}
    171. //					else
    172. //					{
    173. //						minParent->_left = minRight->_right;
    174. //					}
    175. //					delete minRight;
    176. //				}
    177. //				return true;
    178. //			}
    179. //		}
    180. //		return false;
    181. //	}
    182. //	void _InOrder(Node* root)
    183. //	{
    184. //		if (root == nullptr)
    185. //			return;
    186. //
    187. //		_InOrder(root->_left);
    188. //		cout << root->_key << " ";
    189. //		_InOrder(root->_right);
    190. //	}
    191. //	void InOrder()
    192. //	{
    193. //		_InOrder(_root);
    194. //	}
    195. //private:
    196. //	Node* _root = nullptr;
    197. //};
    198. //
    199. //int main()
    200. //{
    201. //	BSTree bs;
    202. //	bs.Insert(3);
    203. //	bs.Insert(8);
    204. //	bs.Insert(7);
    205. //	bs.Insert(9);
    206. //	bs.Insert(11);
    207. //
    208. //	bs.InOrder();
    209. //	return 0;
    210. //}
    211.  
    212. /// //
    213. 				//		K V模型
    214.  
    215. template<class K,class V>
    216. struct BSTreeNode {
    217. 	BSTreeNode(const K& key,const V& value)
    218. 		:_key(key)
    219. 		,_value(value)
    220. 		, _left(nullptr)
    221. 		, _right(nullptr)
    222. 	{};
    223.  
    224. 	BSTreeNode* _left;
    225. 	BSTreeNode* _right;
    226. 	K _key;
    227. 	V _value;
    228. };
    229.  
    230. template<class K,class V>
    231. class BSTree
    232. {
    233. 	typedef BSTreeNode Node;
    234. public:
    235. 	bool Insert(const K& key,const V& value)
    236. 	{
    237. 		if (_root == nullptr)
    238. 		{
    239. 			_root = new Node(key,value);
    240. 			return true;
    241. 		}
    242.  
    243. 		Node* parent = nullptr;
    244. 		Node* cur = _root;
    245. 		while (cur)
    246. 		{
    247. 			if (key > cur->_key)
    248. 			{
    249. 				parent = cur;
    250. 				cur = cur->_right;
    251. 			}
    252. 			else if (key < cur->_key)
    253. 			{
    254. 				parent = cur;
    255. 				cur = cur->_left;
    256. 			}
    257. 			else
    258. 			{
    259. 				return false;
    260. 			}
    261. 		}
    262. 		cur = new Node(key, value);
    263. 		//这里别用nullptr去判断,问就是写的时候好像不对
    264. 		if (parent->_key > key)
    265. 		{
    266. 			parent->_left = cur;
    267. 		}
    268. 		else
    269. 		{
    270. 			parent->_right = cur;
    271. 		}
    272. 		return true;
    273. 	}
    274.  
    275. 	Node* Find(const K& key)
    276. 	{
    277. 		Node* cur = _root;
    278. 		while (cur)
    279. 		{
    280. 			if (cur->_key > key)
    281. 			{
    282. 				cur = cur->_left;
    283. 			}
    284. 			else if (cur->_key < key)
    285. 			{
    286. 				cur = cur->_right;
    287. 			}
    288. 			else
    289. 			{
    290. 				return cur;
    291. 			}
    292. 		}
    293. 		return nullptr;
    294. 	}
    295.  
    296. 	//删除有三种情况
    297. 	//要删除的孩子有左节点（1）
    298. 	//要删除的孩子有右节点（2）
    299. 	//要删除的孩子有左，右节点（3）替换法删除
    300. 	//要删除的孩子无节点（属于1或2）
    301. 	bool Erase(const K& key)
    302. 	{
    303. 		Node* cur = _root;
    304. 		Node* parent = nullptr;
    305. 		while (cur)
    306. 		{
    307. 			if (key < cur->_key)
    308. 			{
    309. 				parent = cur;
    310. 				cur = cur->_left;
    311. 			}
    312. 			else if (key > cur->_right)
    313. 			{
    314. 				parent = cur;
    315. 				cur = cur->_right;
    316. 			}
    317. 			else//找到了要删除的节点
    318. 			{
    319. 				// 一个孩子--左为空 or 右为空
    320. 				// 两个孩子 -- 替换法
    321. 				if (cur->_left == nullptr)
    322. 				{
    323. 					if (cur == _root)
    324. 					{
    325. 						_root = cur->_right;
    326. 					}
    327. 					else
    328. 					{
    329. 						if (cur == parent->_left)
    330. 						{
    331. 							parent->_left = cur->_right;
    332. 						}
    333. 						else
    334. 						{
    335. 							parent->_right = cur->_right;
    336. 						}
    337. 					}
    338. 					delete cur;
    339. 				}
    340. 				else if (cur->_right == nullptr)
    341. 				{
    342. 					if (cur == _root)
    343. 					{
    344. 						_root = cur->_left;
    345. 					}
    346. 					else
    347. 					{
    348. 						if (cur == parent->_left)
    349. 						{
    350. 							parent->_left = cur->_left;
    351. 						}
    352. 						else
    353. 						{
    354. 							parent->_right = cur->_left;
    355. 						}
    356. 					}
    357. 					delete cur;
    358. 				}
    359. 				else // 两个孩子都不为空，替换法删除
    360. 					//找到左子树的最大节点或者右子树的最小节点替换
    361. 				{
    362. 					// 右子树的最小节点替代  且右子树最小节点，一定是左，右为空！
    363. 					Node* minRight = cur->_right;
    364. 					Node* minParent = cur;
    365. 					while (minRight->_left)
    366. 					{
    367. 						minParent = minRight;
    368. 						minRight = minRight->_left;
    369. 					}
    370.  
    371. 					std::swap(cur->_key, minRight->_key);
    372. 					if (minParent->_right == minRight)
    373. 					{
    374. 						minParent->_right = minRight->_right;
    375. 					}
    376. 					else
    377. 					{
    378. 						minParent->_left = minRight->_right;
    379. 					}
    380. 					delete minRight;
    381. 				}
    382. 				return true;
    383. 			}
    384. 		}
    385. 		return false;
    386. 	}
    387. 	void _InOrder(Node* root)
    388. 	{
    389. 		if (root == nullptr)
    390. 			return;
    391.  
    392. 		_InOrder(root->_left);
    393. 		cout << root->_key << ": " << root->_value << endl;
    394. 		_InOrder(root->_right);
    395. 	}
    396. 	void InOrder()
    397. 	{
    398. 		_InOrder(_root);
    399. 	}
    400. private:
    401. 	Node* _root = nullptr;
    402. };
    403.  
    404. void TestBSTree()
    405. {
    406. 	//BSTree dict;
    407. 	//dict.Insert("insert", "插入");
    408. 	//dict.Insert("erase", "删除");
    409. 	//dict.Insert("left", "左边");
    410. 	//dict.Insert("string", "字符串");
    411.  
    412. 	//string str;
    413. 	//while (cin >> str)
    414. 	//{
    415. 	//	auto ret = dict.Find(str);
    416. 	//	if (ret)
    417. 	//	{
    418. 	//		cout << str << ":" << ret->_value << endl;
    419. 	//	}
    420. 	//	else
    421. 	//	{
    422. 	//		cout << "单词拼写错误" << endl;
    423. 	//	}
    424. 	//}
    425.  
    426. 	string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
    427. 	// 统计水果出现的次
    428. 	BSTreeint> countTree;
    429. 	
    430. 	for (int i = 0; i < sizeof(strs) / sizeof(strs[0]); i++)
    431. 	{
    432. 		auto ret = countTree.Find(strs[i]);
    433. 		if (ret == nullptr)
    434. 		{
    435. 			countTree.Insert(strs[i], 1);
    436. 		}
    437. 		else
    438. 		{
    439. 			ret->_value++;
    440. 		}
    441. 	}
    442. 	
    443. 	countTree.InOrder();
    444. 	//for (auto str : strs)
    445. 	//{
    446. 	//	auto ret = countTree.Find(str);
    447. 	//	if (ret == NULL)
    448. 	//	{
    449. 	//		countTree.Insert(str, 1);
    450. 	//	}
    451. 	//	else
    452. 	//	{
    453. 	//		ret->_value++;
    454. 	//	}
    455. 	//}
    456. 	//countTree.InOrder();
    457. }
    458.  
    459. int main()
    460. {
    461. 	TestBSTree();
    462. 	return 0;
    463. }
    464.

    最后的最后，创作不易，希望读者三连支持💖

    赠人玫瑰，手有余香💖

  • 相关阅读:
    提前预警，防患未然：看千寻位置如何助力兴国县“跑赢”地质灾害
    java源码系列：HashMap源码验证，自己写的HashMap性能高吗？为什么在JDK8中新增红黑树？
    Python 框架学习 Django篇 (四) 数据库增删改查(CURD)
    games101-3 BRDF101
    解决在 Spring Boot 中运行 JUnit 测试遇到的 NoSuchMethodError 错误
    寄存器（内存访问）
    Linux：进程管理 | 进程创建 | 进程终止 | 进程等待 | 进程替换
    React Native中集成ArcGIS以显示地图、渲染自定义图层和获取地理信息数据
    react的different算法
    蓝桥等考Python组别十二级001
  • 原文地址：https://blog.csdn.net/weixin_62700590/article/details/126903752