• 手撕AVL树

    目录

    一、概念

    二、 结点的定义

    2.1 键值对pair

    2.2 定义细节

    三、 AVL树的插入操作

    3.1 平衡因子调整规则

    3.2 旋转规则

    3.2.1 新结点插入较高左子树的左侧 — 左左:右单旋 

    3.2.2 新结点插入较高右子树的右侧 — 右右:左单旋

    3.2.3 新结点插入较高左子树的右侧 — 左右:左右双旋

    3.2.4 新结点插入较高右子树的左侧 — 右左:右左双旋

    四、 AVL树的删除操作

    五、 AVL树性能分析

    六、 完整代码

    一、概念

    二叉搜索树虽可以缩短查找的效率，但若数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在链表中搜索元素，效率低下。

    因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，若能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
     

    一棵AVL树是空树 或 具有以下性质的二叉搜索树：
    1. 它的左右子树都是AVL树
    2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)    右子树高度减去左子树高度
    3. 若一棵二叉搜索树是高度平衡的，其就是AVL树。
        若它有n个结点，其高度可保持在log_2 n，搜索时间复杂度O(log_2 n)
    4. 不允许键值冗余

    二、 结点的定义

    2.1 键值对pair

    pair是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息

    SGI-STL中对于pair的定义:

    1. template <class T1, class T2>
    2. struct pair
    3. {
    4.     typedef T1 first_type;
    5.     typedef T2 second_type;
    6.     T1 first;
    7.     T2 second;
    8.     pair(): first(T1()), second(T2()) {}
    9.     pair(const T1& a, const T2& b): first(a), second(b) {}
    10. };

    但使用时需要显示指定元素类型会导致代码过长，并且频繁使用时较为麻烦，于是出现make_pair进行自动类型推导。其定义为:

    1. template <class T1,class T2>
    2. pair make_pair (T1 x, T2 y)
    3. {    
    4.     return ( pair(x,y) );
    5. }

    2.2 定义细节

    结点中存储了左子树指针、右子树指针和父指针以及一个键值对(即数据域)、平衡因子。不过平衡因子并不是必要的，没有平衡因子同样可以实现AVL树。

    1. struct AVLTreeNode {
    2. 	AVLTreeNode(const pair& kv) :
    3.             _parent(nullptr), _left(nullptr), 
    4.             _right(nullptr),_data(kv),_balance_factor(0) {}
    5.  
    6. 	AVLTreeNode* _parent;
    7. 	AVLTreeNode* _left;
    8. 	AVLTreeNode* _right;
    9.  
    10. 	pair _data;
    11. 	int _balance_factor;//平衡因子
    12. };

    普通二叉树和搜索二叉树都是二叉链(没有父指针)，为什么AVL树会需要使用三叉链呢？

    这个问题可以从后面的讲解得到答案。
    插入和删除结点、旋转 、平衡因子调整，这些操作都会需要频繁的使用父指针，使用三叉链可以减少查找父结点的时间复杂度并且使得AVL树的实现更加方便。

    三、 AVL树的插入操作

    AVL本质上就是具有特殊性质的二叉搜索树，其插入操作与二叉搜索树较为相似，不过更为复杂。

    AVL树的插入过程可以分为两步
    1. 按照二叉搜索树的方式插入新节点    2. 调整节点的平衡因子

    1. bool insert(const pair& kv) {
    2.     //第一步: 按照二叉搜索树的方式插入新节点 
    3. 	if (_root == nullptr) {
    4. 		_root = new TreeNode(kv);
    5. 		return true;
    6. 	}
    7.  
    8. 	TreeNode* parent = nullptr;
    9. 	TreeNode* cur = _root;
    10. 	while (cur != nullptr) {
    11. 		if (kv.first > cur->_data.first) {
    12. 			parent = cur;
    13. 			cur = cur->_right;
    14. 		}
    15. 		else if (kv.first < cur->_data.first) {
    16. 			parent = cur;
    17. 			cur = cur->_left;
    18. 		}
    19. 		else return false;
    20. 	}
    21. 	cur = new TreeNode(kv);
    22. 	if (kv.first > parent->_data.first) {
    23. 		parent->_right = cur;
    24.     }
    25. 	else { //kv.first < parent->_data.first)
    26. 		parent->_left = cur;
    27. 	}
    28. 	cur->_parent = parent;
    29.     
    30.     //调整平衡因子
    31.     //………………    
    32. }

    但是平衡因子是如何调整的呢？

    3.1 平衡因子调整规则

    1. 若新增结点在其父结点的左边，则父结点的平衡因子 -1；若新增结点在其父结点的右边，则父结点的平衡因子 +1。

    2. 更新后，若父结点的平衡因子为1 或 -1，说明插入前父结点的平衡因子为0,插入后父结点所在子树的高度发生变化，需要继续向上更新

    3.更新后，若父结点的平衡因子为0，说明插入前父结点的平衡因子为1 或 -1，插入到了父结点矮的一边，父结点所在子树的高度并未发生变化，所以不需继续向上更新

    4.更新后，若父结点的平衡因子为2 或 -2，说明插入前父结点的平衡因子为1 或 -1(达到平衡临界值)，插入后已经破坏平衡，此时父结点所子树需要进行旋转处理

    5.更新后，若父结点的平衡因子的绝对值大于2(理论上而言不可能)，说明插入前该树就不是AVL树，需检查之前的操作。

    1. while (parent != nullptr){
    2.     //规则1
    3.     if (cur == parent->_right) ++parent->_balance_factor;
    4. 	else --parent->_balance_factor;
    5.     
    6.     //规则2
    7. 	if(parent->_balance_factor == 0) break;
    8.     
    9.     //规则3
    10. 	else if (abs(parent->_balance_factor) == 1) {
    11. 		cur = parent;
    12. 		parent = parent->_parent;
    13. 	}
    14.  
    15.     //规则4
    16. 	else if (abs(parent->_balance_factor) == 2) {
    17. 		//需要旋转
    18.         //………………
    19. 	}
    20.  
    21.     //规则5
    22.     else {
    23. 		assert(false);
    24. 	}
    25.     return true;
    26. }

    3.2 旋转规则

    AVL树的旋转可以分为四种:

    3.2.1 新结点插入较高左子树的左侧 — 左左:右单旋 

    1. //发生右旋的判断条件
    2. if (parent->_balance_factor == -2 && cur->_balance_factor == -1) {
    3. 	rotate_right(parent);
    4. }
    1. void rotate_right(TreeNode* parent) {
    2. 	TreeNode* subL = parent->_left;
    3. 	TreeNode* subLR = subL->_right;
    4. 	TreeNode* pparent = parent->_parent;//发生旋转的子树的父结点
    5.  
    6. 	parent->_left = subLR;
    7. 	if (subLR != nullptr) subLR->_parent = parent;//h可能为0,即空树
    8. 	subL->_right = parent;
    9. 	parent->_parent = subL;
    10.  
    11.     //父结点所在的子树发生右旋转后，该子树的根结点发生改变
    12. 	if (_root == parent) {
    13. 		_root = subL;
    14. 		subL->_parent = nullptr;
    15. 	}
    16. 	else {
    17. 		if (pparent->_left == parent) pparent->_left = subL;
    18. 		else pparent->_right = subL;
    19. 		subL->_parent = pparent;
    20. 	}
    21.  
    22.     //更新平衡因子
    23. 	subL->_balance_factor = parent->_balance_factor = 0;
    24. }

    3.2.2 新结点插入较高右子树的右侧 — 右右:左单旋

    1. //发生左旋的判断条件
    2. if (parent->_balance_factor == 2 && cur->_balance_factor == 1) {
    3.     rotate_left(parent);
    4. }
    1. void rotate_left(TreeNode* parent) {
    2. 	TreeNode* subR = parent->_right;
    3. 	TreeNode* subRL = subR->_left;
    4. 	TreeNode* pparent = parent->_parent;
    5.  
    6. 	parent->_right = subRL;
    7. 	if (subRL != nullptr) subRL->_parent = parent;
    8. 	subR->_left = parent;
    9. 	parent->_parent = subR;
    10.  
    11. 	//解决根结点变换带来的问题
    12. 	if (_root == parent) {
    13. 		_root = subR;
    14. 		subR->_parent = nullptr;
    15. 	}
    16. 	else {
    17. 		if (pparent->_left == parent) pparent->_left = subR;
    18. 		else pparent->_right = subR;
    19. 		subR->_parent = pparent;
    20. 	}
    21. 	subR->_balance_factor = parent->_balance_factor = 0;
    22. }

    3.2.3 新结点插入较高左子树的右侧 — 左右:左右双旋

    1. void rotate_left_right(TreeNode* parent) {
    2. 	TreeNode* subL = parent->_left;
    3. 	TreeNode* subLR = subL->_right;
    4. 	int bf = subLR->_balance_factor;
    5.  
    6. 	rotate_left(parent->_left);
    7. 	rotate_right(parent);
    8.  
    9. 	//更新平衡因子
    10. 	subLR->_balance_factor = 0;
    11.  
    12.     //情况一
    13. 	if (bf == 1) {
    14. 		parent->_balance_factor = 0;
    15. 		subL->_balance_factor = -1;
    16. 	}
    17.     //情况二
    18. 	else if (bf == -1) {
    19. 		parent->_balance_factor = 1;
    20. 		subL->_balance_factor = 0;
    21. 	}
    22.     //情况三
    23. 	else if (bf == 0) {
    24. 		parent->_balance_factor = 0;
    25. 		subL->_balance_factor = 0;
    26. 	}
    27. 	else assert(false);
    28. }

    3.2.4 新结点插入较高右子树的左侧 — 右左:右左双旋

    1. void rotate_right_left(TreeNode* parent) {
    2. 	TreeNode* subR = parent->_right;
    3. 	TreeNode* subRL = subR->_left;
    4. 	int bf = subRL->_balance_factor;
    5.  
    6. 	rotate_right(parent->_right);
    7. 	rotate_left(parent);
    8.  
    9.     //调整平衡因子
    10. 	subRL->_balance_factor = 0;
    11.  
    12.     //情况一
    13. 	if (bf == 1) {
    14. 		parent->_balance_factor = -1;
    15. 		subR->_balance_factor = 0;
    16. 	}
    17.     //情况二
    18. 	else if (bf == -1) {
    19. 		parent->_balance_factor = 0;
    20. 		subR->_balance_factor = 1;
    21. 	}
    22.     //情况三
    23. 	else if (bf == 0) {
    24. 		parent->_balance_factor = 0;
    25. 		subR->_balance_factor = 0;
    26. 	}
    27.  
    28. 	else assert(false);
    29. }

    四、 AVL树的删除操作

    因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不
    过与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
     

    五、 AVL树性能分析

    AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1
    这样可以保证查询时高效的时间复杂度，即O(log_2 N)
    但是若要对AVL树做一些结构修改的操作，性能非常低下。比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置
    因此若需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合

    六、 完整代码

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using std::cout;
    6. using std::endl;
    7. using std::max;
    8. using std::swap;
    9. using std::pair;
    10. using std::make_pair;
    11.  
    12. template<class K,class V>
    13. struct AVLTreeNode {
    14. 	AVLTreeNode(const pair& kv) :_parent(nullptr), _left(nullptr), _right(nullptr),_data(kv),_balance_factor(0) {}
    15.  
    16. 	AVLTreeNode* _parent;
    17. 	AVLTreeNode* _left;
    18. 	AVLTreeNode* _right;
    19.  
    20. 	pair _data;
    21. 	int _balance_factor;//平衡因子
    22. };
    23.  
    24. template<class K, class V>
    25. class AVLTree 
    26. {
    27. 	typedef AVLTreeNode TreeNode;
    28. public:
    29. 	bool insert(const pair& kv) {
    30. 		if (_root == nullptr) {
    31. 			_root = new TreeNode(kv);
    32. 			return true;
    33. 		}
    34.  
    35. 		TreeNode* parent = nullptr;
    36. 		TreeNode* cur = _root;
    37. 		while (cur != nullptr) {
    38. 			if (kv.first > cur->_data.first) {
    39. 				parent = cur;
    40. 				cur = cur->_right;
    41. 			}
    42. 			else if (kv.first < cur->_data.first) {
    43. 				parent = cur;
    44. 				cur = cur->_left;
    45. 			}
    46. 			else return false;
    47. 		}
    48. 		cur = new TreeNode(kv);
    49. 		if (kv.first > parent->_data.first) {
    50. 			parent->_right = cur;
    51. 		}
    52. 		else { //kv.first < parent->_data.first)
    53. 			parent->_left = cur;
    54. 		}
    55. 		cur->_parent = parent;
    56.  
    57. 		//控制平衡
    58. 		//更新平衡因子
    59. 		while (parent != nullptr){
    60. 			if (cur == parent->_right) ++parent->_balance_factor;
    61. 			else --parent->_balance_factor;
    62.  
    63. 			if(parent->_balance_factor == 0) break;
    64. 			else if (abs(parent->_balance_factor) == 1) {
    65. 				cur = parent;
    66. 				parent = parent->_parent;
    67. 			}
    68. 			else if (abs(parent->_balance_factor) == 2) {
    69. 				//需要旋转
    70. 				if (parent->_balance_factor == 2 && cur->_balance_factor == 1) {
    71. 					rotate_left(parent);
    72. 				}
    73. 				else if (parent->_balance_factor == -2 && cur->_balance_factor == -1) {
    74. 					rotate_right(parent);
    75. 				}
    76. 				else if (parent->_balance_factor == -2 && cur->_balance_factor == 1) {
    77. 					rotate_left_right(parent);
    78. 				}
    79. 				else if (parent->_balance_factor == 2 && cur->_balance_factor == -1) {
    80. 					rotate_right_left(parent);
    81. 				}
    82. 				else assert(false);
    83. 				break;
    84. 			}
    85. 			else {
    86. 				assert(false);
    87. 			}
    88. 		}
    89. 		return true;
    90. 	}
    91.  
    92. 	void inorder() {
    93. 		_inorder(_root);
    94. 	}
    95. 	bool IsBlance() {
    96. 		return _IsBlance(_root);
    97. 	}
    98. private:
    99. 	void _inorder(TreeNode* root) {
    100. 		if (root == nullptr) {
    101. 			return;
    102. 		}
    103. 		_inorder(root->_left);
    104. 		cout << root->_data.first << " ";
    105. 		_inorder(root->_right);
    106. 	}
    107.  
    108. 	bool _IsBlance(TreeNode* root) {
    109. 		if (root == nullptr) return true;
    110.  
    111. 		int diff = Height(root->_right) - Height(root->_left);
    112. 		if (diff != root->_balance_factor) {
    113. 			cout << root->_data.first << "结点的平衡因子异常" << endl;
    114. 			return false;
    115. 		}
    116.  
    117. 		return abs(diff) < 2 && _IsBlance(root->_left) && _IsBlance(root->_right);
    118. 	}
    119. 	int Height(TreeNode* root) {
    120. 		if (root == nullptr) return 0;
    121. 		return max(Height(root->_left),Height(root->_right)) + 1;
    122. 	}
    123.  
    124. 	void rotate_left(TreeNode* parent) {
    125. 		TreeNode* subR = parent->_right;
    126. 		TreeNode* subRL = subR->_left;
    127. 		TreeNode* pparent = parent->_parent;
    128.  
    129. 		parent->_right = subRL;
    130. 		if (subRL != nullptr) subRL->_parent = parent;
    131. 		subR->_left = parent;
    132. 		parent->_parent = subR;
    133.  
    134. 		//解决根结点变换带来的问题
    135. 		if (_root == parent) {
    136. 			_root = subR;
    137. 			subR->_parent = nullptr;
    138. 		}
    139. 		else {
    140. 			if (pparent->_left == parent) pparent->_left = subR;
    141. 			else pparent->_right = subR;
    142. 			subR->_parent = pparent;
    143. 		}
    144. 		subR->_balance_factor = parent->_balance_factor = 0;
    145. 	}
    146.  
    147. 	void rotate_right(TreeNode* parent) {
    148. 		TreeNode* subL = parent->_left;
    149. 		TreeNode* subLR = subL->_right;
    150. 		TreeNode* pparent = parent->_parent;
    151.  
    152. 		parent->_left = subLR;
    153. 		if (subLR != nullptr) subLR->_parent = parent;
    154. 		subL->_right = parent;
    155. 		parent->_parent = subL;
    156.  
    157. 		if (_root == parent) {
    158. 			_root = subL;
    159. 			subL->_parent = nullptr;
    160. 		}
    161. 		else {
    162. 			if (pparent->_left == parent) pparent->_left = subL;
    163. 			else pparent->_right = subL;
    164. 			subL->_parent = pparent;
    165. 		}
    166. 		subL->_balance_factor = parent->_balance_factor = 0;
    167. 	}
    168.  
    169. 	void rotate_left_right(TreeNode* parent) {
    170. 		TreeNode* subL = parent->_left;
    171. 		TreeNode* subLR = subL->_right;
    172. 		int bf = subLR->_balance_factor;
    173.  
    174. 		rotate_left(parent->_left);
    175. 		rotate_right(parent);
    176.  
    177. 		//更新平衡因子
    178. 		subLR->_balance_factor = 0;
    179. 		if (bf == 1) {
    180. 			parent->_balance_factor = 0;
    181. 			subL->_balance_factor = -1;
    182. 		}
    183. 		else if (bf == -1) {
    184. 			parent->_balance_factor = 1;
    185. 			subL->_balance_factor = 0;
    186. 		}
    187. 		else if (bf == 0) {
    188. 			parent->_balance_factor = 0;
    189. 			subL->_balance_factor = 0;
    190. 		}
    191. 		else assert(false);
    192. 	}
    193.  
    194. 	void rotate_right_left(TreeNode* parent) {
    195. 		TreeNode* subR = parent->_right;
    196. 		TreeNode* subRL = subR->_left;
    197. 		int bf = subRL->_balance_factor;
    198.  
    199. 		rotate_right(parent->_right);
    200. 		rotate_left(parent);
    201.  
    202. 		subRL->_balance_factor = 0;
    203. 		if (bf == 1) {
    204. 			parent->_balance_factor = -1;
    205. 			subR->_balance_factor = 0;
    206. 		}
    207. 		else if (bf == -1) {
    208. 			parent->_balance_factor = 0;
    209. 			subR->_balance_factor = 1;
    210. 		}
    211. 		else if (bf == 0) {
    212. 			parent->_balance_factor = 0;
    213. 			subR->_balance_factor = 0;
    214. 		}
    215. 		else assert(false);
    216. 	}
    217. private:
    218. 	TreeNode* _root = nullptr;
    219. };
  • 相关阅读:
    使用Spark清洗统计业务数据并保存到数据库中
    02- 数据结构与算法 - 最长回文子串(动态规划/中心扩展算法/Manacher 算法)
    机器学习/人工智能的笔试面试题目——CNN相关问题总结
    tailwindcss -原子化 CSS 框架
    大模型应用开发：运行你的第一个聊天程序
    git图形化管理工具
    DS1302时钟芯片(SPI协议)
    国债1万亿，你该学点什么
    C/C++通过位操作实现2个uint32_t合并为uint64_t
    请求转发（J2EE）
  • 原文地址：https://blog.csdn.net/GG_Bruse/article/details/127883235