devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构：AVL树_在数据库中配置avl树

作者：小丑西瓜9 | 2024-04-30 04:54:18

赞

踩

在数据库中配置avl树

目录

1、AVL树的概念

2、二叉搜索树的功能与实现

1、AVL树节点定义

2、AVL树的插入

3、AVL树的旋转操作

1、左旋

2、右旋

3、左右旋

 4、右左旋

 3、AVL树完整代码实现

1、AVL树的概念

        在前面的文章中，我们学过了二叉搜索树，二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是 AVL 树
左右子树高度之差 ( 简称平衡因子 ) 的绝对值不超过 1(-1/0/1)
平衡因子：右子树高度减去左子树高度
如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在
O(log2 n) ，搜索时间复杂度 O(log2 n) 。
以下是一个简单AVL树的示例：节点周围的是平衡因子。

2、二叉搜索树的功能与实现

1、AVL树节点定义

  1. template<class K,class V>
  2. 	struct AVLTreeNode
  3. 	{
  4. 		AVLTreeNode<K, V>* _left;
  5. 		AVLTreeNode<K, V>* _right;
  6. 		AVLTreeNode<K, V>* _parent;
  7. 		int _bf; //平衡因子
  8. 		pair<K, V> _kv;
  9. 		AVLTreeNode(const pair<K, V>& kv)
  10. 			:_left(nullptr)
  11. 			, _right(nullptr)
  12. 			, _parent(nullptr)
  13. 			, _bf(0)
  14. 			,_kv(kv)
  15. 		{
  16.  
  17. 		}
  18. 	};
每个节点的平衡因子设置为0，每个节点包含左右指针，以及父节点指针，每个节点的数据用pair来实现，第一个元素为Key来比较。

2、AVL树的插入

AVL树是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看作二叉搜索树

插入过程与二叉搜索树一致，只不过要注意更新节点的平衡因子。

