• 数据结构：AVL树的旋转（高度平衡树）

    1、AVL树简介

     AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

    • 它的子树都是AVL树
    • 左右子树高度插（平衡因子）的绝对值不超过1

    AVL树还是一个搜索二叉树，只不过因为普通的搜索二叉树有可能变成单只树，这样就使查找效率非常的低。我们就给普通的搜索二叉树增加了一个平衡因子来使AVL左右子树的高度差的绝对值不超过1

    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. 	pair<K, V> _kv;                          // 存储的键对
    8. 	int _bf;                                 // balance factor
    9.  
    10. 	AVLTreeNode(const pair<K, V>& kv)
    11. 		:_left(nullptr)
    12. 		, _right(nullptr)
    13. 		, _parent(nullptr)
    14. 		, _kv(kv)
    15. 		, _bf(0)
    16. 	{}
    17. };
    18.  
    19. template<class K, class V>
    20. class AVLTree
    21. {
    22. 	typedef AVLTreeNode<K, V> Node;
    23. public:
    24. 	bool Insert(const pair<K, V>& kv);
    25. 	bool IsBalance();
    26. 	void InOrder();
    27. 	void Height();
    28.  
    29. private:
    30. 	void RotateL(Node* parent);              //左旋转
    31. 	void RotateR(Node* parent);              //右旋转
    32. 	void RotateRL(Node* parent);             //右左旋转
    33. 	void RotateLR(Node* parent);             //左右旋转
    34. 	bool _IsBalance(Node* root);
    35. 	void _InOrder(Node* root);
    36. 	int _Height(Node* root);
    37.  
    38.  
    39. 	Node* _root = nullptr;
    40. };

    2、AVL树的插入

    • AVL树的插入前面和搜索二叉树的插入一模一样，只不过我们要注意平衡因子
    • 因为AVL树保持平衡是要平衡因子的绝对值不超过1，而插入会使平衡因子改变，所以我们也要要相应的旋转，使平衡因子的绝对值不超过一，我们又有几种情况
    1. 假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
    2. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋。当subR的平衡因子为-1时，执行右左双旋
    3. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋。当subL的平衡因子为1时，执行左右双旋
    4. 旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新
    1. template<class K, class V>
    2. bool AVLTree<K, V>::Insert(const pair<K, V>& kv)
    3. {
    4. 	if (_root == nullptr)
    5. 	{
    6. 		_root = new Node(kv);
    7. 		return true;
    8. 	}
    9.  
    10. 	Node* parent = nullptr;
    11. 	Node* cur = _root;
    12. 	while (cur)
    13. 	{
    14. 		if (cur->_kv.first < kv.first)
    15. 		{
    16. 			parent = cur;
    17. 			cur = cur->_right;
    18. 		}
    19. 		else if (cur->_kv.first > kv.first)
    20. 		{
    21. 			parent = cur;
    22. 			cur = cur->_left;
    23. 		}
    24. 		else
    25. 		{
    26. 			return false;
    27. 		}
    28. 	}
    29.  
    30. 	cur = new Node(kv);
    31. 	if (parent->_kv.first > kv.first)
    32. 	{
    33. 		parent->_left = cur;
    34. 	}
    35. 	else
    36. 	{
    37. 		parent->_right = cur;
    38. 	}
    39. 	cur->_parent = parent;
    40.  
    41. 	// 更新平衡因子
    42. 	while (parent)
    43. 	{
    44. 		if (cur == parent->_right)
    45. 		{
    46. 			parent->_bf++;
    47. 		}
    48. 		else
    49. 		{
    50. 			parent->_bf--;
    51. 		}
    52.  
    53. 		if (parent->_bf == 1 || parent->_bf == -1)
    54. 		{
    55. 			// 继续更新
    56. 			parent = parent->_parent;
    57. 			cur = cur->_parent;
    58. 		}
    59. 		else if (parent->_bf == 0)
    60. 		{
    61. 			break;
    62. 		}
    63. 		else if (parent->_bf == 2 || parent->_bf == -2)
    64. 		{
    65. 			// 需要旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度
    66. 			if (parent->_bf == 2 && cur->_bf == 1)
    67. 			{
    68. 				RotateL(parent);
    69. 			}
    70. 			else if (parent->_bf == -2 && cur->_bf == -1)
    71. 			{
    72. 				RotateR(parent);
    73. 			}
    74. 			else if (parent->_bf == -2 && cur->_bf == 1)
    75. 			{
    76. 				RotateLR(parent);
    77. 			}
    78. 			else if (parent->_bf == 2 && cur->_bf == -1)
    79. 			{
    80. 				RotateRL(parent);
    81. 			}
    82. 			else
    83. 			{
    84. 				assert(false);
    85. 			}
    86.  
    87. 			break;
    88. 		}
    89. 		else
    90. 		{
    91. 			assert(false);
    92. 		}
    93. 	}
    94.  
    95. 	return true;
    96. }

    2.1、左单旋

    1. subRL变成parent的右子树 
    2. parent变成subR的左子树
    3. subR变成新根
    4. 更新平衡因子
    1. template<class K, class V>
    2. void AVLTree<K, V>::RotateL(Node* parent)
    3. {
    4. 	Node* subR = parent->_right;
    5. 	Node* subRL = subR->_left;
    6.  
    7. 	parent->_right = subRL;
    8. 	subR->_left = parent;
    9.  
    10. 	Node* parentParent = parent->_parent;
    11.  
    12. 	parent->_parent = subR;
    13. 	if (subRL)
    14. 		subRL->_parent = parent;
    15.  
    16. 	if (_root == parent)
    17. 	{
    18. 		_root = subR;
    19. 		subR->_parent = nullptr;
    20. 	}
    21. 	else
    22. 	{
    23. 		if (parentParent->_left == parent)
    24. 		{
    25. 			parentParent->_left = subR;
    26. 		}
    27. 		else
    28. 		{
    29. 			parentParent->_right = subR;
    30. 		}
    31.  
    32. 		subR->_parent = parentParent;
    33. 	}
    34.  
    35. 	parent->_bf = subR->_bf = 0;
    36. }

    2.2、右单旋

    60为parent，30为subL，b为subLR 

    1. subLR变成parent的左子树 
    2. parent变成subL的右子树
    3. subL变成新根
    4. 更新平衡因子
    1. template<class K, class V>
    2. void AVLTree<K, V>::RotateR(Node* parent)
    3. {
    4. 	Node* subL = parent->_left;
    5. 	Node* subLR = subL->_right;
    6.  
    7. 	parent->_left = subLR;
    8. 	if (subLR)
    9. 		subLR->_parent = parent;
    10.  
    11. 	Node* parentParent = parent->_parent;
    12.  
    13. 	subL->_right = parent;
    14. 	parent->_parent = subL;
    15.  
    16. 	if (_root == parent)
    17. 	{
    18. 		_root = subL;
    19. 		subL->_parent = nullptr;
    20. 	}
    21. 	else
    22. 	{
    23. 		if (parentParent->_left == parent)
    24. 		{
    25. 			parentParent->_left = subL;
    26. 		}
    27. 		else
    28. 		{
    29. 			parentParent->_right = subL;
    30. 		}
    31.  
    32. 		subL->_parent = parentParent;
    33. 	}
    34.  
    35. 	subL->_bf = parent->_bf = 0;
    36. }

    2.3、左右双旋 

    先对30进行左单旋，先对90右单旋

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

    2.3、右左双旋 

    先对90进行右单旋，先对30左单旋 

    1. template<class K, class V>
    2. void AVLTree<K, V>::RotateRL(Node* parent)
    3. {
    4. 	Node* subR = parent->_right;
    5. 	Node* subRL = subR->_left;
    6. 	int bf = subRL->_bf;
    7.  
    8. 	RotateR(parent->_right);
    9. 	RotateL(parent);
    10.  
    11. 	if (bf == 0)
    12. 	{
    13. 		// subRL自己就是新增
    14. 		parent->_bf = subR->_bf = subRL->_bf = 0;
    15. 	}
    16. 	else if (bf == -1)
    17. 	{
    18. 		// subRL的左子树新增
    19. 		parent->_bf = 0;
    20. 		subRL->_bf = 0;
    21. 		subR->_bf = 1;
    22. 	}
    23. 	else if (bf == 1)
    24. 	{
    25. 		// subRL的右子树新增
    26. 		parent->_bf = -1;
    27. 		subRL->_bf = 0;
    28. 		subR->_bf = 0;
    29. 	}
    30. 	else
    31. 	{
    32. 		assert(false);
    33. 	}
    34. }

     3、AVL树的性能

    AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

    如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合

    4、实现

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

  • 相关阅读:
    Go：定 n 对括号，来生成格式正确的括号的所有组合(附完整源码)
    静电学历史
    【leetcode34----最小差值】
    UE Lyda项目学习 二、距离匹配 步幅适配 同步组
    面试高潮季即将来袭，Android 开发者能否在其中鲤鱼跃龙门？
    人工智能聊天机器人如何帮助您实现工作与生活的平衡
    二、系统知识笔记-系统架构概述
    多测师肖sir_高级讲师_python安装和pycharm（002）
    linux 冷启动热启动
    Stream之flatMap用法
  • 原文地址：https://blog.csdn.net/weixin_74268082/article/details/134227505