• 二叉搜索树

    目录

    二叉搜索树概念

    二叉树搜索树的模拟实现

    1.插入 Insert

    2.Erase 删除结点（难点）

    3.InOder (中序遍历)

    4.Find 

    递归实现方式

    完整代码

    总结

    二叉搜索树概念

    其又称二叉排序树、二叉查找树。

    满足以下性质：
    非空左子树的key值小于根结点的key值；

    非空右子树的key值大于根结点的key值；

    左、右子树都是二叉搜索树。

    二叉树搜索树的模拟实现

    1.插入 Insert

     在树中，寻找适合key插入的位置，找到插入返回true ,已有重复key返回false.

    思路：

    比较key 和根结点的_key   如果key大于_key 往根的右子树去找   

    如果key小于_key 往根的左子树去找

    如果树中不存在已有的key 则必定走到空结点 ，链接上key的值即可

    如果树中存在key 结束查找 返回false 

    画图辅助理解

    在树中，插入key为五的结点：

    定义一个cur临时结点

    1--比较cur->_key 与key（下面简称比较）   key小于cur->_key   往左子树中查找 cur=cur->left

    2--比较   key>cur->_key   往右子树查找   cur=cur->right

    3--比较    key_key  往左子树查找  cur=cur->left

    4--比较     key>cur->_key    往右子树查找   cur=cur->right  

    5--cur为空  找到可以链接的位置 链接上结点

     以下有俩点需要注意：

    1.如果树为空 ，则需要先创建树

    2.链接结点，需要保存cur的父亲

    下面代码演示

    1. 		bool Insert(const K& key)
    2. 		{
    3. 			if (_root == nullptr)
    4. 			{
    5. 				_root = new Node(key);
    6. 				return true;
    7. 			}
    8. 			
    9. 			//找到适合插入的位置
    10. 			Node* cur = _root;
    11. 			Node* parent = nullptr;
    12. 			while (cur) 
    13. 			{
    14. 				parent = cur;  //更新parent
    15. 				if (cur->_key > key)
    16. 				{
    17. 					cur = cur->_left;
    18. 				}
    19. 				else if (cur->_key < key) //更新parent
    20. 				{
    21. 					cur = cur->_right;
    22. 				}
    23. 				else
    24. 					return false;
    25. 			}
    26.  
    27. 			//准备插入  插入点一定是空结点
    28. 			cur = new Node(key);
    29.  
    30. 			//判断插入父亲的左还是右
    31. 			if (parent->_key > key) parent->_left = cur;
    32. 			else parent->_right = cur;
    33.  
    34. 			//插入成功
    35. 			return true; 
    36.  
    37. 		}

    2.Erase 删除结点（难点）

    关于二叉搜索树的删除相对不容易，需要考虑多种情况，下面就来详细解释。

    上图列举四种具有代表性的删除结点

    分别是：

    key结点的左和右子树都为空     key的左子树为空  key的右子树为空  key的左和右子树都不为空

    对于左子树右子树都为空 我们可以归于左子树或者右子树为空的一种中

    下文 只需要对 2  3  4三种方式进行剖析

    这三种方式都必须先找到cur

    找cur的方式与inser相同 ，在此不做介绍

    1）cur的左为空

    --1--判断cur是否为根结点   是则将cur->left赋值给_root 

    --2--判断cur是父亲的左还是右 ，链接cur->right

    2)cur的右为空

    该方式与1）类似 

    需要判断cur是否为root结点 

    不为root则需要判断是父亲的左还是右结点

    在此不做过多的介绍

    3)cur的左和右子树都不为空

    如果我们简单的删除cur ，则破坏搜索二叉树，因此我们引入替换法

    在cur的子树中，找到一个合适的值替换，使树仍为搜索二叉树

    找替换结点的方式：
    左子树中，找最大    

    右子树中，找最小

    如果我们要删除key为3的结点 因为cur的结点有左子树和右子树 所以需要找替换 

    我们找cur右子树的最小值 即右子树最左边的元素  4  

    交换 3 和 4的值  然后删除 rightmin的结点  

    要删除rightmin结点 需要注意该结点的右子树需要被链接到cur的父亲上  

    代码剖析

    1. 		bool Erase(const K& key)
    2. 		{
    3. 			//1.k的左为空
    4. 			//2.k的右为空
    5. 			//3.k左右都存在，替换删除
    6.  
    7. 			Node* cur = _root;
    8. 			Node* parent = nullptr;
    9. 			while (cur)
    10. 			{
    11. 				parent = cur; //更新父亲
    12. 				if (cur->_key < key) cur = cur->_right;
    13. 				else if (cur->_key > key) cur = cur->_left;
    14.  
    15. 				//找到了
    16. 				else
    17. 				{
    18. 					//1.左为空
    19. 					if (cur->_left == nullptr)
    20. 					{
    21.  
    22. 						//删除点为根
    23. 						if (cur == _root) _root = cur->_right;
    24.  
    25. 						//判断是父亲的左、右链接
    26. 						if (parent->_right == cur)  //右链接
    27. 						{
    28. 							parent->_right = cur->_right;
    29. 						}
    30. 						else
    31. 						{
    32. 							parent->_left = cur->_right;
    33. 						}
    34.  
    35. 					}
    36.  
    37. 					//2.右为空
    38. 					else if (cur->_right == nullptr)
    39. 					{
    40. 						//删除点为根
    41. 						if (cur == _root) _root = cur->_left;
    42.  
    43. 						//判断是父亲的左、右链接
    44. 						if (parent->_right == cur)  //右链接
    45. 						{
    46. 							parent->_right = cur->_left;
    47. 						}
    48. 						else
    49. 						{
    50. 							parent->_left = cur->_left;
    51. 						}
    52. 					}
    53.  
    54. 					//3.替换
    55. 					else
    56. 					{
    57. 						//找右数的最小 右子树的最左边元素
    58. 						Node* pminright = cur;
    59. 						Node* minright = cur->_right;
    60. 						
    61. 						//找到左树空就找到了
    62. 						while (minright->_left)
    63. 						{
    64. 							pminright = minright;  //保存父亲结点
    65. 							minright = minright->_right;	
    66. 						}
    67.  
    68. 						cur->_key = minright->_key;  //交换
    69.  
    70. 						//判断是父亲的左子树还是右子树要被删除
    71. 						if (pminright->_left ==minright )
    72. 							pminright->_left = minright->_right;
    73. 						else 
    74. 							pminright->_right= minright->_right;
    75. 					}
    76. 				}
    77. 			}
    78. 			delete(cur);
    79. 			return true;
    80. 		}

     

    3.InOder (中序遍历)

    规则：左子树 ——根结点——右子树

     

    遍历顺序  1  3  4  6  7  8  10  13  14 

    搜索二叉树的中序遍历可以将key按照大小遍历出

    对于一个类中，我们调用InOder函数 是无法传递私有变量_root 

    因为写一个子函数提供遍历

    1. 		void InOrder()
    2. 		{
    3. 			_InOrder(_root);
    4. 		}
    5. 		void _InOrder(Node* root)
    6. 		{
    7. 			if (root == nullptr) return;
    8.  
    9. 			_InOrder(root->_left);
    10. 			cout << root->_key << ":" << root->_val << endl;
    11. 			_InOrder(root->_right);
    12.  
    13. 		}

    4.Find 

    查找树中是否存在值为key的函数，找到返回结点指针，找不到返回空

    思路是从根结点开始 ，如果key 小于cur->_key 那么往左子树查找，大于则往右子树查找

    1. 		Node* Find(const K& key)
    2. 		{
    3. 			Node* cur = _root;
    4. 			while (cur)
    5. 			{
    6. 				if (cur->_key < key)
    7. 					cur = cur->_right;
    8. 				else if (cur->_key > key)
    9. 					cur = cur->_left;  
    10. 				else
    11. 					return cur;
    12. 			}
    13.  
    14. 			return nullptr; //没找到，返回空指针
    15. 		}

    递归实现方式

    关于递归的实现，其思路较简单 方法与循坏类似

    写代码有一条不成文的准则：

    能用循坏，尽量不用递归，避免栈溢出；

    对于二叉搜索树的递归 需要注意：
    --1--递归要传入结点参数，要写子函数调用

    --2--cur的链接，不需要保存父亲结点 引用cur的指针  

    完整代码
     

    展示key_value模型应用的代码

    1. #include<iostream>
    2. #include<string>
    3. using namespace std;
    4.  
    5.  
    6. namespace key_val
    7. {
    8. 	template<class K, class V> //key和value
    9. 	//node
    10. 	struct BSTreeNode
    11. 	{
    12. 		BSTreeNode<K, V>* _left;
    13. 		BSTreeNode<K, V>* _right;
    14. 		K _key;
    15. 		V _val;
    16.  
    17. 		BSTreeNode(const K& key, const V& val)
    18. 			:_left(nullptr),
    19. 			_right(nullptr),
    20. 			_key(key),
    21. 			 _val(val)
    22. 		{}
    23. 	};
    24.  
    25. 	template<class K,class V>
    26. 	class BSTree
    27. 	{
    28. 		typedef BSTreeNode<K, V> Node;
    29. 	public:
    30. 		bool Insert(const K& key, const V& value)
    31. 		{
    32. 			if (_root == nullptr)
    33. 			{
    34. 				_root = new Node(key, value);
    35. 				return true;
    36. 			}
    37. 			
    38. 			//找到适合插入的位置
    39. 			Node* cur = _root;
    40. 			Node* parent = nullptr;
    41. 			while (cur) 
    42. 			{
    43. 				parent = cur;  //更新parent
    44. 				if (cur->_key > key)
    45. 				{
    46. 					cur = cur->_left;
    47. 				}
    48. 				else if (cur->_key < key) //更新parent
    49. 				{
    50. 					cur = cur->_right;
    51. 				}
    52. 				else
    53. 					return false;
    54. 			}
    55.  
    56. 			//准备插入  插入点一定是空结点
    57. 			cur = new Node(key, value);
    58.  
    59. 			//判断插入父亲的左还是右
    60. 			if (parent->_key > key) parent->_left = cur;
    61. 			else parent->_right = cur;
    62.  
    63. 			//插入成功
    64. 			return true; 
    65.  
    66. 		}
    67. 		Node* Find(const K& key)
    68. 		{
    69. 			Node* cur = _root;
    70. 			while (cur)
    71. 			{
    72. 				if (cur->_key < key)
    73. 					cur = cur->_right;
    74. 				else if (cur->_key > key)
    75. 					cur = cur->_left;  
    76. 				else
    77. 					return cur;
    78. 			}
    79.  
    80. 			return nullptr; //没找到，返回空指针
    81. 		}
    82.  
    83.  
    84. 		bool Erase(const K& key)
    85. 		{
    86. 			//1.k的左为空
    87. 			//2.k的右为空
    88. 			//3.k左右都存在，替换删除
    89.  
    90. 			Node* cur = _root;
    91. 			Node* parent = nullptr;
    92. 			while (cur)
    93. 			{
    94. 				parent = cur; //更新父亲
    95. 				if (cur->_key < key) cur = cur->_right;
    96. 				else if (cur->_key > key) cur = cur->_left;
    97.  
    98. 				//找到了
    99. 				else
    100. 				{
    101. 					//1.左为空
    102. 					if (cur->_left == nullptr)
    103. 					{
    104.  
    105. 						//删除点为根
    106. 						if (cur == _root) _root = cur->_right;
    107.  
    108. 						//判断是父亲的左、右链接
    109. 						if (parent->_right == cur)  //右链接
    110. 						{
    111. 							parent->_right = cur->_right;
    112. 						}
    113. 						else
    114. 						{
    115. 							parent->_left = cur->_right;
    116. 						}
    117.  
    118. 					}
    119.  
    120. 					//2.右为空
    121. 					else if (cur->_right == nullptr)
    122. 					{
    123. 						//删除点为根
    124. 						if (cur == _root) _root = cur->_left;
    125.  
    126. 						//判断是父亲的左、右链接
    127. 						if (parent->_right == cur)  //右链接
    128. 						{
    129. 							parent->_right = cur->_left;
    130. 						}
    131. 						else
    132. 						{
    133. 							parent->_left = cur->_left;
    134. 						}
    135. 					}
    136.  
    137. 					//3.替换
    138. 					else
    139. 					{
    140. 						//找右数的最小 右子树的最左边元素
    141. 						Node* pminright = cur;
    142. 						Node* minright = cur->_right;
    143. 						
    144. 						//找到左树空就找到了
    145. 						while (minright->_left)
    146. 						{
    147. 							pminright = minright;  //保存父亲结点
    148. 							minright = minright->_right;	
    149. 						}
    150.  
    151. 						cur->_key = minright->_key;  //交换
    152.  
    153. 						//判断是父亲的左子树还是右子树要被删除
    154. 						if (pminright->_left ==minright )
    155. 							pminright->_left = minright->_right;
    156. 						else 
    157. 							pminright->_right= minright->_right;
    158. 					}
    159. 				}
    160. 			}
    161. 			delete(cur);
    162. 			return true;
    163. 		}
    164.  
    165. 		void InOrder()
    166. 		{
    167. 			_InOrder(_root);
    168. 		}
    169. 		void _InOrder(Node* root)
    170. 		{
    171. 			if (root == nullptr) return;
    172.  
    173. 			_InOrder(root->_left);
    174. 			cout << root->_key << ":" << root->_val << endl;
    175. 			_InOrder(root->_right);
    176.  
    177. 		}
    178.  
    179. 	private:
    180. 		Node* _root = nullptr;
    181. 	
    182. 	
    183. 	};

    总结

    本文重点学习搜索二叉树的插入和删除，它具有快速查找的功能，在查找具有O(logN)-O(N)的效率，关于搜索二叉树的实现，有较多的细节，也要仔细甄别。

  • 相关阅读:
    云计算（Docker）
    Json简介与基本使用
    Go语言中的defer关键字
    转发与重定向的使用
    tar 和 zip 打包压缩命令
    Vue生命周期
    481、神奇字符串
    系统打印服务已关闭，竟然是它的问题！
    【oncmdmsg 鼠标】2023/8/19 上午9:50:14
    阿里CTO程立：阿里巴巴的开源历程、理念和实践
  • 原文地址：https://blog.csdn.net/m0_73299809/article/details/134066527