• AVL树的插入--旋转笔记

    目录

    AVL树

    性质

    实现

    结点构造

    左单旋

    代码实现、有注释说明：

    右单旋 

    代码实现，有注释说明

    左右双旋

    1. 孙字辈的平衡因子为 0

    2. 孙字辈的平衡因子为 1

    3.  孙字辈的平衡因子为 -1

    代码实现

    右左双旋

    1. 孙字辈的平衡因子为 0

    2. 孙字辈的平衡因子为 1

    3.  孙字辈的平衡因子为 -1

    代码实现

    插入的实现

    代码实现--有相应细节注释说明

     

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

    AVL树

    AVL树是解决上述问题的方法之一：

    当向二叉搜索树插入新结点后，通过对树中的结点进行调整，保证每个结点的左右子树高度之差的绝对值不超过1，即可降低树的高度，从而减少平均搜索长度。

    性质

    左右子树都是AVL树
    左右子树高度之差(简称平衡因子)的绝对值不超过1
    如果它有N个结点，其高度可保持在 log2N，搜索时间复杂度O(log2N)

    相比较于搜索二叉树，我们在实现 AVL 树时，用到了三叉连，每个结点除了左右指针，还有指向父亲结点的指针，还加入了平衡因子，方便判断和及时调整（旋转）

    实现

    结点构造

    1. template<class k,class v>
    2.  
    3. //定义结点 ---三叉链，涉及到回溯问题
    4. struct AVLTreeNode
    5. {
    6. 	pair _kv;
    7. 	AVLTreeNode* _left;
    8. 	AVLTreeNode* _right;
    9. 	AVLTreeNode* _parent;
    10. 	
    11. 	int _bf;     //平衡因子--右子树-左子树的高度差
    12.  
    13. 	AVLTreeNode(const pair& kv)
    14. 		:_kv(kv)
    15. 		, _left(nullptr)
    16. 		, _right(nullptr)
    17. 		, _parent(nullptr)
    18. 		,_bf(0)
    19. 	{}
    20. };

    在AVL树中，我们最需要搞明白的就是插入结点时，是怎么样保证左右高度差不超过 1 的？通过旋转来对树左右高度进行控制

    左边高，向右旋转：右单旋

    右边高，向左旋转：左单旋

    左单旋

    那么什么时候会进行左单旋呢？

    当父亲结点平衡因子为 2 ，且其右子树结点平衡因子为 1

    这颗树就不符合AVL树的规则，需要进行旋转，左单旋是右边高，向左进行旋转：

    旋转很简单，但是每个结点都有三个指针，之间的关系很复杂，且还要考虑各种情况，上述是 subRL 为空的情况，且parent为根的情况。最后更新平衡因子，三个结点都为 0

    代码实现、有注释说明：

    1. //左单旋
    2. 	void RotateL(Node* parent)
    3. 	{
    4. 		Node* subR = parent->_right;
    5. 		Node* subRL = subR->_left;
    6.  
    7. 		parent->_right = subRL;
    8. 		if (subRL)
    9. 			subRL->_parent = parent;       //当 subRL 不为空时，要注意结点父亲要更新
    10.  
    11. 		Node* ppNode = parent->_parent;    //先保留父亲的父亲，以防父亲不是根节点
    12.  
    13. 		subR->_left = parent;
    14. 		parent->_parent = subR;         //注意父亲结点的父亲也要更新
    15.  
    16. 		if (parent == _root)         //父亲为根，
    17. 		{
    18. 			_root = subR;            //更新根
    19. 			_root->_parent = nullptr;  //根的父亲直接为空
    20. 		}
    21. 		else                            //如果父亲不为根，是上面其他结点的一个子树
    22. 		{
    23. 			if (parent == ppNode->_left)  //判断是左子树
    24. 			{
    25. 				ppNode->_left = subR;      //保留的结点起作用，保留的结点的指向更新
    26. 			}
    27. 			else
    28. 			{
    29. 				ppNode->_right = subR;   判断是右子树
    30. 			}
    31.  
    32. 			subR->_parent = ppNode;      //subR的父亲为保留的结点
    33. 		}
    34.  
    35. 		subR->_bf = parent->_bf = 0;    //最后平衡因子根据图更新
    36. 	}

    右单旋 

    什么时候会进行右单旋呢？

    AVL树的插入删除遍历等操作
    application/x-rar 5星 超过95%的资源 3KB
    下载

    当父亲结点平衡因子为 -2 ，且其左子树结点平衡因子为 -1

    这颗树就不符合AVL树的规则，需要进行旋转，右单旋是左边高，向右进行旋转：

    上述是 subLR 不为空，parent 为根的情况，旋转和平衡因子的更新如上图所示；

    无论是左单旋还是右单旋，最后平衡因子的更新是发生在 parent 和 它的孩子结点上，都为 0 

    代码实现，有注释说明

    1. //右单旋
    2. 	void 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* ppNode = parent->_parent;  //保存父亲的父亲，防止父亲不是根节点，后面需要更新
    12.  
    13. 		subL->_right = parent;         //如图，改变指向
    14. 		parent->_parent = subL;
    15.  
    16. 		if (parent == _root)        //如果父亲就是根节点
    17. 		{
    18. 			_root = subL;
    19. 			_root->_parent = nullptr;   //更新根节点，根节点指向空
    20. 		}
    21. 		else                            //不为根，那么就是上层结点的子树
    22. 		{
    23. 			if (parent == ppNode->_left)     //判断为左子树
    24. 			{
    25. 				ppNode->_left = subL;      //将上层结点的左指向我们的subL
    26. 			}
    27. 			else
    28. 			{  
    29. 				ppNode->_right = subL;    //判断为右子树，更新上层结点的右子树指向
    30. 			}
    31.  
    32. 			subL->_parent = ppNode;       //新根subL的父亲指向上层结点
    33. 		}
    34.  
    35. 		subL->_bf = parent->_bf = 0;     //最后更新原父亲和其孩子的平衡因子
    36. 	}

    无论是左单旋还是右单旋，都是一边高的情况；

    对于一个父亲节点来说，也会出现：

    左子树高，左子树无左树有右树

    右子树高，右子树无右树有左树

    单旋并不能解决上述情况

    这就是要处理的双旋转问题

    单旋就处理不了吗？对的，处理不了，如下所示：

    每种双旋转的大情况都有三种，涉及到平衡因子的更新，在此直接揭晓：

    平衡因子的更新，取决于孩子的孩子 (孙字辈) 的平衡因子

    左右双旋

    什么时候会进行左右双旋呢？

    当父亲结点平衡因子为 -2 ，且其左子树结点平衡因子为 1

    1. 孙字辈的平衡因子为 0

    左右双旋之后，可以看到三个结点的平衡因子都是 0

    2. 孙字辈的平衡因子为 1

    左右双旋之后，parent 和 subLR 平衡因子为 0 ，subL的平衡因子为  -1

    3.  孙字辈的平衡因子为 -1

    avl树的删除、插入、平衡化旋转算法实现
    application/x-rar 5星 超过95%的资源 8KB
    下载

    左右双旋之后，subL 和 subLR 平衡因子为 0 ，parent的平衡因子为  1

    代码实现

    1. 	//左右双旋
    2. 	void RotateLR(Node* parent)
    3. 	{
    4. 		//记录
    5. 		Node* subL = parent->_left;
    6. 		Node* subLR = subL->_right;
    7. 		int bf = subLR->_bf;
    8.  
    9. 		RotateL(parent->_left);
    10. 		RotateR(parent);     //平衡因子被全部调零，更新平衡因子
    11.  
    12. 		if (bf == 0)           //根据孙字辈的结点平衡因子，对照图进行更新
    13. 		{
    14. 			parent->_bf = 0;
    15. 			subL->_bf = 0;
    16. 			subLR->_bf = 0;
    17. 		}
    18. 		else if (bf == 1)
    19. 		{
    20. 			parent->_bf = 0;
    21. 			subL->_bf = -1;
    22. 			subLR->_bf = 0;
    23. 		}
    24. 		else if (bf == -1)
    25. 		{
    26. 			parent->_bf = 1;
    27. 			subL->_bf = 0;
    28. 			subLR->_bf = 0;
    29. 		}
    30. 		else
    31. 		{
    32. 			//旋转前就有问题
    33. 			assert(false);
    34. 		}
    35. 	}

    右左双旋

    什么时候会进行右左双旋呢？

    当父亲结点平衡因子为 2 ，且其右子树结点平衡因子为 -1

    于左右双旋道理相同，先右单旋，再左单旋，有三种情况：

    1. 孙字辈的平衡因子为 0

    如图示，右左双旋后，三个结点的平衡因子全部更新为 0

    2. 孙字辈的平衡因子为 1

    右左双旋之后，subR 和 subRL 平衡因子为 0 ，parent的平衡因子为  -1

    3.  孙字辈的平衡因子为 -1

    右左双旋之后，parent 和 subRL 平衡因子为 0 ，subR的平衡因子为  1

    代码实现

    1. //右左双旋
    2. 	void RotateRL(Node* parent)
    3. 	{
    4. 		//记录
    5. 		Node* subR = parent->_right;
    6. 		Node* subRL = subR->_left;
    7. 		int bf = subRL->_bf;          //记录孙字辈结点的平衡因子
    8.  
    9. 		RotateR(parent->_right);      //根据上述分析，对相应结点进行旋转
    10. 		RotateL(parent);
    11.  
    12. 		if (bf == 0)                //根据孙字辈结点的平衡因子，进行更新
    13. 		{
    14. 			parent->_bf = 0;
    15. 			subR->_bf = 0;
    16. 			subRL->_bf = 0;
    17. 		}
    18. 		else if (bf == 1)
    19. 		{
    20. 			parent->_bf = -1;
    21. 			subR->_bf = 0;
    22. 			subRL->_bf = 0;
    23. 		}
    24. 		else if (bf == -1)
    25. 		{
    26. 			parent->_bf = 0;
    27. 			subR->_bf = 1;
    28. 			subRL->_bf = 0;
    29. 		}
    30. 		else
    31. 		{
    32. 			//旋转前就有问题
    33. 			assert(false);
    34. 		}
    35. 	}

    插入的实现

    AVL树的插入规则遵循搜索二叉树的插入规则，比结点大的插入在右边，比结点小的插入在左边，要插入，就应该先找到要插入的位置 

    代码实现--有相应细节注释说明

    1. 	//插入
    2. 	bool Insert(const pair& kv)
    3. 	{
    4. 		//1. 按照搜索树的规则插入
    5. 		//2. 看是否违反平衡规则，违反则旋转
    6.  
    7. 		//空树时
    8. 		if (_root == nullptr)
    9. 		{
    10. 			_root = new Node(kv);
    11. 			return true;
    12. 		}
    13.  
    14. 		//找到插入位置
    15. 		Node* parent = nullptr;
    16. 		Node* cur = _root;
    17. 		while (cur)
    18. 		{
    19. 			if (cur->_kv.first < kv.first)
    20. 			{
    21. 				parent = cur;
    22. 				cur = cur->_right;
    23. 			}
    24. 			else if (cur->_kv.first > kv.first)
    25. 			{
    26. 				parent = cur;
    27. 				cur = cur->_left;
    28. 			}
    29. 			else
    30. 			{
    31. 				return false;
    32. 			}
    33. 		}
    34. 		cur = new Node(kv);                //找到结点，创建结点，链接结点
    35. 		if (parent->_kv.first < kv.first)
    36. 		{
    37. 			parent->_right = cur;
    38. 		}
    39. 		else
    40. 		{
    41. 			parent->_left = cur;
    42. 		}
    43.  
    44. 		cur->_parent = parent;  //注意结点的更新
    45.  
    46. 		// 已经将结点插入了，现在判断平衡因子--不影响另一颗子树，只会影响祖先
    47.         //   （新增在父亲右，父亲平衡因子++，新增在左父亲平衡因子--）
    48. 		//子树高度变了继续往上更新，高度不变停止更新
    49. 		//没有违反规则，结束，违反规则--旋转处理
    50.  
    51. 		while (parent) //依次往上更新，最坏情况下最远更新到根
    52. 		{
    53. 			if (cur==parent->_right)
    54. 			{
    55. 				parent->_bf++;
    56. 			}
    57. 			else
    58. 			{
    59. 				parent->_bf--;
    60. 			}
    61. 			//是否继续更
    62. 			if (parent->_bf == 0)
    63. 			{
    64. 				break;  //高度不变
    65. 			}
    66. 			else if (parent->_bf == 1 || parent->_bf == -1)
    67. 			{
    68. 				//子树高度变了，继续网上更新祖先
    69. 				cur = cur->_parent;
    70. 				parent = parent->_parent;
    71. 			}
    72. 			else if (parent->_bf == 2 || parent->_bf == -2)
    73. 			{
    74. 				//子树不平衡旋转
    75. 				if (parent->_bf == 2 && cur->_bf == 1)  //左单旋
    76. 				{
    77. 					RotateL(parent);
    78. 				}
    79. 				else if (parent->_bf == -2 && cur->_bf == -1)  //右单旋
    80. 				{
    81. 					RotateR(parent);
    82. 				}
    83. 				else if (parent->_bf == -2 && cur->_bf == 1)   //左右双旋
    84. 				{
    85. 					RotateLR(parent);
    86. 				}
    87. 				else if (parent->_bf == 2 && cur->_bf == -1)   //右左双旋
    88. 				{
    89. 					RotateRL(parent);
    90. 				}
    91.  
    92. 				break;
    93. 			}
    94. 			else
    95. 			{
    96. 				//插入之前AVL就不平衡了
    97. 				assert(false);
    98. 			}
    99. 		}
    100.  
    101. 		return true;
    102.  
    103. 	}

     

  • 相关阅读:
    Mysql在项目中相关使用(简单操作数据库)
    多项式加法_C语言
    基于STM32+NBIOT(BC26)设计的物联网观赏鱼缸
    图片怎么批量重命名从1到50？
    10474 - Where is the Marble? （UVA）
    使用Vue实现弹窗效果
    Java中快速掌握正则表达式
    脑机接口的发展研究
    div内文字水平居中+垂直居中
    【Dotnet 工具箱】基于 .NET 6 和 Angular 构建项目任务管理平台
  • 原文地址：https://blog.csdn.net/weixin_53316121/article/details/126167732