devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之二叉搜索树_最优二叉查找树

作者：天景科技苑 | 2024-08-08 14:06:18

赞

踩

最优二叉查找树

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，即<Key, Value>的键值对。该种方式在现实生活中非常常见。核心是想要通过一个值去找另一个值。

比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
比如：实现一个简单的英汉词典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)

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号