• 数据结构——AVL树

    目录

    1.什么是AVL树？

    2.AVL树插入的模拟实现

    ①节点定义

    ②插入

    ③旋转

    ⑴右单旋

    ⑵左单旋

    ⑶双旋（右左旋）

    ⑷双旋（左右旋）

    ⑸完整的插入代码

    3.AVL树的性能分析

    1.什么是AVL树？

    AVL树是一种自平衡二叉查找树，也被称为高度平衡树。它具有以下特点：

    1. 它本身是一棵二叉搜索树，即每个结点包含一个关键字和两个子结点，且满足左子树中所有关键字小于该结点的关键字，右子树中所有关键字大于该结点的关键字。
    2. AVL树带有平衡条件，即每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。为了保持这种平衡，可能需要通过一次或多次树旋转来重新平衡，这可能需要对树进行调整。

    2.AVL树插入的模拟实现

    ①节点定义

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

    因为在使用过程中可能会频繁使用到父节点，因此我们将其设计为三叉链，且在这里我们设计一个平衡因子（注：在AVL树中可能没有平衡因子，在这里引入平衡因子只是为了方便我们理解），规定一个初始节点的平衡因子为0，当它的左子树中出现新节点时平衡因子就--，右子树中出现新节点时平衡因子就++，当平衡因子==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* cur = _root;
    10. 	Node* parent = nullptr;
    11. 	// 寻找要插入的位置
    12. 	while (cur)
    13. 	{
    14. 		if (kv.first < cur->_kv.first)
    15. 		{
    16. 			parent = cur;
    17. 			cur = cur->_left;
    18. 		}
    19. 		else if (kv.first > cur->_kv.first)
    20. 		{
    21. 			parent = cur;
    22. 			cur = cur->_right;
    23. 		}
    24. 		else
    25. 		{
    26. 			return false;
    27. 		}
    28. 	}
    29.  
    30. 	// 到此处cur已经指向了应该插入的位置，
    31. 	// 然后判断应该插入到parent的哪边
    32. 	cur = new Node(kv);
    33. 	if (kv.first > cur->_kv.first)
    34. 	{
    35. 		parent->_right = cur;
    36. 	}
    37. 	else
    38. 	{
    39. 		parent->_left = cur;
    40. 	}
    41. 	cur->_parent = parent;
    42.  
    43. 	// 插入完成后要更改平衡因子
    44. 	// 从父节点向上更新一直更新到平衡因子为0(已平衡)
    45. 	// 或者更新到平衡因子为2或-2(已失衡)
    46. 	// 或者更新到根节点的父节点为止
    47. 	while (parent)
    48. 	{
    49. 		if (cur == parent->_left)
    50. 			parent->_bf--;
    51. 		else
    52. 			parent->_bf++;
    53.  
    54. 		if (parent->_bf == 0)
    55. 		{
    56. 			break;
    57. 		}
    58. 		else if (parent->_bf == -1 || parent->_bf == 1)
    59. 		{
    60. 			cur = parent;
    61. 			parent = parent->_parent;
    62. 		}
    63. 		else if (parent->_bf == 2 || parent->_bf == -2)
    64. 		{
    65. 			// 此时当前节点已失衡，需要通过旋转来调整
    66.  
    67. 			// ......(在下方结合图片具体分析)
    68. 		}
    69. 		else
    70. 		{
    71. 			assert();
    72. 		}
    73. 	}
    74.  
    75. 	return true;
    76. }

    ③旋转

    根据插入位置的不同，可以具体地将它们大致分为四类。它们分别有对应的旋转策略，在这里我们使用先特殊后推广到一般的方法来解释

    ⑴右单旋

    此情况适用于新节点插入较高左子树的左侧时，抽象图如下

    当h==0时，示例图如下

    当h==1时，示例图如下

    接下来推广到一般，示例图如下

    不难看出，右单旋操作的关键是将当前节点（即5）的右边赋给父节点（即10）的左边，然后将当前节点（即5）的右边指向父节点，再增添一些细节后可以得到如下右单旋代码

    1. void RotateR(Node* parent)
    2. {
    3. 	Node* cur = parent->_left;    // 记录当前节点
    4. 	Node* curright = cur->_right; // 记录当前节点的右节点
    5.  
    6. 	// 如果当前节点的右节点为空说明是h为0的情况
    7. 	// 不为空时就要进行节点间的连接
    8. 	if (curright) 
    9. 	{
    10. 		curright->_parent = parent;
    11. 	}
    12.  
    13. 	parent->_left = curright;
    14. 	cur->_right = parent;
    15.  
    16. 	// 此时需要确定parent是否属于子树
    17. 	if (parent == _root)
    18. 	{
    19. 		_root = cur;
    20. 		cur->_parent = nullptr;
    21. 	}
    22. 	else // 此时parent以下的节点属于子树
    23. 	{
    24. 		cur->_parent = parent->_parent;
    25.  
    26. 		// 确认parent与其父节点间的关系
    27. 		// 然后将cur与parent的父节点连接起来
    28. 		if (parent->_parent->_left == parent)
    29. 		{
    30. 			parent->_parent->_left = cur;
    31. 		}
    32. 		else
    33. 		{
    34. 			parent->_parent->_right = cur;
    35. 		}
    36. 	}
    37. 	parent->_parent = cur;
    38.  
    39. 	// 在进行右单旋后，当前节点与父节点的平衡因子均变为0
    40. 	cur->_bf = parent->_bf = 0;
    41. }

    ⑵左单旋

    此情况适用于新节点插入较高右子树的右侧，抽象图如下

    其具体情况与右单旋类似，这里就不过多赘述，直接给出代码

    1. void RotateL(Node* parent)
    2. {
    3. 	Node* cur = parent->_right;    // 记录当前节点
    4. 	Node* curleft = cur->_left; // 记录当前节点的左节点
    5.  
    6. 	// 如果当前节点的左节点为空说明是h为0的情况
    7. 	// 不为空时就要进行节点间的连接
    8. 	if (curleft)
    9. 	{
    10. 		curleft->_parent = parent;
    11. 	}
    12.  
    13. 	parent->_right = curleft;
    14. 	cur->_left = parent;
    15.  
    16. 	// 此时需要确定parent是否属于子树
    17. 	if (parent == _root)
    18. 	{
    19. 		_root = cur;
    20. 		cur->_parent = nullptr;
    21. 	}
    22. 	else // 此时parent以下的节点属于子树
    23. 	{
    24. 		cur->_parent = parent->_parent;
    25.  
    26. 		// 确认parent与其父节点间的关系
    27. 		// 然后将cur与parent的父节点连接起来
    28. 		if (parent->_parent->_left == parent)
    29. 		{
    30. 			parent->_parent->_left = cur;
    31. 		}
    32. 		else
    33. 		{
    34. 			parent->_parent->_right = cur;
    35. 		}
    36. 	}
    37. 	parent->_parent = cur;
    38.  
    39. 	// 在进行左单旋后，当前节点与父节点的平衡因子均变为0
    40. 	cur->_bf = parent->_bf = 0;
    41. }

    ⑶双旋（右左旋）

    此情况适用于新节点插入较高左子树的右侧，抽象图如下

    在此我们先以左边的插入情况举例

    当h==0时，示例图如下

    当h==1时，示例图如下

    接下来推广到一般，示例图如下

    接下来再让我们看看右边的情况

    当h==0时，示例图如下

    当h==1时，示例图如下

    接下来推广到一般，示例图如下

    结合上述几幅图像来看，从结果上来看，最终的结果是15节点的右边赋给了20节点的左边，15节点的左边边赋给了10节点的右边；此外，对于平衡因子来说，当h==0时，三个节点的平衡因子均被更新为0，而h!=0时，三个节点的平衡因子分为2种情况，当插入在15节点的左边时，三个节点的平衡因子分别被更新为0,0,1，当插入在15节点的右边时，三个节点的平衡因子分别被更新为0,0,-1。通过复用左单旋与右单旋的代码可以得到如下代码

    1. void RotateRL(Node* parent)
    2. {
    3. 	Node* cur = parent->_right;
    4. 	Node* curleft = cur->_left;
    5. 	int bf = curleft->_bf;
    6. 	RotateR(cur);
    7. 	RotateL(parent);
    8.  
    9. 	if (bf == 0) // h==0的情况
    10. 	{
    11. 		parent->_bf = 0;
    12. 		cur->_bf = 0;
    13. 		curleft->_bf = 0;
    14. 	}
    15. 	else if (bf == 1) //新节点插入到右侧的情况
    16. 	{
    17. 		parent->_bf = -1;
    18. 		cur->_bf = 0;
    19. 		curleft->_bf = 0;
    20. 	}
    21. 	else if (bf == -1)//新节点插入到左侧的情况
    22. 	{
    23. 		cur->_bf = 1;
    24. 		parent->_bf = 0;
    25. 		curleft->_bf = 0;
    26. 	}
    27. 	else // 出现其他情况时报错
    28. 	{
    29. 		assert();
    30. 	}
    31. }

    ⑷双旋（左右旋）

    此情况适用于新节点插入较高左子树的右侧，具体抽象图如下

    这里与上面的右左旋大同小异，因此在这里只画出两种情况的一般示例图与h==0的示例图

    当h==0时，示例图如下

    当新节点插入在7的左侧时，一般示例图如下

    当新节点插入在7的右侧时，一般示例图如下

    根据结果我们发现它的结果与右左旋类似，因此我们只需对代码作一定的修改即可，代码如下

    1. void RotateLR(Node* parent)
    2. {
    3. 	Node* cur = parent->_left;
    4. 	Node* curright = cur->_right;
    5. 	int bf = curright->_bf;
    6. 	RotateL(cur);
    7. 	RotateR(parent);
    8.  
    9. 	if (bf == 0) // h==0的情况
    10. 	{
    11. 		parent->_bf = 0;
    12. 		cur->_bf = 0;
    13. 		curright->_bf = 0;
    14. 	}
    15. 	else if (bf == 1) //新节点插入到右侧的情况
    16. 	{
    17. 		parent->_bf = 0;
    18. 		cur->_bf = -1;
    19. 		curleft->_bf = 0;
    20. 	}
    21. 	else if (bf == -1)//新节点插入到左侧的情况
    22. 	{
    23. 		cur->_bf = 0;
    24. 		parent->_bf = 1;
    25. 		curleft->_bf = 0;
    26. 	}
    27. 	else // 出现其他情况时报错
    28. 	{
    29. 		assert();
    30. 	}
    31. }

    ⑸完整的插入代码

    1. bool Insert(const pair& kv)
    2. {
    3. 	if (_root == nullptr)
    4. 	{
    5. 		_root = new Node(kv);
    6. 		return true;
    7. 	}
    8.  
    9. 	Node* cur = _root;
    10. 	Node* parent = nullptr;
    11. 	// 寻找要插入的位置
    12. 	while (cur)
    13. 	{
    14. 		if (kv.first < cur->_kv.first)
    15. 		{
    16. 			parent = cur;
    17. 			cur = cur->_left;
    18. 		}
    19. 		else if (kv.first > cur->_kv.first)
    20. 		{
    21. 			parent = cur;
    22. 			cur = cur->_right;
    23. 		}
    24. 		else
    25. 		{
    26. 			return false;
    27. 		}
    28. 	}
    29.  
    30. 	// 到此处cur已经指向了应该插入的位置，
    31. 	// 然后判断应该插入到parent的哪边
    32. 	cur = new Node(kv);
    33. 	if (kv.first > cur->_kv.first)
    34. 	{
    35. 		parent->_right = cur;
    36. 	}
    37. 	else
    38. 	{
    39. 		parent->_left = cur;
    40. 	}
    41. 	cur->_parent = parent;
    42.  
    43. 	// 插入完成后要更改平衡因子
    44. 	// 从父节点向上更新一直更新到平衡因子为0(已平衡)
    45. 	// 或者更新到平衡因子为2或-2(已失衡)
    46. 	// 或者更新到根节点的父节点为止
    47. 	while (parent)
    48. 	{
    49. 		if (cur == parent->_left)
    50. 			parent->_bf--;
    51. 		else
    52. 			parent->_bf++;
    53.  
    54. 		if (parent->_bf == 0)
    55. 		{
    56. 			break;
    57. 		}
    58. 		else if (parent->_bf == -1 || parent->_bf == 1)
    59. 		{
    60. 			cur = parent;
    61. 			parent = parent->_parent;
    62. 		}
    63. 		else if (parent->_bf == 2 || parent->_bf == -2)
    64. 		{
    65. 			// 此时当前节点已失衡，需要通过旋转来调整
    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. 				RotateRL(parent);
    77. 			}
    78. 			else if (parent->_bf == -2 && cur->_bf == 1)
    79. 			{
    80. 				RotateLR(parent);
    81. 			}
    82. 				
    83. 			// 插入完成后结束插入
    84. 			break;
    85. 		}
    86. 		else
    87. 		{
    88. 			assert();
    89. 		}
    90. 	}
    91.  
    92. 	return true;
    93. }

    3.AVL树的性能分析

            AVL树是一种绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1。这样的平衡条件使得AVL树在查询时的性能高效且稳定。在AVL树中，任何节点的两个子树的高度差都不超过1，因此，在执行查询操作时，最坏的情况就是需要遍历log(N)层节点，其中N是树中节点的数量，因此查询效率非常高。

            然而，如果需要对AVL树进行结构修改操作，比如插入或删除节点，维持其绝对平衡性的同时会导致性能降低。在插入节点时，需要维护其平衡性，这可能会导致旋转的次数增加。在最差的情况下，旋转次数可能达到O(log(N))，这会显著影响到插入操作的性能。

            在删除节点时，可能需要执行多次旋转操作来重新平衡树。在最差的情况下，删除操作可能需要O(log(N))的时间复杂度，因为需要一直旋转到根节点。因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树。然而，如果数据经常需要修改，那么AVL树可能就不是最佳选择了。

            总的来说，AVL树在查询性能上表现出色，但如果需要经常进行结构修改操作，其性能就可能会变得较差。

  • 相关阅读:
    更智能！AIRIOT加速煤炭行业节能减排升级
    详解synchronize关键字
    记录：c++生成json
    应该选择网络安全还是程序员？
    【编程之路】面试必刷TOP101：动态规划（72-77，Python实现）
    #gStore-weekly | gStore源码解析（四）：安全机制之黑白名单配置解析
    【每日一题】689. 三个无重叠子数组的最大和-2023.11.19
    ITIL-4关键词汇总
    【系统架构设计】架构核心知识： 3.7 大型网站系统架构演化
    大数据下一代变革之必研究数据湖技术Hudi原理实战双管齐下-后续
  • 原文地址：https://blog.csdn.net/qq_73201597/article/details/132889375