• 数据结构：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* _left;
    5. 		AVLTreeNode* _right;
    6. 		AVLTreeNode* _parent;
    7. 		int _bf; //平衡因子
    8. 		pair _kv;
    9. 		AVLTreeNode(const pair& 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& 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 = parent;
    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* _left;
    8. 		AVLTreeNode* _right;
    9. 		AVLTreeNode* _parent;
    10. 		int _bf; //平衡因子
    11. 		pair _kv;
    12. 		AVLTreeNode(const pair& 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 Node;
    27. 	public:
    28. 		bool Insert(const pair& 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. }

  • 相关阅读:
    王道机试C++第 4 章 字符串：字符串内容详解及三个小程序 Day29
    自媒体人必看的9个网站，每一个都很实用，值得收藏
    797. 所有可能的路径
    爬虫ip如何加入到代码里实现自动化数据抓取
    怎样评测对比报表工具的性能？
    机器学习：可解释学习
    Leetcode 2862. Maximum Element-Sum of a Complete Subset of Indices
    css笔记
    linux下golang环境安装教程（学习笔记）
    Grafana Loki查询加速：如何在不添加资源的前提下提升查询速度
  • 原文地址：https://blog.csdn.net/decade777555/article/details/136538683