• C++进阶篇4---番外-AVL树

    一、AVL树的概念

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

    【注意】平衡因子是用右子树的高度减去左子树的高度得到的

     

    二、AVL树结点的定义

    1. template<class K,class V>
    2. struct AVLTreeNode {
    3. 	AVLTreeNode* _left;
    4. 	AVLTreeNode* _right;
    5. 	AVLTreeNode* _parent;
    6. 	pair _kv;
    7. 	int _bf;
    8.  
    9.  
    10. 	AVLTreeNode(const pair& kv)
    11. 		:_left(nullptr)
    12. 		, _right(nullptr)
    13. 		, _parent(nullptr)
    14. 		,_kv(kv)
    15. 		,_bf(0)
    16. 	{}
    17. };

     三、AVL树的插入

    AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。
    AVL树的插入过程可以分为两步：
    1. 按照二叉搜索树的方式插入新节点
    2. 调整节点的平衡因子
    1. template<class K,class V>
    2. class AVLTree {
    3. 	typedef AVLTreeNode Node;
    4. public:
    5. 	bool insert(const pair& kv)
    6. 	{
    7. 		if (_root == nullptr)
    8. 		{
    9. 			_root = new Node(kv);
    10. 			return true;
    11. 		}
    12.  
    13. 		Node* cur = _root;
    14. 		Node* parent = nullptr;
    15. 		while (cur)
    16. 		{
    17. 			if(cur->_kv.first>kv.first)
    18. 			{
    19. 				parent = cur;
    20. 				cur = cur->_left;
    21. 			}
    22. 			else if (cur->_kv.first < kv.first)
    23. 			{
    24. 				parent = cur;
    25. 				cur = cur->_right;
    26. 			}
    27. 			else
    28. 			{
    29. 				return false;
    30. 			}
    31. 		}
    32.  
    33. 		cur = new Node(kv);
    34. 		cur->_parent = parent;
    35. 		if (parent->_kv.first > kv.first )
    36. 		{
    37. 			parent->_left = cur;
    38. 		}
    39. 		else
    40. 		{
    41. 			parent->_right = cur;
    42. 		}
    43.  
    44. 		//看树是否还保持平衡
    45. 		while (parent)
    46. 		{
    47. 			//先调整平衡因子---因为插入的结点是叶子节点，所以父结点的平衡因子必然发生变化
    48.             //在根据平衡因子的计算公式height_r - height_l，判断平衡因子的变化
    49. 			if (parent->_left == cur)
    50. 			{
    51. 				parent->_bf--;
    52. 			}
    53. 			else
    54. 			{
    55. 				parent->_bf++;
    56. 			}
    57.  
    58. 			//看是否需要调整以及如何调整
    59. 			//...
    60. 		}
    61. 	}
    62. private:
    63. 	Node* _root = nullptr;
    64. };

    上面代码的插入逻辑和二叉搜索树很相似，这里不多讲了(忘记的或者不了解的可以去看二叉搜索树)，主要看如何判断树是否平衡以及如何调整使得树保持平衡

    这里主要分三种情况：

    1、父节点的平衡因子变成0，则树保持平衡，不需要变化

    解释:父节点的平衡因子变成0，说明之前未正负1，只有如下两种情况

    2、父节点的平衡因子变成正负1，则该子树的高度发生变化，但该子树依旧平衡，要看它的父节点所在的子树是否还能保持平衡

    3、父结点的平衡因子变成正负2，则该子树的不能保持平衡，需要进行旋转调整

    1. template<class K,class V>
    2. class AVLTree {
    3. 	typedef AVLTreeNode Node;
    4. public:
    5. 	bool insert(const pair& kv)
    6. 	{
    7. 		if (_root == nullptr)
    8. 		{
    9. 			_root = new Node(kv);
    10. 			return true;
    11. 		}
    12.  
    13. 		Node* cur = _root;
    14. 		Node* parent = nullptr;
    15. 		while (cur)
    16. 		{
    17. 			if(cur->_kv.first>kv.first)
    18. 			{
    19. 				parent = cur;
    20. 				cur = cur->_left;
    21. 			}
    22. 			else if (cur->_kv.first < kv.first)
    23. 			{
    24. 				parent = cur;
    25. 				cur = cur->_right;
    26. 			}
    27. 			else
    28. 			{
    29. 				return false;
    30. 			}
    31. 		}
    32.  
    33. 		cur = new Node(kv);
    34. 		cur->_parent = parent;
    35. 		if (parent->_kv.first > kv.first )
    36. 		{
    37. 			parent->_left = cur;
    38. 		}
    39. 		else
    40. 		{
    41. 			parent->_right = cur;
    42. 		}
    43.  
    44. 		//看树是否还保持平衡
    45. 		while (parent)
    46. 		{
    47. 			//先调整平衡因子
    48. 			if (parent->_left == cur)
    49. 			{
    50. 				parent->_bf--;
    51. 			}
    52. 			else
    53. 			{
    54. 				parent->_bf++;
    55. 			}
    56.  
    57. 			if (parent->_bf == 0)
    58. 			{
    59. 				break;
    60. 			}
    61. 			else if (parent->_bf == 1 || parent->_bf == -1)
    62. 			{
    63. 				cur = parent;
    64. 				parent = parent->_parent;
    65. 			}
    66. 			else if (parent->_bf == 2 || parent->_bf == -2)
    67. 			{
    68. 				//分4种情况:左单旋，右单旋，先左旋在右旋，先右旋在左旋
    69. 				//...
    70.  
    71.                 //旋转完成后子树就平衡了=> 整个树都平衡了，直接退出循环
    72.                 break;
    73. 			}
    74. 			else
    75. 			{
    76. 				//如果进入这里，说明前面的代码出错
    77. 				assert(0);
    78. 			}
    79. 		}
    80. 	}
    81. private:
    82. 	Node* _root = nullptr;
    83. };

     四、旋转调整

    1、新节点插入较高右子树的右侧---右右：左单旋

    代码如下

    1. 	void _RotateL(Node* parent)
    2. 	{
    3. 		Node* subR = parent->_right;
    4. 		Node* subRL = subR->_left;
    5. 		Node* pParent = parent->_parent;
    6. 		subR->_left = parent;
    7. 		parent->_parent = subR;
    8. 		if (subRL)//注意h==0的情况
    9. 			subRL->_parent = parent;
    10. 		if (_root == parent)
    11. 		{
    12. 			_root = subR;
    13. 			subR->_parent = nullptr;
    14. 		}
    15. 		else
    16. 		{
    17. 			subR->_parent = pParent;
    18. 			if (pParent->_left == parent)
    19. 			{
    20. 				pParent->_left = subR;
    21. 			}
    22. 			else
    23. 			{
    24. 				pParent->_right = subR;
    25. 			}
    26. 		}
    27. 		subR->_bf = parent->_bf = 0;
    28. 	}

    2、 新节点插入较高左子树的左侧---左左：右单旋

    注意事项同上。

    代码如下 

    1. void _RotateR(Node* parent)
    2. 	{
    3. 		Node* subL = parent->_left;
    4. 		Node* subLR = subL->_right;
    5. 		Node* pParent = parent->_parent;
    6. 		subL->_right = parent;
    7. 		parent->_parent = subL;
    8. 		if (subLR)//注意h==0的情况
    9. 			subLR->_parent = parent;
    10. 		if (_root == parent)
    11. 		{
    12. 			_root = subL;
    13. 			subL->_parent = nullptr;
    14. 		}
    15. 		else
    16. 		{
    17. 			subL->_parent = pParent;
    18. 			if (pParent->_left == parent)
    19. 			{
    20. 				pParent->_left = subL;
    21. 			}
    22. 			else
    23. 			{
    24. 				pParent->_right = subL;
    25. 			}
    26. 		}
    27. 		subL->_bf = parent->_bf = 0;
    28. 	}

    3、 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

    代码如下

    1. 	void _RotateRL(Node* parent)
    2. 	{
    3. 		Node* subR = parent->_right;
    4. 		Node* subRL = subR->_left;
    5. 		int bf = subRL->_bf;//提前记录，防止在旋转时被修改
    6. 		_RotateR(parent->_right);
    7. 		_RotateL(parent);
    8. 		if (bf == 0)
    9. 		{
    10. 			parent->_bf = subR->_bf = subRL->_bf = 0;
    11. 		}
    12. 		else if (bf == 1)
    13. 		{
    14. 			parent->_bf = -1;
    15. 			subR->_bf = subRL->_bf = 0;
    16. 		}
    17. 		else
    18. 		{
    19. 			subR->_bf = 1;
    20. 			parent->_bf = subRL->_bf = 0;
    21. 		}
    22. 	}

     4.新节点插入较高左子树的右侧---左右：先左单旋再右单旋

    这个留给读者思考 

    附：

    1. //完整版代码
    2. template<class K,class V>
    3. struct AVLTreeNode {
    4. 	AVLTreeNode* _left;
    5. 	AVLTreeNode* _right;
    6. 	AVLTreeNode* _parent;
    7. 	pair _kv;
    8. 	int _bf;
    9.  
    10.  
    11. 	AVLTreeNode(const pair& kv)
    12. 		:_left(nullptr)
    13. 		, _right(nullptr)
    14. 		, _parent(nullptr)
    15. 		,_kv(kv)
    16. 		,_bf(0)
    17. 	{}
    18. };
    19.  
    20. template<class K,class V>
    21. class AVLTree {
    22. 	typedef AVLTreeNode Node;
    23. public:
    24. 	bool insert(const pair& kv)
    25. 	{
    26. 		if (_root == nullptr)
    27. 		{
    28. 			_root = new Node(kv);
    29. 			return true;
    30. 		}
    31.  
    32. 		Node* cur = _root;
    33. 		Node* parent = nullptr;
    34. 		while (cur)
    35. 		{
    36. 			if (cur->_kv.first > kv.first)
    37. 			{
    38. 				parent = cur;
    39. 				cur = cur->_left;
    40. 			}
    41. 			else if (cur->_kv.first < kv.first)
    42. 			{
    43. 				parent = cur;
    44. 				cur = cur->_right;
    45. 			}
    46. 			else
    47. 			{
    48. 				return false;
    49. 			}
    50. 		}
    51.  
    52. 		cur = new Node(kv);
    53. 		cur->_parent = parent;
    54. 		if (parent->_kv.first > kv.first)
    55. 		{
    56. 			parent->_left = cur;
    57. 		}
    58. 		else
    59. 		{
    60. 			parent->_right = cur;
    61. 		}
    62.  
    63. 		while (parent)
    64. 		{
    65. 			if (parent->_left == cur)
    66. 			{
    67. 				parent->_bf--;
    68. 			}
    69. 			else
    70. 			{
    71. 				parent->_bf++;
    72. 			}
    73.  
    74. 			if (parent->_bf == 0)//为0，说明之前_bf=-1/1,即子树的高度没有发生变化
    75. 			{
    76. 				break;
    77. 			}	
    78. 			else if (parent->_bf == 1 || parent->_bf == -1)//为正负1，说明之前_bf=0，即子树的高度发生变化，并且会影响到上层祖宗结点
    79. 			{
    80. 				cur = parent;
    81. 				parent = parent->_parent;
    82. 			}
    83. 			else if (parent->_bf == 2 || parent->_bf == -2)//为正负2，树明显不平衡，需要旋转调整
    84. 			{
    85. 				if (parent->_bf == 2 && cur->_bf == 1)//如果该子树的严格右边高，则左单旋
    86. 				{
    87. 					_RotateL(parent);
    88. 				}
    89. 				else if (parent->_bf == -2 && cur->_bf == -1)//如果该子树的严格左边高，则右单旋
    90. 				{
    91. 					_RotateR(parent);
    92. 				}
    93. 				else if (parent->_bf == -2 && cur->_bf == 1)//左右旋
    94. 				{
    95. 					_RotateLR(parent);
    96. 				}
    97. 				else if (parent->_bf == 2 && cur->_bf == -1)//右旋左旋
    98. 				{
    99. 					_RotateRL(parent);
    100. 				}
    101. 				
    102. 				break;//旋转之后整个树就平衡了，直接跳出循环
    103. 			}
    104. 			else
    105. 			{
    106. 				//这种情况不可能发生，如果发生就说明程序出错
    107. 				assert(false);
    108. 			}
    109. 		}
    110. 		return true;
    111. 	}
    112.  
    113. 	void _RotateLR(Node* parent)
    114. 	{
    115. 		Node* subL = parent->_left;
    116. 		Node* subLR = subL->_right;
    117. 		int bf = subLR->_bf;
    118. 		_RotateL(parent->_left);
    119. 		_RotateR(parent);
    120. 		if (bf == 1)
    121. 		{
    122. 			subL->_bf = -1;
    123. 			subLR->_bf = parent->_bf = 0;
    124. 		}
    125. 		else if(bf == -1)
    126. 		{
    127. 			parent->_bf = 1;
    128. 			subL->_bf = subLR->_bf = 0; 
    129. 		}
    130. 		else//bf==0，插入的结点就是subLR
    131. 		{
    132. 			parent->_bf = subL->_bf = subLR->_bf = 0;
    133. 		}
    134. 	}
    135.  
    136. 	void _RotateRL(Node* parent)
    137. 	{
    138. 		Node* subR = parent->_right;
    139. 		Node* subRL = subR->_left;
    140. 		int bf = subRL->_bf;
    141. 		_RotateR(parent->_right);
    142. 		_RotateL(parent);
    143. 		if (bf == 1)
    144. 		{
    145. 			parent->_bf = -1;
    146. 			subR->_bf = subRL->_bf = 0;
    147. 		}
    148. 		else if(bf == -1)
    149. 		{
    150. 			subR->_bf = 1;
    151. 			parent->_bf = subRL->_bf = 0;
    152. 		}
    153. 		else //bf==0，插入的结点就是subLR
    154. 		{
    155. 			parent->_bf = subR->_bf = subRL->_bf = 0;
    156. 		}
    157. 	}
    158.  
    159. 	//右单旋
    160. 	void _RotateR(Node*parent)
    161. 	{
    162. 		Node* subL = parent->_left;//找到要作为新根的结点
    163. 		Node* pParent = parent->_parent;//找到该子树的父亲结点
    164. 		Node* subLR = subL->_right;
    165. 		subL->_right = parent;
    166. 		parent->_parent = subL;
    167. 		parent->_left = subLR;
    168. 		if (subLR)
    169. 			subLR->_parent = parent;
    170. 		if (_root == parent)//如果是根
    171. 		{
    172. 			_root = subL;
    173. 			subL->_parent = nullptr;
    174. 		}
    175. 		else
    176. 		{
    177. 			subL->_parent = pParent;
    178. 			if (pParent->_left == parent)
    179. 			{
    180. 				pParent->_left = subL;
    181. 			}
    182. 			else
    183. 			{
    184. 				pParent->_right = subL;
    185. 			}
    186. 		}
    187. 		parent->_bf = subL->_bf = 0;
    188. 	}
    189.  
    190. 	//左单旋
    191. 	void _RotateL(Node* parent)
    192. 	{
    193. 		Node* subR = parent->_right;//找到要作为新根的结点
    194. 		Node* pParent = parent->_parent;//找到该子树的父亲结点
    195. 		Node* subRL = subR->_left;//找到要被"过继"的孩子结点
    196. 		subR->_left = parent;
    197. 		if (subRL)//如有"过继"结点
    198. 			subRL->_parent = parent;
    199. 		parent->_parent = subR;
    200. 		parent->_right = subRL;
    201. 		if (_root == parent)//如果是根
    202. 		{
    203. 			_root = subR;
    204. 			subR->_parent = nullptr;
    205. 		}
    206. 		else
    207. 		{
    208. 			subR->_parent = pParent;
    209. 			if (pParent->_left == parent)
    210. 			{
    211. 				pParent->_left = subR;
    212. 			}
    213. 			else
    214. 			{
    215. 				pParent->_right = subR;
    216. 			}
    217. 		}
    218. 		parent->_bf = subR->_bf = 0;
    219. 	}
    220.  
    221.  
    222. 	bool Isbalance()
    223. 	{
    224. 		return _Isbalance(_root);
    225. 		//return _Isbalance(_root) >= 0;
    226. 	}
    227. 	bool _Isbalance(Node*root)
    228. 	{
    229. 		if (root == nullptr)
    230. 			return true;
    231. 		int left = _Height(root->_left);
    232. 		int right = _Height(root->_right);
    233. 		if (abs(right - left) > 1)
    234. 		{
    235. 			cout << root->_kv.first << ":" << root->_kv.second << endl;
    236. 			return false;
    237. 		}
    238. 		if (right - left != root->_bf)
    239. 		{
    240. 			cout << root->_kv.first << ":"<< "平衡因子出错" << endl;
    241. 			return false;
    242. 		}
    243. 		return _Isbalance(root->_left) && _Isbalance(root->_right);
    244. 	}
    245.  
    246. 	size_t size()
    247. 	{
    248. 		return _size(_root);
    249. 	}
    250.  
    251. 	size_t Height()
    252. 	{
    253. 		return _Height(_root);
    254. 	}
    255.  
    256. private:
    257. 	size_t _Height(Node*root)
    258. 	{
    259. 		if (root == nullptr)
    260. 			return 0;
    261. 		return max(_Height(root->_left),_Height(root->_right)) + 1;
    262. 	}
    263. 	size_t _size(Node* root)
    264. 	{
    265. 		if (root == nullptr)
    266. 			return 0;
    267. 		return 1 + _size(root->_left) + _size(root->_right);
    268. 	}
    269.  
    270.     //如果单纯判断是否平衡可以这么写，-1表示不平衡，>=0表示平衡
    271. 	//int _Isbalance(Node* root)
    272. 	//{
    273. 	//	if (root == nullptr)
    274. 	//		return 0;
    275. 	//	int left = _Isbalance(root->_left);
    276. 	//	if (left < 0) return -1;
    277. 	//	int right = _Isbalance(root->_right);
    278. 	//	if (right < 0) return -1;
    279. 	//	if (abs(right - left) > 1 || right - left != root->_bf)
    280. 	//	{
    281. 	//		return -1;
    282. 	//	}
    283. 	//	return max(left, right) + 1;
    284. 	//}
    285. private:
    286. 	Node* _root = nullptr;
    287. };

  • 相关阅读:
    物联网网关助力生产数据可视化，提升智能管理水平
    若依3.6.0使用Mybatis-plus分页失效以及完美替换Pagehelper【已解决】
    Python:实现merge sort归并排序算法(附完整源码)
    猿创征文｜深度学习基于ResNet18网络完成图像分类
    相机不小心格式化了怎么恢复？如何快速找回珍贵照片
    记一次有趣的逻辑SRC挖掘
    Android Qcom Display学习(十)
    neo4j load csv 配置和使用
    短视频矩阵系统源码技术独立部署搭建
    【计算机视觉 | 目标检测】目标检测常用数据集及其介绍（十二）
  • 原文地址：https://blog.csdn.net/V_zjs/article/details/134266459