• 数据结构之二叉搜索树

    1.二叉搜索树

    1.1 二叉搜索树概念

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

     通过观察可以发现：搜索二叉树走一遍中序遍历可以排成升序.

    1.2 二叉搜索树操作

    1. 二叉搜索树的查找

    2. 二叉搜索树的插入

     插入的具体过程如下：
    a. 树为空，则直接插入

    b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

    3. 二叉搜索树的删除

    删除节点的原则是：必须保持搜索二叉树的特性.

    1.3 二叉搜索树的实现

    1. namespace K
    2. {
    3. 	template<class K>
    4. 	struct BSTreeNode//定义节点的结构体
    5. 	{
    6. 		BSTreeNode<K>* _left;//左孩子指针
    7. 		BSTreeNode<K>* _right;//右孩子指针
    8. 		K _key;//存的值
    9.  
    10. 		BSTreeNode(const K& key)//节点的构造函数
    11. 			:_left(nullptr)
    12. 			,_right(nullptr)
    13. 			,_key(key)
    14. 		{}
    15. 	};
    16.  
    17. 	template<class K>
    18. 	class BSTree
    19. 	{
    20. 		typedef BSTreeNode<K> Node;
    21. 	public:
    22. 		BSTree()//构造函数
    23. 			:_root(nullptr)
    24. 		{}
    25. 		BSTree(const BSTree<K>& t)
    26. 		{
    27. 			_root = Copy(t._root);//调用递归copy去拷贝构造
    28. 		}
    29. 		BSTree<K>& operator=(BSTree<K> t)//利用现代写法进行赋值拷贝
    30. 		{
    31. 			swap(_root, t._root);
    32. 			return *this;
    33. 		}
    34. 		~BSTree()
    35. 		{
    36. 			Destory(_root);//调用Destory去析构
    37. 			_root = nullptr;//将root置空
    38. 		}
    39. 		bool Insert(const K& key)
    40. 		{
    41. 			if (_root == nullptr)//如果刚开始树为空树，那么直接给一个节点给root
    42. 			{
    43. 				_root = new Node(key);
    44. 				return true;
    45. 			}
    46. 			Node* cur = _root;//利用cur去循环迭代找到空位
    47. 			Node* parent = nullptr;//利用parent去记录cur的父亲节点,并且要注意这个刚开始给成nullptr
    48. 			while (cur)//利用循环去找适合key的空位,找到为空的位置就结束
    49. 			{
    50. 				if (key > cur->_key)//大于就去右子树
    51. 				{
    52. 					parent = cur;//进入语句先把父节点赋值
    53. 					cur = cur->_right;//然后再把cur迭代
    54. 				}
    55. 				else if (key < cur->_key)//小于就去左子树
    56. 				{
    57. 					parent = cur;
    58. 					cur = cur->_left;
    59. 				}
    60. 				else
    61. 				{
    62. 					return false;//如果找到与key值相等的节点那么就删除
    63. 				}
    64. 			}//出了while循环说明找到了合适的空位，此时可以开始插入新节点
    65.  
    66. 			cur = new Node(key);//给cur申请一个节点
    67. 			if (key > parent->_key)//这里的if语句判断一定要注意，是用值判断而不是指针
    68. 				parent->_right = cur;
    69. 			else if (key < parent->_key)
    70. 				parent->_left = cur;
    71.  
    72. 			return true;//插入成功返回
    73. 		}
    74. 		Node* Find(const K& key)
    75. 		{
    76. 			Node* cur = _root;
    77. 			while (cur)//利用循环去找
    78. 			{
    79. 				if (key > cur->_key)
    80. 				{
    81. 					cur = cur->_right;
    82. 				}
    83. 				else if (key < cur->_key)
    84. 				{
    85. 					cur = cur->_left;
    86. 				}
    87. 				else
    88. 				{
    89. 					return cur;
    90. 				}
    91. 			}
    92. 			return false;//出了循环还未找到就返回false
    93. 		}
    94. 		bool Erase(const K& key)
    95. 		{
    96. 			Node* cur = _root;
    97. 			Node* parent = nullptr;
    98. 			while (cur)
    99. 			{
    100. 				if (key > cur->_key)
    101. 				{
    102. 					parent = cur;
    103. 					cur = cur->_right;
    104. 				}
    105. 				else if (key < cur->_key)
    106. 				{
    107. 					parent = cur;
    108. 					cur = cur->_left;
    109. 				}//上面两段if语句都是去定位key的位置
    110. 				else//进入else语句则找到了需要删除的节点
    111. 				{
    112. 					if (cur->_left == nullptr)//如果需要删除的节点的左节点为空，即没有左孩子
    113. 					{
    114. 						if (cur == _root)//注：这种情况非常容易被忽略
    115. 						{
    116. 							_root = cur->_right;//如果cur就为根节点的话，也就是右单支的情况，那么把root赋值为cur的右节点
    117. 						}
    118. 						else//cur不为根节点的情况
    119. 						{
    120. 							if (cur == parent->_left)//需要判断cur为父亲的左孩子还是右孩子
    121. 							{
    122. 								parent->_left = cur->_right;//需要将cur的右孩子托孤给父亲
    123. 							}
    124. 							else if (cur == parent->_right)
    125. 							{
    126. 								parent->_right = cur->_right;
    127. 							}
    128. 						}
    129. 						delete cur;//最后删除cur节点
    130. 					}
    131. 					else if (cur->_right == nullptr)//如果需要删除的节点的右节点为空，即没有右孩子
    132. 					{
    133. 						if (cur == _root)//需要特别注意
    134. 						{
    135. 							_root = cur->_left;//如果cur就为根节点的话，也就是左单支的情况，那么把root赋值为cur的左节点
    136. 						}
    137. 						else//cur不为根节点的情况
    138. 						{
    139. 							if (cur == parent->_left)//需要判定的是cur节点为父节点的左孩子还是右孩子
    140. 							{
    141. 								parent->_left = cur->_left;//将cur节点的左孩子托孤给父亲
    142. 							}
    143. 							else if (cur == parent->_right)
    144. 							{
    145. 								parent->_right = cur->_left;
    146. 							}
    147. 						}
    148. 						delete cur;//最后删除cur节点
    149. 					}
    150. 					else
    151. 					{
    152. 						//这种情况最复杂：也就是需要删除的节点左孩子和右孩子都存在的情况
    153. 						//此时我们采用替代法删除
    154. 						Node* minRight = cur->_right;//去被删除的节点的右子树找最小节点，左子树找最大节点道理也是一样的
    155. 						Node* minParent = cur;//注意：这里一定不能给空节点,必须给cur节点
    156. 						//至于为什么不能给空节点,万一下面的while循环进不去，后面的if语句就会造成非法访问
    157. 						while (minRight->_left)//注意:括号里面是左节点不为空时为循环结束的条件,因为我们的目的是去找到最左节点，最左节点已经走到空了，就不要再进入循环了
    158. 						{
    159. 							minParent = minRight;
    160. 							minRight = minRight->_left;
    161. 						}
    162. 						cur->_key = minRight->_key;//将cur的值替换成右子树的最小节点值
    163. 						//走到这里就很容易知道最小节点的左子树一定为空了，但是右子树呢？
    164. 						//右子树如果不为空我们就需要进行托孤，这种托孤方式也就演变成了上面两种简单的方式
    165. 						//但是这一部很容易被遗忘：大家都会觉得minRight一定会是minParent的左孩子
    166. 						//这是错误的理解，这里一定要去判断minRight为minParent右孩子的情况，这里画图理解
    167. 						if (minRight == minParent->_left)//如果为父节点的左孩子，那么就把我的右孩子交给父节点的左孩子
    168. 								minParent->_left = minRight->_right;
    169. 						else if (minRight == minParent->_right)//如果为父节点的右孩子，那么就把我的右孩子交给父节点的右孩子
    170. 								minParent->_right = minRight->_right;
    171. 						delete minRight;
    172. 					}
    173. 					return true;//删除完节点过后返回true
    174. 				}
    175. 			}
    176. 			return false;//出了while循环还没有找到需要删除的节点返回false
    177. 		}
    178. 		bool InsertR(const K& key)//递归插入key
    179. 		{
    180. 			return _InsertR(_root, key);
    181. 		}
    182. 		Node* FindR(const K& key)//递归查找key
    183. 		{
    184. 			return _FindR(_root, key);
    185. 		}
    186. 		bool EraseR(const K& key)//递归删除key
    187. 		{
    188. 			return _EraseR(_root, key);
    189. 		}
    190. 		void Inorder()//中序遍历
    191. 		{
    192. 			_Inorder(_root);//把中序遍历的递归封装一层，传root指针，保护root不被改变
    193. 			cout << endl;
    194. 		}
    195. 	private:
    196. 		void Destory(Node* root)
    197. 		{
    198. 			if (root == nullptr)
    199. 				return;
    200. 			Destory(root->_left);
    201. 			Destory(root->_right);
    202. 			delete root;//利用后序遍历递归删除节点
    203. 		}
    204. 		Node* Copy(Node* root)
    205. 		{
    206. 			if (root == nullptr)
    207. 				return nullptr;
    208. 			Node* newroot = new Node(root->_key);//建立新节点
    209. 			newroot->_left = Copy(root->_left);//新节点的左右节点再去转换成子问题
    210. 			newroot->_right = Copy(root->_right);
    211. 			return newroot;//最后返回新节点
    212. 		}
    213. 		bool _InsertR(Node*& root, const K& key)//注意这里要用引用传参
    214. 		{
    215. 			if (root == nullptr)//root为空时new一个节点
    216. 			{
    217. 				root = new Node(key);
    218. 				return true;
    219. 			}
    220.  
    221. 			if (key > root->_key)
    222. 			{
    223. 				return _InsertR(root->_right, key);
    224. 			}
    225. 			else if (key < root->_key)
    226. 			{
    227. 				return _InsertR(root->_left, key);
    228. 			}
    229. 			else
    230. 			{
    231. 				return false;
    232. 			}
    233. 		}
    234. 		Node* _FindR(Node* root, const K& key)
    235. 		{
    236. 			if (root == nullptr)
    237. 			{
    238. 				return nullptr;
    239. 			}
    240. 			if (key > root->_key)
    241. 			{
    242. 				return _FindR(root->_right, key);
    243. 			}
    244. 			else if (key < root->_key)
    245. 			{
    246. 				return _FindR(root->left, key);
    247. 			}
    248. 			else
    249. 			{
    250. 				return root;
    251. 			}
    252. 		}
    253. 		bool _EraseR(Node*& root, const K& key)//注意这里一定要使用引用传参
    254. 		{
    255. 			if (root == nullptr)//如果root为空则返回false
    256. 			{
    257. 				return false;
    258. 			}
    259. 			if (key > root->_key)
    260. 			{
    261. 				return _EraseR(root->_right, key);
    262. 			}
    263. 			else if (key < root->_key)
    264. 			{
    265. 				return _EraseR(root->_left, key);
    266. 			}
    267. 			else
    268. 			{
    269. 				//找到了该节点
    270. 				if (root->_left == nullptr)//左孩子为空，右孩子存在的情况
    271. 				{
    272. 					Node* del = root;//用del记录一下这个带删除的节点
    273. 					root = root->_right;//然后将root的右节点赋值给root
    274. 					//上面这一步非常巧，左边的root实际是上一层父节点的左孩子或右孩子的引用
    275. 					//这里就体现出了引用传参的作用
    276. 					delete del;//链接关系处理完过后，最后删除这个root节点
    277. 				}
    278. 				else if (root->_right == nullptr)
    279. 				{
    280. 					Node* del = root;
    281. 					root = root->_left;
    282. 					delete del;
    283. 				}
    284. 				else
    285. 				{
    286. 					Node* minRight = root->_right;
    287. 					while (minRight->_left)//递归去找root的右子树中的最左节点，也就是最小节点
    288. 					{
    289. 						minRight = minRight->_left;
    290. 					}
    291. 					K min = minRight->_key;//用变量min存一下这个节点
    292. 					//转换成在root的右子树删除min
    293. 					_EraseR(root->_right, min);//这里转换成子问题去删除min
    294. 					root->_key = min;//再将root的值替换成min
    295. 				}
    296. 				return true;
    297. 			}
    298. 		}
    299. 		void _Inorder(Node* root)
    300. 		{
    301. 			if (root == nullptr)
    302. 				return;
    303.  
    304. 			_Inorder(root->_left);
    305. 			cout << root->_key << " ";
    306. 			_Inorder(root->_right);
    307. 		}
    308. 		Node* _root;
    309. 	};
    310. }

    二叉树实现的代码测试：

    1. void TestBSTree1()
    2. {
    3. 	K::BSTree<int> t;
    4. 	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
    5. 	for (auto e : a)
    6. 	{
    7. 		t.InsertR(e);
    8. 	}
    9. 	t.Inorder();
    10.  
    11. 	t.EraseR(5);
    12. 	t.Inorder();
    13.  
    14. 	t.EraseR(8);
    15. 	t.Inorder();
    16.  
    17. 	t.EraseR(7);
    18. 	t.Inorder();
    19.  
    20. 	t.EraseR(5);
    21. 	t.Inorder();
    22.  
    23. 	// 测试时，把树中的节点删除干净，确保没问题 
    24. 	for (auto e : a)
    25. 	{
    26. 		t.EraseR(e);
    27. 		t.Inorder();
    28. 	}
    29. 	t.Inorder();
    30. }
    31. void TestBSTree2()
    32. {
    33. 	K::BSTree<int> t;
    34. 	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
    35. 	for (auto e : a)
    36. 	{
    37. 		t.InsertR(e);
    38. 	}
    39. 	t.Inorder();
    40.  
    41. 	K::BSTree<int> copy = t;
    42. 	copy.Inorder();
    43. }

    1.4 二叉搜索树的应用

    1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。核心是想要体现在不在的问题。
    比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
    ·以单词集合中的每个单词作为key，构建一棵二叉搜索树
    ·在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
    2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见。核心是想要通过一个值去找另一个值。

    比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
    文单词与其对应的中文就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。
    比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：

    ·<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key

    ·查询英文单词时，只需给出英文单词，就可快速找到与其对应的key

    KV模型的代码：

    1. namespace KV
    2. {
    3. 	template<class K, class V>
    4. 	struct BSTreeNode
    5. 	{
    6. 		BSTreeNode<K, V>* _left;
    7. 		BSTreeNode<K, V>* _right;
    8.  
    9. 		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. 	template<class K, class V>
    20. 	class BSTree
    21. 	{
    22. 		typedef BSTreeNode<K, V> Node;
    23. 	private:
    24. 	// 如果树中已经存在key，返回false
    25. 	bool _InsertR(Node*& root, const K& key, const V& value)
    26. 	{
    27. 		if (root == NULL)  // 插入
    28. 		{
    29. 			root = new Node(key, value);
    30. 			return true;
    31. 		}
    32.  
    33. 		if (root->_key < key)
    34. 		{
    35. 			return _InsertR(root->_right, key, value);
    36. 		}
    37. 		else if (root->_key > key)
    38. 		{
    39. 			return _InsertR(root->_left, key, value);
    40. 		}
    41. 		else
    42. 		{
    43. 			return false;
    44. 		}
    45. 	}
    46.  
    47. 	Node* _FindR(Node* root, const K& key)
    48. 	{
    49. 		if (root == nullptr)
    50. 		{
    51. 			return nullptr;
    52. 		}
    53.  
    54. 		if (root->_key < key)
    55. 		{
    56. 			return _FindR(root->_right, key);
    57. 		}
    58. 		else if (root->_key > key)
    59. 		{
    60. 			return _FindR(root->_left, key);
    61. 		}
    62. 		else
    63. 		{
    64. 			return root;
    65. 		}
    66. 	}
    67.  
    68. 	// 如果树中不存在key，返回false
    69. 	// 存在，删除后，返回true
    70. 	bool _EraseR(Node*& root, const K& key)
    71. 	{
    72. 		if (root == NULL)
    73. 		{
    74. 			return false;
    75. 		}
    76.  
    77. 		if (root->_key < key)
    78. 		{
    79. 			return _EraseR(root->_right, key);
    80. 		}
    81. 		else if (root->_key > key)
    82. 		{
    83. 			return _EraseR(root->_left, key);
    84. 		}
    85. 		else
    86. 		{
    87. 			// 找到了，root就是要删除的节点
    88. 			if (root->_left == nullptr)
    89. 			{
    90. 				Node* del = root;
    91. 				root = root->_right;
    92. 				delete del;
    93. 			}
    94. 			else if (root->_right == nullptr)
    95. 			{
    96. 				Node* del = root;
    97. 				root = root->_left;
    98. 				delete del;
    99. 			}
    100. 			else
    101. 			{
    102. 				Node* minRight = root->_right;
    103. 				while (minRight->_left)
    104. 				{
    105. 					minRight = minRight->_left;
    106. 				}
    107. 				K kmin = minRight->_key;
    108. 				V vMin = minRight->_value;
    109.  
    110. 				// 转换成在root的右子树删除min
    111. 				_EraseR(root->_right, kmin);
    112. 				root->_key = kmin;
    113. 				root->_value = vMin;
    114. 			}
    115.  
    116. 			return true;
    117. 		}
    118. 	}
    119.  
    120. 	void _Destory(Node* root)
    121. 	{
    122. 		if (root == NULL)
    123. 		{
    124. 			return;
    125. 		}
    126.  
    127. 		_Destory(root->_left);
    128. 		_Destory(root->_right);
    129. 		delete root;
    130. 	}
    131.  
    132. 	Node* _Copy(Node* root)
    133. 	{
    134. 		if (root == nullptr)
    135. 		{
    136. 			return nullptr;
    137. 		}
    138.  
    139. 		Node* copyNode = new Node(root->_key, root->_value);
    140. 		copyNode->_left = _Copy(root->_left);
    141. 		copyNode->_right = _Copy(root->_right);
    142.  
    143. 		return copyNode;
    144. 	}
    145.  
    146. 	public:
    147. 		BSTree()
    148. 		:_root(nullptr)
    149. 		{}
    150.  
    151. 		BSTree(const BSTree<K, V>& t)
    152. 		{
    153. 			_root = _Copy(t._root);
    154. 		}
    155.  
    156. 		// t1 = t2
    157. 		BSTree<K, V>& operator=(BSTree<K, V> t)
    158. 		{
    159. 			swap(_root, t._root);
    160. 			return *this;
    161. 		}
    162.  
    163. 		~BSTree()
    164. 		{
    165. 			_Destory(_root);
    166. 			_root = nullptr;
    167. 		}
    168. 		bool InsertR(const K& key, const V& value)
    169. 		{
    170. 			return _InsertR(_root, key, value);
    171. 		}
    172.  
    173. 		Node* FindR(const K& key)
    174. 		{
    175. 			return _FindR(_root, key);
    176. 		}
    177.  
    178. 		bool EraseR(const K& key)
    179. 		{
    180. 			return _EraseR(_root, key);
    181. 		}
    182.  
    183. 		void _InOrder(Node* root)
    184. 		{
    185. 			if (root == nullptr)
    186. 				return;
    187.  
    188. 			_InOrder(root->_left);
    189. 			cout << root->_key << ":" << root->_value << endl;
    190. 			_InOrder(root->_right);
    191. 		}	
    192.  
    193. 		void InOrder()
    194. 		{
    195. 			_InOrder(_root);
    196. 			cout << endl;
    197. 		}
    198.  
    199. 	private:
    200. 		Node* _root;
    201. 	};
    202. }

    KV模型代码测试：
     

    1. void TestBSTree3()
    2. {
    3. 	KV::BSTree<string, string> dict;
    4. 	dict.InsertR("string", "字符串");
    5. 	dict.InsertR("tree", "树");
    6. 	dict.InsertR("left", "左边、剩余");
    7. 	dict.InsertR("right", "右边");
    8. 	dict.InsertR("sort", "排序");
    9. 	// ...插入词库中所有单词
    10. 	string str;
    11. 	while (cin >> str)
    12. 	{
    13. 		KV::BSTreeNode<string, string>* ret = dict.FindR(str);
    14. 		if (ret == nullptr)
    15. 		{
    16. 			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
    17. 		}
    18. 		else
    19. 		{
    20. 			cout << str << "中文翻译:" << ret->_value << endl;
    21. 		}
    22. 	}
    23. }
    24. void TestBSTree4()
    25. {
    26. 	// 统计水果出现的次数
    27. 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    28. 	KV::BSTree<string, int> countTree;
    29. 	for (const auto& str : arr)
    30. 	{
    31. 		// 先查找水果在不在搜索树中
    32. 		// 1、不在，说明水果第一次出现，则插入<水果, 1>
    33. 		//KV::BSTreeNode<string, int>* ret = countTree.FindR(str);
    34. 		auto ret = countTree.FindR(str);
    35. 		if (ret == NULL)
    36. 		{
    37. 			countTree.InsertR(str, 1);
    38. 		}
    39. 		else
    40. 		{
    41. 			ret->_value++;
    42. 		}
    43. 	}
    44.  
    45. 	countTree.InOrder();
    46. }

    1.5 二叉搜索树的性能分析

    插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
    对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
    但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

    最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2N
    最差情况下，二叉搜索树退化为单支树，其平均比较次数为： N/2

    问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？

    所以实际中搜索二叉树，极端情况下没有办法保证效率，所以后面会对搜索二叉树进一步扩展延申:AVLTree,红黑树.他们对搜索二叉树，左右高度提出了要求，非常接近完全二叉树，他们的效率可以达到O(logN)

  • 相关阅读:
    为什么2023年一定要用OKR？
    MySQL常见知识点（面试题）总结
    关于爬虫发展历史，价值，问题和应对恶意爬虫的策略
    Apache Doris 在小鹅通的应用实践
    ACM模式各种输入整理（C++）
    JMU 数科 数据库与数据仓库期末总结（2）选择题
    学生HTML个人网页作业作品 简单的IT技术个人简历模板html下载 简单个人网页设计作业 静态HTML个人博客主页
    【排序算法】选择排序（C语言）
    Fluorescein-PEG-DSPE 磷脂-聚乙二醇-荧光素荧光磷脂PEG衍生物
    uniapp解决scroll滑动之后被u-sticky挡住的问题
  • 原文地址：https://blog.csdn.net/weixin_56054625/article/details/126904922