因为平衡因子是右子树高度减去左子树高度，所以如果在左子树添加节点，bf(平衡因子）--，在右子树添加，bf++。

parent节点的平衡因子更新有三种情况：

1、parent的平衡因子为0，说明满足AVL性质，插入成功。

2、parent的平衡因子为1或-1，说明该树的高度增加，需要向上更新。

3、parent的平衡因子为-2或2，说明该节点违反了平衡树性质，需要对其进行旋转处理。

旋转处理下面会介绍，我们先来看插入的代码实现：

  1. bool Insert(const pair<K, V>& kv)
  2. 		{
  3. 			if (_root == nullptr)
  4. 			{
  5. 				_root = new Node(kv);
  6. 				return true;
  7. 			}
  8. 			
  9. 				Node* parent = nullptr;
  10. 				Node* cur = _root;
  11. 				while (cur)
  12. 				{
  13. 					if (cur->_kv.first < kv.first)
  14. 					{
  15. 						parent = cur;
  16. 						cur = cur->_right;
  17. 					}
  18. 					else if (cur->_kv.first > kv.first)
  19. 					{
  20. 						parent = cur;
  21. 						cur = cur->_left;
  22. 					}
  23. 					else
  24. 					{
  25. 						return false;
  26. 					}
  27. 				}
  28. 				cur = new Node(kv);
  29. 				if (parent->_kv.first < kv.first)
  30. 				{
  31. 					parent->_right = cur;
  32. 				}
  33. 				else
  34. 				{
  35. 					parent->_left = cur;
  36. 				}
  37. 				cur->_parent = parent;
  38. 				while (parent)
  39. 				{
  40. 					if (cur == parent->_left)
  41. 					{
  42. 						parent->_bf--;
  43. 					}
  44. 					else
  45. 					{
  46. 						parent->_bf++;
  47. 					}
  48. 					if (parent->_bf == 0)
  49. 					{
  50. 						break;
  51.  
  52. 					}
  53. 					else if (parent->_bf == 1 || parent->_bf == -1)
  54. 					{
  55. 						cur = cur->_parent;
  56. 						parent = parent->_parent;
  57. 					}
  58. 					else if (parent->_bf == 2 || parent->_bf == -2)
  59. 					{
  60. 						if (parent->_bf == 2 && cur->_bf == 1)
  61. 						{
  62. 							RotateL(parent);
  63. 						}
  64. 						else if (parent->_bf == -2 && cur->_bf == -1)
  65. 						{
  66. 							RotateR(parent);
  67. 						}
  68. 						else if (parent->_bf == -2 && cur->_bf == 1)
  69. 						{
  70. 							RotateLR(parent);
  71. 						}
  72. 						else
  73. 						{
  74. 							RotateRL(parent);
  75. 						}
  76. 						break;
  77. 					}
  78. 					else
  79. 					{
  80. 						assert(false);
  81. 					}
  82. 				}
  83. 			return true;
  84. 		}

寻找插入位置与搜索二叉树一致，然后更新平衡因子 ，对于不同的违反AVL树性质需要不同的旋转操作。

3、AVL树的旋转操作

我们先来看左旋对应的情况：

1、左旋

a,b,c具有相同的高度，旋转后注意更新parent和cur的平衡因子为0； 
  1. void RotateL(Node* parent)
  2. 		{
  3. 			Node* sub = parent->_right;
  4. 			Node* subl = sub->_left;
  5. 			parent->_right = subl;
  6. 			if (subl)
  7. 			{
  8. 				subl->_parent = parent;
  9. 			}
  10. 			sub->_left = parent;
  11. 			Node* ppnode = parent->_parent;
  12. 			parent->_parent = sub;
  13. 			if (parent == _root)
  14. 			{
  15. 				_root = sub;
  16. 				sub->_parent = nullptr;
  17. 			}
  18. 			else
  19. 			{
  20. 				if (parent == ppnode->_left)
  21. 				{
  22. 					ppnode->_left = sub;
  23. 				}
  24. 				else
  25. 				{
  26. 					ppnode->_right = sub;
  27. 				}
  28. 				sub->_parent = ppnode;
  29. 			}
  30. 			parent->_bf = 0;
  31. 			sub->_bf = 0;
  32. 		}

2、右旋

原理与左旋相似，不过是向右旋转而已 （a,b,c具有相同的高度）

  1. void RotateR(Node* parent)
  2. 		{
  3. 			Node* sub = parent->_left;
  4. 			Node* subr = sub->_right;
  5. 			parent->_left = subr;
  6. 			if (subr)
  7. 			{
  8. 				subr->_parent = parent;
  9. 			}
  10. 			sub->_right = parent;
  11. 			Node* ppnode = parent->_parent;
  12. 			parent->_parent = sub;
  13. 			if (parent == _root)
  14. 			{
  15. 				_root = sub;
  16. 				sub->_parent = nullptr;
  17. 			}
  18. 			else
  19. 			{
  20. 				if (parent == ppnode->_left)
  21. 				{
  22. 					ppnode->_left = sub;
  23. 				}
  24. 				else
  25. 				{
  26. 					ppnode->_right = sub;
  27. 				}
  28. 				sub->_parent = ppnode;
  29. 			}
  30. 			parent->_bf = 0;
  31. 			sub->_bf = 0;
  32. 		}

3、左右旋

先以subl为根左旋，再以parent为根进行右旋。（a,b,c具有相同的高度）

  1. void RotateLR(Node* parent)
  2. 		{
  3. 			Node* subl = parent->_left;
  4. 			Node* sublr = subl->_right;
  5. 			int bf = sublr->_bf;
  6. 			RotateL(subl);
  7. 			RotateR(parent);
  8. 			if (bf == -1)
  9. 			{
  10. 				sublr->_bf = 0;
  11. 				parent->_bf = 1;
  12. 				subl->_bf = 0;
  13. 			}
  14. 			else if (bf == 1)
  15. 			{
  16. 				sublr->_bf = 0;
  17. 				parent->_bf = 0;
  18. 				subl->_bf = -1;
  19. 			}
  20. 			else if (bf == 0)
  21. 			{
  22. 				subl->_bf = 0;
  23. 				parent->_bf = 0;
  24. 				sublr->_bf = 0;
  25. 			}
  26. 			else
  27. 			{
  28. 				assert(false);
  29. 			}
  30. 		}

根据sublr的平衡因子的不同（也就是插入到了B还是C）来判断如何更新平衡因子。

 4、右左旋

原理与左右旋相似，只是换了个方向。（a,b,c具有相同的高度）

  1. void RotateRL(Node* parent)
  2. 		{
  3. 			Node* subr = parent->_right;
  4. 			Node* subrl = subr->_left;
  5. 			int bf = subrl->_bf;
  6. 			RotateR(subr);
  7. 			RotateL(parent);
  8. 			if (bf == -1)
  9. 			{
  10. 				subrl->_bf = 0;
  11. 				parent->_bf = 0;
  12. 				subr->_bf = 1;
  13. 			}
  14. 			else if (bf == 1)
  15. 			{
  16. 				subrl->_bf = 0;
  17. 				parent->_bf = -1;
  18. 				subr->_bf = 0;
  19. 			}
  20. 			else if(bf==0)
  21. 			{
  22. 				subrl->_bf = 0;
  23. 				parent->_bf = 0;
  24. 				subr->_bf = 0;
  25. 			}
  26. 			else
  27. 			{
  28. 				assert(false);
  29. 			}
  30. 		}

根据sublr的平衡因子的不同（也就是插入到了B还是C）来判断如何更新平衡因子。 

 3、AVL树完整代码实现

内部包含查找以及判断是否是AVL树的函数，以及中序遍历。

  1. #pragma once
  2. namespace AVLTree_test
  3. {
  4. 	template<class K,class V>
  5. 	struct AVLTreeNode
  6. 	{
  7. 		AVLTreeNode<K, V>* _left;
  8. 		AVLTreeNode<K, V>* _right;
  9. 		AVLTreeNode<K, V>* _parent;
  10. 		int _bf; //平衡因子
  11. 		pair<K, V> _kv;
  12. 		AVLTreeNode(const pair<K, V>& kv)
  13. 			:_left(nullptr)
  14. 			, _right(nullptr)
  15. 			, _parent(nullptr)
  16. 			, _bf(0)
  17. 			,_kv(kv)
  18. 		{
  19.  
  20. 		}
  21. 	};
  22.  
  23. 	template<class K,class V>
  24. 	class AVLTree
  25. 	{
  26. 		typedef AVLTreeNode<K, V> Node;
  27. 	public:
  28. 		bool Insert(const pair<K, V>& kv)
  29. 		{
  30. 			if (_root == nullptr)
  31. 			{
  32. 				_root = new Node(kv);
  33. 				return true;
  34. 			}
  35. 			
  36. 				Node* parent = nullptr;
  37. 				Node* cur = _root;
  38. 				while (cur)
  39. 				{
  40. 					if (cur->_kv.first < kv.first)
  41. 					{
  42. 						parent = cur;
  43. 						cur = cur->_right;
  44. 					}
  45. 					else if (cur->_kv.first > kv.first)
  46. 					{
  47. 						parent = cur;
  48. 						cur = cur->_left;
  49. 					}
  50. 					else
  51. 					{
  52. 						return false;
  53. 					}
  54. 				}
  55. 				cur = new Node(kv);
  56. 				if (parent->_kv.first < kv.first)
  57. 				{
  58. 					parent->_right = cur;
  59. 				}
  60. 				else
  61. 				{
  62. 					parent->_left = cur;
  63. 				}
  64. 				cur->_parent = parent;
  65. 				while (parent)
  66. 				{
  67. 					if (cur == parent->_left)
  68. 					{
  69. 						parent->_bf--;
  70. 					}
  71. 					else
  72. 					{
  73. 						parent->_bf++;
  74. 					}
  75. 					if (parent->_bf == 0)
  76. 					{
  77. 						break;
  78.  
  79. 					}
  80. 					else if (parent->_bf == 1 || parent->_bf == -1)
  81. 					{
  82. 						cur = cur->_parent;
  83. 						parent = parent->_parent;
  84. 					}
  85. 					else if (parent->_bf == 2 || parent->_bf == -2)
  86. 					{
  87. 						if (parent->_bf == 2 && cur->_bf == 1)
  88. 						{
  89. 							RotateL(parent);
  90. 						}
  91. 						else if (parent->_bf == -2 && cur->_bf == -1)
  92. 						{
  93. 							RotateR(parent);
  94. 						}
  95. 						else if (parent->_bf == -2 && cur->_bf == 1)
  96. 						{
  97. 							RotateLR(parent);
  98. 						}
  99. 						else
  100. 						{
  101. 							RotateRL(parent);
  102. 						}
  103. 						break;
  104. 					}
  105. 					else
  106. 					{
  107. 						assert(false);
  108. 					}
  109. 				}
  110. 			return true;
  111. 		}
  112.  
  113. 		void RotateL(Node* parent)
  114. 		{
  115. 			Node* sub = parent->_right;
  116. 			Node* subl = sub->_left;
  117. 			parent->_right = subl;
  118. 			if (subl)
  119. 			{
  120. 				subl->_parent = parent;
  121. 			}
  122. 			sub->_left = parent;
  123. 			Node* ppnode = parent->_parent;
  124. 			parent->_parent = sub;
  125. 			if (parent == _root)
  126. 			{
  127. 				_root = sub;
  128. 				sub->_parent = nullptr;
  129. 			}
  130. 			else
  131. 			{
  132. 				if (parent == ppnode->_left)
  133. 				{
  134. 					ppnode->_left = sub;
  135. 				}
  136. 				else
  137. 				{
  138. 					ppnode->_right = sub;
  139. 				}
  140. 				sub->_parent = ppnode;
  141. 			}
  142. 			parent->_bf = 0;
  143. 			sub->_bf = 0;
  144. 		}
  145. 		void RotateR(Node* parent)
  146. 		{
  147. 			Node* sub = parent->_left;
  148. 			Node* subr = sub->_right;
  149. 			parent->_left = subr;
  150. 			if (subr)
  151. 			{
  152. 				subr->_parent = parent;
  153. 			}
  154. 			sub->_right = parent;
  155. 			Node* ppnode = parent->_parent;
  156. 			parent->_parent = sub;
  157. 			if (parent == _root)
  158. 			{
  159. 				_root = sub;
  160. 				sub->_parent = nullptr;
  161. 			}
  162. 			else
  163. 			{
  164. 				if (parent == ppnode->_left)
  165. 				{
  166. 					ppnode->_left = sub;
  167. 				}
  168. 				else
  169. 				{
  170. 					ppnode->_right = sub;
  171. 				}
  172. 				sub->_parent = parent;
  173. 			}
  174. 			parent->_bf = 0;
  175. 			sub->_bf = 0;
  176. 		}
  177.  
  178. 		void RotateLR(Node* parent)
  179. 		{
  180. 			Node* subl = parent->_left;
  181. 			Node* sublr = subl->_right;
  182. 			int bf = sublr->_bf;
  183. 			RotateL(subl);
  184. 			RotateR(parent);
  185. 			if (bf == -1)
  186. 			{
  187. 				sublr->_bf = 0;
  188. 				parent->_bf = 1;
  189. 				subl->_bf = 0;
  190. 			}
  191. 			else if (bf == 1)
  192. 			{
  193. 				sublr->_bf = 0;
  194. 				parent->_bf = 0;
  195. 				subl->_bf = -1;
  196. 			}
  197. 			else if (bf == 0)
  198. 			{
  199. 				subl->_bf = 0;
  200. 				parent->_bf = 0;
  201. 				sublr->_bf = 0;
  202. 			}
  203. 			else
  204. 			{
  205. 				assert(false);
  206. 			}
  207. 		}
  208. 		void RotateRL(Node* parent)
  209. 		{
  210. 			Node* subr = parent->_right;
  211. 			Node* subrl = subr->_left;
  212. 			int bf = subrl->_bf;
  213. 			RotateR(subr);
  214. 			RotateL(parent);
  215. 			if (bf == -1)
  216. 			{
  217. 				subrl->_bf = 0;
  218. 				parent->_bf = 0;
  219. 				subr->_bf = 1;
  220. 			}
  221. 			else if (bf == 1)
  222. 			{
  223. 				subrl->_bf = 0;
  224. 				parent->_bf = -1;
  225. 				subr->_bf = 0;
  226. 			}
  227. 			else if(bf==0)
  228. 			{
  229. 				subrl->_bf = 0;
  230. 				parent->_bf = 0;
  231. 				subr->_bf = 0;
  232. 			}
  233. 			else
  234. 			{
  235. 				assert(false);
  236. 			}
  237. 		}
  238.  
  239. 		void _InOrder(Node* root)
  240. 		{
  241. 			if (root == nullptr)
  242. 				return;
  243. 			_InOrder(root->_left);
  244. 			cout << root->_kv.first << " " << root->_bf << endl;
  245. 			_InOrder(root->_right);
  246. 		}
  247. 		void InOrder()
  248. 		{
  249. 			_InOrder(_root);
  250. 		}
  251.  
  252. 		int Height(Node* root)
  253. 		{
  254. 			if (root == nullptr)
  255. 			{
  256. 				return 0;
  257. 			}
  258. 			int leftHeight = Height(root->_left);
  259. 			int rightHeight = Height(root->_right);
  260.  
  261. 			return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
  262. 		}
  263. 		bool _IsBalance(Node* root)
  264. 		{
  265. 			if (root == nullptr)
  266. 				return true;
  267. 			int leftHeight = Height(root->_left);
  268. 			int rightHeight = Height(root->_right);
  269. 			if (abs(rightHeight - leftHeight) >= 2)
  270. 			{
  271. 				cout << root->_kv.first << "不平衡" << endl;
  272. 				return false;
  273. 			}
  274. 			if (rightHeight - leftHeight != root->_bf)
  275. 			{
  276. 				cout << root->_kv.first << "平衡因子异常" << endl;
  277. 				return false;
  278. 			}
  279. 			return _IsBalance(root->_left) && _IsBalance(root->_right);
  280. 		}
  281. 		bool IsBalance()
  282. 		{
  283. 			return _IsBalance(_root);
  284. 		}
  285. 		Node* Find(const K& key)
  286. 		{
  287. 			Node* cur = _root;
  288. 			while (cur)
  289. 			{
  290. 				if (cur->_kv.first < key)
  291. 				{
  292. 					cur = cur->_right;
  293. 				}
  294. 				else if (cur->_kv.first > key)
  295. 				{
  296. 					cur = cur->_left;
  297. 				}
  298. 				else
  299. 				{
  300. 					return cur;
  301. 				}
  302. 			}
  303. 			return NULL;
  304. 		}
  305. 	private:
  306. 		Node* _root = nullptr;
  307. 	};
  308. 	void TestAVLTree1()
  309. 	{
  310. 		int a[] = { 4, 2, 6, 1,0 ,67,56,33,212,90};
  311. 		AVLTree<int, int> t;
  312. 		for (auto e : a)
  313. 		{
  314. 			if (e == 14)
  315. 			{
  316. 				int x = 0;
  317. 			}
  318.  
  319. 			t.Insert(make_pair(e,e));
  320. 		}
  321.  
  322. 		t.InOrder();
  323. 		cout << t.IsBalance();
  324. 	}
  325. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/511500
推荐阅读
相关标签

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

  

闽ICP备14008679号