• AVL树详解+模拟实现

    目录

    1.AVL树的概念

    2.树的结点定义

    3.AVL树的插入  

    4.AVL树的旋转

    5.AVL树的验证

    6.AVL树的查找

    7.AVL树的性能

    1.AVL树的概念

    ①二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的。

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

    ③AVL树可以是一棵空树，也可以是具有以下性质的一棵二叉搜索树：

    • 树的左右子树都是AVL树。
    • 树的左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/1)

                             

    ④如果一棵二叉搜索树的高度是平衡的，它就是AVL树。如果它有n个结点，其高度可保持在)O(logN)，搜索时间复杂度也是O(logN)。

    ⑤注意： 这里所说的二叉搜索树的高度是平衡的是指，树中每个结点左右子树高度之差的绝对值不超过1，因为只有满二叉树才能做到每个结点左右子树高度之差均为0。
     

                                    

    2.树的结点定义

    • 我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。

    • 给每个结点增加平衡因子并不是必须的，只是实现AVL树的一种方式，不引入平衡因子也可以实现AVL树，只不过会麻烦一点。

    1. template<class K, class V>
    2. struct AVLTreeNode
    3. {
    4. 	//三叉链
    5. 	AVLTreeNode* _left;
    6. 	AVLTreeNode* _right;
    7. 	AVLTreeNode* _parent;
    8.  
    9. 	//存储的键值对
    10. 	pair _kv;
    11.  
    12. 	//平衡因子(balance factor)
    13. 	int _bf; //右子树高度-左子树高度，我们只是这样规定的
    14.  
    15. 	//构造函数
    16. 	AVLTreeNode(const pair& kv)
    17. 		:_left(nullptr)
    18. 		, _right(nullptr)
    19. 		, _parent(nullptr)
    20. 		, _kv(kv)
    21. 		, _bf(0)
    22. 	{}
    23. };

                    

                    

    3.AVL树的插入  

    (1)AVL树插入结点时有以下三个步骤：

    • 按照二叉搜索树的插入方法，找到待插入位置。
    • 找到待插入位置后，将待插入结点插入到树中。
    • 更新平衡因子，如果出现不平衡，则需要进行旋转。

                     

    (2)平衡因子

    • 与二叉搜索树插入结点不同的是，AVL树插入结点后需要更新树中结点的平衡因子，因为插入新结点后可能会影响树中某些结点的平衡因子。
    • 由于一个结点的平衡因子是否需要更新，是取决于该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的祖先结点的平衡因子可能需要更新。

                    

    ①所以我们插入结点后需要倒着往上更新平衡因子，更新规则如下：

    • 新增结点在parent的右边，parent的平衡因子 ++。
    • 新增结点在parent的左边，parent的平衡因子 −−。


    ②每更新完一个结点的平衡因子后，都需要进行以下判断：

    • 如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子。
    • 如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了。
    • 如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理。
       

    ③判断理由

    • -1或1 ： 只有0经过−−/++ 操作后会变成-1/1，说明新结点的插入使得parent的左子树或右子树增高了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子。
    • 0  ：  只有-1/1经过++/−− 操作后会变成0，说明新结点插入到了parent左右子树当中高度较矮的一棵子树，插入后使得parent左右子树的高度相等了，此操作并没有改变以parent为根结点的子树的高度，从而不会影响parent的父结点的平衡因子，因此无需继续往上更新平衡因子。
    • -2或2  ：此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理。
       

    ④注意

    •  parent的平衡因子在更新前只可能是-1/0/1（AVL树中每个结点的左右子树高度之差的绝对值不超过1）。
    • 而在最坏情况下，我们更新平衡因子时会一路更新到根结点。

    ⑤说明

    • 由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新。
    • 当然，我们也可以不用三叉链结构，可以在插入结点时将路径上的结点存储到一个栈当中，当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子，但是相对较麻烦。
    • 当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。 
    • 若是在更新平衡因子的过程当中，出现了平衡因子为-2/2的结点，这时我们需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种
    1. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
    2. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
    3. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。
    4. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。
    • 并且，在进行旋转处理后就无需继续往上更新平衡因子了，因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了。 

                    

    ⑥我们将插入结点称为cur，将其父结点称为parent，那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，那么我们必定要执行以下逻辑：

    1. cur = parent;
    2. parent = parent->_parent;

                     

    ⑦代码

    1. //插入函数
    2. bool Insert(const pair& kv)
    3. {
    4. 	if (_root == nullptr) //若AVL树为空树，则插入结点直接作为根结点
    5. 	{
    6. 		_root = new Node(kv);
    7. 		return true;
    8. 	}
    9.  
    10. 	//1、按照二叉搜索树的插入方法，找到待插入位置
    11. 	Node* cur = _root;
    12. 	Node* parent = nullptr;
    13. 	while (cur)
    14. 	{
    15. 		if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
    16. 		{
    17. 			//往该结点的左子树走
    18. 			parent = cur;
    19. 			cur = cur->_left;
    20. 		}
    21. 		else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
    22. 		{
    23. 			//往该结点的右子树走
    24. 			parent = cur;
    25. 			cur = cur->_right;
    26. 		}
    27. 		else //待插入结点的key值等于当前结点的key值
    28. 		{
    29. 			//插入失败（不允许key值冗余）
    30. 			return false;
    31. 		}
    32. 	}
    33.  
    34. 	//2、将待插入结点插入到树中
    35. 	cur = new Node(kv); //根据所给值构造一个新结点
    36. 	if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
    37. 	{
    38. 		//插入到parent的左边
    39. 		parent->_left = cur;
    40. 		cur->_parent = parent;
    41. 	}
    42. 	else //新结点的key值大于parent的key值
    43. 	{
    44. 		//插入到parent的右边
    45. 		parent->_right = cur;
    46. 		cur->_parent = parent;
    47. 	}
    48.  
    49. 	//3、更新平衡因子，如果出现不平衡，则需要进行旋转
    50. 	while (cur != _root) //最坏一路更新到根结点
    51. 	{
    52. 		if (cur == parent->_left) //parent的左子树增高
    53. 		{
    54. 			parent->_bf--; //parent的平衡因子--
    55. 		}
    56. 		else if (cur == parent->_right) //parent的右子树增高
    57. 		{
    58. 			parent->_bf++; //parent的平衡因子++
    59. 		}
    60.  
    61. 		//判断是否更新结束或需要进行旋转
    62. 		if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
    63. 		{
    64. 			break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
    65. 		}
    66. 		else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子
    67. 		{
    68. 			//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
    69. 			cur = parent;
    70. 			parent = parent->_parent;
    71. 		}
    72. 		else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了）
    73. 		{
    74. 			if (parent->_bf == -2)
    75. 			{
    76. 				if (cur->_bf == -1)
    77. 				{
    78. 					RotateR(parent); //右单旋
    79. 				}
    80. 				else //cur->_bf == 1
    81. 				{
    82. 					RotateLR(parent); //左右双旋
    83. 				}
    84. 			}
    85. 			else //parent->_bf == 2
    86. 			{
    87. 				if (cur->_bf == -1)
    88. 				{
    89. 					RotateRL(parent); //右左双旋
    90. 				}
    91. 				else //cur->_bf == 1
    92. 				{
    93. 					RotateL(parent); //左单旋
    94. 				}
    95. 			}
    96.  
    97. 			break; //旋转后就一定平衡了，无需继续往上更新平衡因子(旋转后树高度变为插入之前了)
    98. 		}
    99. 		else
    100. 		{
    101. 			assert(false); //在插入前树的平衡因子就有问题
    102. 		}
    103. 	}
    104.  
    105. 	return true; //插入成功
    106. }

                    

                    

    4.AVL树的旋转

    (1)左单旋

                    

     ①左单旋步骤

    1. 让subR的左子树作为parent的右子树。
    2. 让parent作为subR的左子树。
    3. 让subR作为整个子树的根。
    4. 更新平衡因子。

    ②左单旋后满足二叉搜索树的性质：

    1. subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。
    2. parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。

                     

    ③代码 ：结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向。

    1. //左单旋
    2. void RotateL(Node* parent)
    3. {
    4. 	Node* subR = parent->_right;
    5. 	Node* subRL = subR->_left;
    6. 	
    7.  
    8. 	//1、建立parent和subRL之间的关系
    9. 	parent->_right = subRL;
    10. 	if (subRL) //subRL可能为空
    11. 		subRL->_parent = parent;
    12.     
    13.     //2.记录pparent
    14.     Node* pparent = parent->_parent;
    15.    
    16.     //3.建立parent和subR的关系
    17.     subR->_left = parent;
    18.     parent->_parent = subR;
    19.  
    20. 	//4.建立pparent和subR的关系
    21. 	if (pparent == nullptr) //parent为根，是一颗单独的树
    22. 	{
    23. 		_root = subR;
    24. 		subR->_parent = nullptr; //subR的_parent指向需改变
    25. 	}
    26. 	else
    27. 	{
    28. 		if (parent == pparent->_left)
    29. 		{
    30. 			pparent->_left = subR;
    31. 		}
    32. 		else //parent == pparent->_right
    33. 		{
    34. 			pparent->_right = subR;
    35. 		}
    36.  
    37. 		subR->_parent = pparent;
    38. 	}
    39.  
    40. 	//5、更新平衡因子
    41. 	subR->_bf = parent->_bf = 0;
    42. }

            

    (2)右单旋

            

    ①右单旋的步骤如下：

    1. 让subL的右子树作为parent的左子树。
    2. 让parent作为subL的右子树。
    3. 让subL作为整个子树的根。
    4. 更新平衡因子。

    ②右单旋后满足二叉搜索树的性质：

    • subL的右子树当中结点的值本身就比parent的值小，因此可以作为parent的左子树。
    • parent及其右子树当中结点的值本身就比subL的值大，因此可以作为subL的右子树。

                     

    ③代码 : 结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向。

    1.     void RotateR(Node* parent)
    2. 	{
    3.  
    4.         
    5. 		Node* subL = parent->_left;
    6. 		Node* subLR = subL->_right;
    7.  
    8.         //1.建立parent和subLR的关系
    9. 		parent->_left = subLR;           
    10. 		if (subLR) //subLR可能为空
    11. 		{
    12. 			subLR->_parent = parent;
    13. 		}
    14. 		
    15.         //2.记录pparent
    16. 		Node* pparent = parent->_parent;
    17.        
    18.         //3.建立subL和parent的关系
    19. 		subL->_right = parent;             
    20. 		parent->_parent = subL;
    21.  
    22.         
    23.         //4.建立pparen和subL的关系
    24. 		if (parent == _root) //parent是一颗独立的树      
    25. 		{
    26. 			_root = subL;
    27. 			_root->_parent = nullptr;
    28. 		}
    29. 		else //parent是一颗子树，
    30. 		{
    31. 			if (pparent->_left == parent)
    32. 			{
    33. 				pparent->_left = subL;
    34. 			}
    35. 			else
    36. 			{
    37. 				pparent->_right = subL;
    38. 			}
    39.             subL->_parent = pparent; //改subL的parent
    40. 		}
    41.  
    42.         //5.更新平衡因子
    43. 		subL->_bf = parent->_bf = 0; //更新平衡因子
    44.  
    45. 	}

                            

    (3)左右双旋

                     

    ①左右双旋的步骤如下：

    • 以subL为旋转点进行左单旋
    • 以parent为旋转点进行右单旋
    • 更新平衡因子

    ②左右双旋后满足二叉搜索树的性质：

    左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根（结合图理解）。

    • subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
    • subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
    • 经过左单旋后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树。

                     

    ③左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

    • 1. 当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。 

                     

    • 2. 当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。

                             

    •  3. 当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。

     ④代码

    1.     void RotateLR(Node* parent)
    2. 	{
    3. 		Node* subL = parent->_left;
    4. 		Node* subLR = subL->_right;
    5.    
    6. 		int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1
    7.         
    8.         //1.以subL为旋转点进行左单旋
    9. 		RotateL(subL);
    10.  
    11.         //2.以parent为旋转点进行右单旋
    12. 		RotateR(parent);
    13.  
    14. 		//3.平衡因子的调节
    15. 		if (bf == -1)
    16. 		{
    17. 			subL->_bf = subLR->_bf = 0;
    18. 			parent->_bf = 1;
    19. 		}
    20. 		else if (bf == 1)
    21. 		{
    22. 			subLR->_bf = parent->_bf = 0;
    23. 			subL->_bf = -1;
    24. 		}
    25. 		else if (bf == 0)
    26. 		{
    27. 			subL->_bf = subLR->_bf = parent->_bf = 0;
    28. 		}
    29. 		else
    30. 		{
    31. 			assert(false);
    32. 		}
    33. 	}

                             

    (4)右左双旋

                     

    ①右左双旋的步骤如下：

    • 以subR为旋转点进行右单旋。
    • 以parent为旋转点进行左单旋。
    • 更新平衡因子。

    ②右左双旋后满足二叉搜索树的性质：

    右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根（结合图理解）。

    • subRL的左子树当中的结点本身就比parent的值大，因此可以作为parent的右子树。
    • subRL的右子树当中的结点本身就比subR的值小，因此可以作为subR的左子树。
    • 经过右单旋后，parent及其子树当中结点的值都就比subRL的值小，而subR及其子树当中结点的值都就比subRL的值大，因此它们可以分别作为subRL的左右子树。
       

    ③右左双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

    • 1.当subRL原始平衡因子是1时，左右双旋后parent、subR、subRL的平衡因子分别更新为-1、0、0。

                     

    • 2. 当subRL原始平衡因子是-1时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、1、0。

                     

    • 3. 当subRL原始平衡因子是0时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、0、0。 

                     

     ④代码

    1. 	void RotateRL(Node* parent)
    2. 	{
    3. 		Node* subR = parent->_right;
    4. 		Node* subRL = subR->_left;
    5.  
    6. 		int bf = subRL->_bf;
    7.         
    8.         //1.以subR为轴进行右旋
    9. 		RotateR(subR);
    10.  
    11.         //2.以parent为轴进行左旋
    12. 		RotateL(parent);
    13.         
    14.         //3.更新平衡因子
    15. 		if (bf == 1) 
    16. 		{
    17. 			subR->_bf = 0;
    18. 			parent->_bf = -1;
    19. 			subRL->_bf = 0;
    20. 		} 
    21. 		else if (bf == -1) 
    22. 		{
    23. 			parent->_bf = 0;
    24. 			subR->_bf = 1;
    25. 			subRL->_bf = 0;
    26. 		}
    27. 		else if (bf == 0) 
    28. 		{
    29. 			parent->_bf = subR->_bf = subRL->_bf = 0;
    30. 		}
    31. 		else
    32. 		{
    33. 			assert(false);
    34. 		}
    35. 	}

                    

                            

    5.AVL树的验证

    (1)验证是否是二叉搜索树

    • AVL树是在二叉搜索树的基础上加入了平衡性的限制，也就是说AVL树也是二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断二叉树是否为二叉搜索树
    • 但中序有序只能证明是二叉搜索树，要证明二叉树是AVL树还需验证二叉树的平衡性，在该过程中我们可以顺便检查每个结点当中平衡因子是否正确。 
    1. //中序遍历
    2. void Inorder()
    3. {
    4. 	_Inorder(_root);
    5. }
    6.  
    7. //中序遍历子函数
    8. void _Inorder(Node* root)
    9. {
    10. 	if (root == nullptr)
    11. 		return;
    12. 	_Inorder(root->_left);
    13. 	cout << root->_kv.first << " ";
    14. 	_Inorder(root->_right);
    15. }

                     

     (2)验证平衡因子

    • 从叶子结点处开始计算每课子树的高度。（每棵子树的高度 = 左右子树中高度的较大值 + 1）
    • 先判断左子树是否是平衡二叉树。
    • 再判断右子树是否是平衡二叉树。
    • 若左右子树均为平衡二叉树，则返回当前子树的高度给上一层，继续判断上一层的子树是否是平衡二叉树，直到判断到根为止。（若判断过程中，某一棵子树不是平衡二叉树，则该树也就不是平衡二叉树了）

    1. //判断是否为AVL树
    2. bool IsAVLTree()
    3. {
    4. 	int hight = 0; //输出型参数
    5. 	return _IsBalanced(_root, hight);
    6. }
    7.  
    8. //检测二叉树是否平衡
    9. bool _IsBalanced(Node* root, int& hight)
    10. {
    11. 	if (root == nullptr) //空树是平衡二叉树
    12. 	{
    13. 		hight = 0; //空树的高度为0
    14. 		return true;
    15. 	}
    16.  
    17. 	//先判断左子树
    18. 	int leftHight = 0;
    19. 	if (_IsBalanced(root->_left, leftHight) == false)
    20. 		return false;
    21.  
    22. 	//再判断右子树
    23. 	int rightHight = 0;
    24. 	if (_IsBalanced(root->_right, rightHight) == false)
    25. 		return false;
    26.  
    27. 	//检查该结点的平衡因子
    28. 	if (rightHight - leftHight != root->_bf)
    29. 	{
    30. 		cout << "平衡因子设置异常：" << root->_kv.first << endl;
    31. 	}
    32.  
    33. 	//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
    34. 	hight = max(leftHight, rightHight) + 1;
    35. 	return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
    36. }

                            

                            

    6.AVL树的查找

    • 若树为空树，则查找失败，返回nullptr。
    • 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
    • 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
    • 若key值等于当前结点的值，则查找成功，返回对应结点。
    1. //查找函数
    2. Node* Find(const K& key)
    3. {
    4. 	Node* cur = _root;
    5. 	while (cur)
    6. 	{
    7. 		if (key < cur->_kv.first) //key值小于该结点的值
    8. 		{
    9. 			cur = cur->_left; //在该结点的左子树当中查找
    10. 		}
    11. 		else if (key > cur->_kv.first) //key值大于该结点的值
    12. 		{
    13. 			cur = cur->_right; //在该结点的右子树当中查找
    14. 		}
    15. 		else //找到了目标结点
    16. 		{
    17. 			return cur; //返回该结点
    18. 		}
    19. 	}
    20. 	return nullptr; //查找失败
    21. }

                                                     

    7.AVL树的性能

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

  • 相关阅读:
    【每周Java技术】2022.07.18 周一 ～ 07.24 周日
    深入浅出排序算法之直接插入排序（拓展：折半插入排序）
    Windows 下基于 MikTeX 的 Latex 环境配置小记
    SQL Server Management Studio (SSMS) 20.1 - 微软数据库管理工具
    聊一聊如何截获 C# 程序产生的日志
    【K8S】Kubernetes集群搭建流程详解
    网格切割算法
    2022年4月最新面经答案总结(Java基础、数据库、JVM、计网、计操、集合、多线程、Spring)持续更新
    组件中的那么属性作用
    云里雾里？云方案没有统一标准，业务结合实际情况才是应该着重考虑的
  • 原文地址：https://blog.csdn.net/m0_52169086/article/details/126625118