• 深入理解AVLTree【旋转控制平衡（单旋、双旋）】

    目录

    一.分部实现AVLTree

    1.树节点（3叉链）

    2.AVLTree成员

    3.插入（重点）

    左单旋：

    右单旋：

    左右双旋：

    右左双旋：

    4.判断该树是否为平衡二叉搜索树

    二.AVLTree实现代码

    前言：二叉树是数据结构的重要一部分，而作为平衡二叉搜索树的AVLTree和红黑树学习起来是比较难的，但是我们需要去了解它们的思路（在学习的过程中，我们最好通过画图去更深入的理解，然后根据自己的图来完成代码实现）

            在学习AVLTree之前建议先去学习一下set和map（了解KV模型，键值对等）

    set+map-》C++ 关联式容器map+set_糖果雨滴a的博客-CSDN博客

    红黑树-》深入理解 红黑树【满足红黑树5条规则】_糖果雨滴a的博客-CSDN博客

    一.分部实现AVLTree

    1.树节点（3叉链）

            实现一个含义3叉链的二叉树，并且包括pair类型的kv，以及为了方便控制平衡而设计出的平衡因子。

    1. template<class K, class V>
    2. struct AVLTreeNode
    3. {
    4. 	pair _kv;
    5. 	AVLTreeNode* _left;
    6. 	AVLTreeNode* _right;
    7. 	AVLTreeNode* _parent;
    8.  
    9. 	// 右子树-左子树的高度差
    10. 	int _bf;
    11.  
    12. 	AVLTreeNode(const pair& kv)
    13. 		: _kv(kv)
    14. 		, _left(nullptr)
    15. 		, _right(nullptr)
    16. 		, _parent(nullptr)
    17. 		, _bf(0)
    18. 	{}
    19.  
    20. 	// AVL树没有规定必须要设计平衡因子
    21. 	// 平衡因子只是一个实现的选择，方便控制平衡
    22. };

    2.AVLTree成员

            为了后面方便，typedef为Node，然后创建一个Node类型的根结点。 

    1. template<class K, class V>
    2. class AVLTree
    3. {
    4. 	typedef AVLTreeNode Node;
    5. private:
    6. 	Node* _root = nullptr;

    3.插入（重点）

    1. bool Insert(const pair& kv)
    2. 	{
    3. 		// 1.搜索树的规则插入
    4. 		// 2.看是否违反平衡规则，如果违反就需要处理：旋转
    5. 		if (_root == nullptr)
    6. 		{
    7. 			_root = new Node(kv);
    8. 			_root->_bf = 0;
    9. 			return true;
    10. 		}
    11. 		
    12. 		Node* parent = nullptr;
    13. 		Node* cur = _root;
    14. 		// 找到要插入的位置
    15. 		while (cur)
    16. 		{
    17. 			if (cur->_kv.first < kv.first)
    18. 			{
    19. 				parent = cur;
    20. 				cur = cur->_right;
    21. 			}
    22. 			else if (cur->_kv.first > kv.first)
    23. 			{
    24. 				parent = cur;
    25. 				cur = cur->_left;
    26. 			}
    27. 			else
    28. 			{
    29. 				return false;
    30. 			}
    31. 		}
    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. 		while (parent)
    49. 		{
    50. 			if (cur == parent->_right)
    51. 			{
    52. 				parent->_bf++;
    53. 			}
    54. 			else
    55. 			{
    56. 				parent->_bf--;
    57. 			}
    58.  
    59. 			// 判断是否要继续更新
    60. 			// 1 or -1 -》 0  插入的节点填上了矮的那边
    61. 			if (parent->_bf == 0)
    62. 			{
    63. 				// 高度不变，更新结束
    64. 				break;
    65. 			}
    66. 			// 0 -》 1 or -1  插入节点导致一边变高了
    67. 			else if (parent->_bf == 1 || parent->_bf == -1)
    68. 			{
    69. 				// 子树的高度变了，继续更新祖先
    70. 				cur = cur->_parent;
    71. 				parent = parent->_parent;
    72. 			}
    73. 			// 1 or -1 -》 2 or -2  插入节点导致本来高的一边又变高了
    74. 			else if (parent->_bf == 2 || parent->_bf == -2)
    75. 			{
    76. 				// 子树不平衡  --需要旋转处理
    77. 				// 左单旋
    78. 				if (parent->_bf == 2 && cur->_bf == 1)
    79. 				{
    80. 					RotateL(parent);
    81. 				}
    82. 				// 右单旋
    83. 				else if (parent->_bf == -2 && cur->_bf == -1)
    84. 				{
    85. 					RotateR(parent);
    86. 				}
    87. 				// 左右双旋
    88. 				else if (parent->_bf == -2 && cur->_bf == 1)
    89. 				{
    90. 					RotateLR(parent);
    91. 				}
    92. 				// 右左双旋
    93. 				else if (parent->_bf == 2 && cur->_bf == -1)
    94. 				{
    95. 					RotateRL(parent);
    96. 				}
    97. 				
    98. 				break;
    99. 			}
    100. 			else
    101. 			{
    102. 				// 插入之前AVL就存在不平衡子树（平衡因子的绝对值>= 2的节点）
    103. 				assert(false);
    104. 			}
    105. 		}
    106.  
    107. 		return true;
    108. 	}

            首先我们注意一下该树是否为空，为空就创建一个节点，把该点平衡因子变为0即可。

            然后因为是3叉链，所以我们要设置一个parent变量和一个cur变量。然后按照二叉搜索树的方法去找到要插入的位置（要插入的元素的first比cur大就往右走，比cur小就往左走），找到之后，new出该节点，然后插入，同时把该链接的都链接上。到这为止都很简单。

            接下来就是AVLTree的重点了：更新平衡因子。

            这里我们首先想想，如果插入了一个元素，那么该元素的parent的平衡因子一定会发生变化，那么parent的parent是否会变化呢？

            这个就不一定了，可能会变化也可能不会变化，需要我们去分情况讨论。而不是该插入元素的祖先节点一定不会发生变化，因此最多会变化到根节点，但不会影响另一边的子树。

            首先先更新该插入元素的parent的平衡因子，如果插入在右边，就++，如果插入在左边，就--，（这里我们设置右边节点多为正数+，左边节点多为负数-）。

            更新了parent节点后，就有继续判断是否要继续往上更新了。

            第一种情况：parent的平衡因子变成了0，那么说明插入的节点填上了矮的那边，高度没有发生变化，不会影响到上面的节点，因此不需要进行更新了，更新结束。

            第二种情况：parent的平衡因子变成了1或者-1，这时说明的插入的节点导致一边变高了，这时候高度变了，那么就需要继续更新祖先的平衡因子，因此我们让cur变成parent，parent变成parent的parent，这样就往上走了一个节点，然后因为整个平衡因子更新在一个while循环中，所以循环到下一个再次进行更新平衡因子。

            第三种情况：这种情况是AVLTree中最重要的地方，也是最难的地方。parent的平衡因子变成了2或者-2，这时说明插入的节点导致本来就高的一边又变高了，因此我们需要平衡该树（这里就需要进行旋转【旋转原则：①保持搜索树的规则 ②让子树变平衡】处理了）。这里我们一定要画图去理解。

            如果出现第四种情况，说明插入之前AVL树就不平衡，即实现的有错误，断言报错。

    左单旋：

            如果只根据语言描述，几乎不能去理解AVLTree的旋转，因此下面我们通过画图的方式来理解AVLTree的旋转操作。 

            根据树高度的不同，树的样子会有所不同。这个就简单看一下。

            这里因为树的高度不同，就可能会有很多种的画法，因此我们可以通过用下面这种可以代表所有情况的抽象图来进行旋转。

             

            这里为什么我们要在parent的上面画一个节点呢？

            因为我们不清楚parent是根还是整个子树的一个局部子树，因此我们要注意进行分情况讨论。

    接下来说一下左单旋的使用场景和操作：

            使用场景： 该cur节点的parent节点的平衡因子为2，cur节点的平衡因子为1时，这里图的样子大概就是一个向右的斜线。

            操作：我们将cur节点parent节点定义为parent，将该parent的右孩子节点定义为subR，将subR的左孩子节点定义为subRL。

            旋转方式：将subRL变为parent的右孩子节点，然后再左旋parent节点，让parent变为subR的左孩子节点。最后更新平衡因子。

            通过语言的描述，再结合上面图中的操作，我们就可以很好的理解左单旋了。

            接下来在通过代码实现来进一步理解左单旋：

    1. void RotateL(Node* parent)
    2. {
    3. 	Node* subR = parent->_right;
    4. 	Node* subRL = subR->_left;
    5.  
    6. 	Node* ppNode = parent->_parent;
    7.  
    8. 	parent->_right = subRL;
    9. 	parent->_parent = subR;
    10. 	if (subRL)
    11. 	{
    12. 		subRL->_parent = parent;
    13. 	}
    14. 	subR->_left = parent;
    15. 		
    16. 	if (parent == _root)
    17. 	{
    18. 		_root = subR;
    19. 		_root->_parent = nullptr;
    20. 	}
    21. 	else
    22. 	{
    23. 		if (ppNode->_left == parent)
    24. 		{
    25. 			ppNode->_left = subR;
    26. 		}
    27. 		else
    28. 		{
    29. 			ppNode->_right = subR;
    30. 		}
    31.  
    32. 		subR->_parent = ppNode;
    33. 	}
    34.  
    35. 	// 更新平衡因子
    36. 	subR->_bf = 0;
    37. 	parent->_bf = 0;
    38. }

            首先定义3个变量，一个是subR，一个是subRL，还有一个是ppNode，这个ppNode就是为了在旋转后，可以让旋转后的subR能连上上面的子树。

            然后把链接关系更改为旋转后的链接关系（这里要注意subRL可能是空）。

            再分情况讨论，第一种是parent就是根节点，这种情况直接让subR变成新的根节点，然后在把subR的parent置为空。第二种是parent不是根节点，这时就要看parent是ppNode的左还是右，是左就让ppNode的左变为subR，是右就让ppNode的右变为subR。

            最后根据画的图更新一下平衡因子即可。

    右单旋：

            右单旋与左单旋较为相似，我们看图来理解。

    右单旋的使用场景和操作：

            使用场景： 该cur节点的parent节点的平衡因子为-2，cur节点的平衡因子为-1时，这里图的样子大概就是一个向左的斜线。

            操作：我们将cur节点parent节点定义为parent，将该parent的左孩子节点定义为subL，将subL的右孩子节点定义为subLR。

            旋转方式：将subRL变为parent的左孩子节点，然后再右旋parent节点，让parent变为subL的右孩子节点。最后更新平衡因子。

            代码实现：

    1. void RotateR(Node* parent)
    2. {
    3. 	Node* subL = parent->_left;
    4. 	Node* subLR = subL->_right;
    5.  
    6. 	Node* ppNode = parent->_parent;
    7.  
    8. 	parent->_left = subLR;
    9. 	parent->_parent = subL;
    10.  
    11. 	if (subLR)
    12. 	{
    13. 		subLR->_parent = parent;
    14. 	}
    15. 	subL->_right = parent;
    16. 		
    17. 	if (parent == _root)
    18. 	{
    19. 		_root = subL;
    20. 		_root->_parent = nullptr;
    21. 	}
    22. 	else
    23. 	{
    24. 		if (parent == ppNode->_left)
    25. 		{
    26. 			ppNode->_left = subL;
    27. 		}
    28. 		else
    29. 		{
    30. 			ppNode->_right = subL;
    31. 		}
    32.  
    33. 		subL->_parent = ppNode;
    34. 	}
    35.  
    36. 	subL->_bf = 0;
    37. 	parent->_bf = 0;
    38. }

            实现方式也很类似左单旋，先定义变量，然后更改链接关系，接着分情况讨论parent是否为根节点，最后更新平衡因子。

    左右双旋：

            先简单看一下不同高度的发生左右双旋的样子。

             通过抽象图来实现左右双旋：

            根据上面的图，我们可以发现根据插入节点的位置不同，旋转出来的不同节点的平衡因子是不同的，因此双旋是需要分情况讨论的，当然这几种情况相同的都是先左旋parent->_left节点，再右旋parent节点，然后就要分情况去更新平衡因子了。（这里我们仔细观察，会发现subLR在3种情况都不同，因此我们可以根据subLR进行分情况）

            第一种情况（subLR为0）：这种情况是发生左右双旋的最低高度，旋转后parent、subL、subLR的平衡因子都为0。

            第二种情况（subLR为-1）：旋转后parent = 1，subL = 0，subLR = 0

            第三种情况（subLR为1）：旋转后parent = 0，subL = -1，subLR = 0

    左右单旋的使用场景和操作：

            使用场景： 该cur节点的parent节点的平衡因子为-2，cur节点的平衡因子为1时，这里图的样子大概就是一个先向左后向右的折线。

            操作：我们将cur节点parent节点定义为parent，将该parent的左孩子节点定义为subL，将subL的右孩子节点定义为subLR。

            旋转方式：先对parent->_left（subL）进行左旋，将subLR的左孩子节点变为subL的右孩子节点，再左旋subL节点，让subL变为subLR的左孩子节点。然后再对parent进行右旋，将subLR的右孩子节点变为parent的左孩子节点，再右旋parent节点，让parent变为subLR的右孩子节点。最后更新平衡因子

            代码实现：

    1. void RotateLR(Node* parent)
    2. {
    3. 	Node* subL = parent->_left;
    4. 	Node* subLR = subL->_right;
    5. 	int bf = subLR->_bf;
    6.  
    7. 	RotateL(parent->_left);
    8. 	RotateR(parent);
    9.  
    10. 	// 更新平衡因子(分三种情况)
    11. 	if (bf == 0)
    12. 	{
    13. 		parent->_bf = 0;
    14. 		subL->_bf = 0;
    15. 		subLR->_bf = 0;
    16. 	}
    17. 	else if (bf == 1)
    18. 	{
    19. 		parent->_bf = 0;
    20. 		subL->_bf = -1;
    21. 		subLR->_bf = 0;
    22. 	}
    23. 	else if (bf == -1)
    24. 	{
    25. 		parent->_bf = 1;
    26. 		subL->_bf = 0;
    27. 		subLR->_bf = 0;
    28. 	}
    29. 	else
    30. 	{
    31. 		// subLR->_bf旋转前就有问题
    32. 		assert(false);
    33. 	}
    34. }

            旋转操作就直接调用实现过的左单旋和右单旋函数即可。

            这里定义的变量依旧是subL、subLR，这里不需要定义ppNode，但是需要定义一个bf（因为我们需要根据subLR的平衡因子来分情况讨论）。

            最后就是根据图来分情况更新平衡因子，如果出现这些情况之外，说明在旋转前就有问题（防止自己前面实现错误，而不知道在哪出错），就断言报错。

    右左双旋：

            与左右双旋类似，直接看图：

            右左双旋同样是需要分情况讨论的（这里依旧是根据subRL进行分情况）

            第一种情况（subRL为0）：这种情况是发生左右双旋的最低高度，旋转后parent、subR、subRL的平衡因子都为0。

            第二种情况（subRL为-1）：旋转后parent = 0，subR = 1，subRL = 0

            第三种情况（subRL为1）：旋转后parent = -1，subR = 0，subRL = 0

    左右单旋的使用场景和操作：

            使用场景： 该cur节点的parent节点的平衡因子为2，cur节点的平衡因子为-1时，这里图的样子大概就是一个先向右后向左的折线。

            操作：我们将cur节点parent节点定义为parent，将该parent的右孩子节点定义为subR，将subR的左孩子节点定义为subRL。

            旋转方式：先对parent->_right（subR）进行右旋，将subRL的右孩子节点变为subR的左孩子节点，再右旋subR节点，让subR变为subRL的右孩子节点。然后再对parent进行左旋，将subRL的左孩子节点变为parent的右孩子节点，再左旋parent节点，让parent变为subRL的左孩子节点。最后更新平衡因子

    代码实现：

    1. void RotateRL(Node* parent)
    2. {
    3. 	Node* subR = parent->_right;
    4. 	Node* subRL = subR->_left;
    5. 	int bf = subRL->_bf;
    6.  
    7. 	RotateR(parent->_right);
    8. 	RotateL(parent);
    9.  
    10. 	// 更新平衡因子(分三种情况)
    11. 	if (bf == 0)
    12. 	{
    13. 		parent->_bf = 0;
    14. 		subR->_bf = 0;
    15. 		subRL->_bf = 0;
    16. 	}
    17. 	else if (bf == 1)
    18. 	{
    19. 		parent->_bf = -1;
    20. 		subR->_bf = 0;
    21. 		subRL->_bf = 0;
    22. 	}
    23. 	else if (bf == -1)
    24. 	{
    25. 		parent->_bf = 0;
    26. 		subR->_bf = 1;
    27. 		subRL->_bf = 0;
    28. 	}
    29. 	else
    30. 	{
    31. 		// subRL->_bf旋转前就有问题
    32. 		assert(false);
    33. 	}
    34. }

            旋转操作就直接调用实现过的右单旋和左单旋函数即可。

            这里依旧是定义变量，然后再根据画的图来更新平衡因子。

    4.判断该树是否为平衡二叉搜索树

            最后，我们再实现一个判断函数，因为我们并不知道我们实现的到底是不是平衡二叉搜索树。

            注意空树也属于平衡二叉搜索树，然后我们通过得到左右子树的平衡因子（高度差），再对这个平衡因子的大小进行判断，如果出现平衡因子的绝对值>=2的情况就说明该节点的平衡因子异常，如果出现该计算得到的平衡因子与上面得到的平衡因子大小不同，则说明该节点平衡因子不符合实际，这两种情况都说明不是平衡二叉搜索树。

            判断完该节点后，需要继续判断其它节点，这里我们采用递归的方法依次向左右子树内部去进行判断。

    1. bool _IsBalanceTree(Node* root)
    2. {
    3. 	// 空树也是AVL树
    4. 	if (nullptr == root)
    5. 		return true;
    6.  
    7. 	// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
    8. 	int leftHeight = _Height(root->_left);
    9. 	int rightHeight = _Height(root->_right);
    10. 	int diff = rightHeight - leftHeight;
    11.  
    12. 	// 如果计算出的平衡因子与pRoot的平衡因子不相等，
    13. 	// 或者pRoot平衡因子的绝对值超过1，则一定不是AVL树
    14. 	if (abs(diff) >= 2)
    15. 	{
    16. 		cout << root->_kv.first << "节点平衡因子异常" << endl;
    17. 		return false;
    18. 	}
    19.  
    20. 	if (diff != root->_bf)
    21. 	{
    22. 		cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
    23. 		return false;
    24. 	}
    25.  
    26. 	// pRoot的左和右如果都是AVL树，则该树一定是AVL树
    27. 	return _IsBalanceTree(root->_left)
    28. 		&& _IsBalanceTree(root->_right);
    29. }
    30.  
    31. bool IsBalanceTree()
    32. {
    33. 	return _IsBalanceTree(_root);
    34. }

    二.AVLTree实现代码

    1. #pragma once
    2. #include 
    3.  
    4. template<class K, class V>
    5. struct AVLTreeNode
    6. {
    7. 	pair _kv;
    8. 	AVLTreeNode* _left;
    9. 	AVLTreeNode* _right;
    10. 	AVLTreeNode* _parent;
    11.  
    12. 	// 右子树-左子树的高度差
    13. 	int _bf;
    14.  
    15. 	AVLTreeNode(const pair& kv)
    16. 		: _kv(kv)
    17. 		, _left(nullptr)
    18. 		, _right(nullptr)
    19. 		, _parent(nullptr)
    20. 		, _bf(0)
    21. 	{}
    22.  
    23. 	// AVL树没有规定必须要设计平衡因子
    24. 	// 平衡因子只是一个实现的选择，方便控制平衡
    25. };
    26.  
    27. template<class K, class V>
    28. class AVLTree
    29. {
    30. 	typedef AVLTreeNode Node;
    31. public:
    32. 	bool Insert(const pair& kv)
    33. 	{
    34. 		// 1.搜索树的规则插入
    35. 		// 2.看是否违反平衡规则，如果违反就需要处理：旋转
    36. 		if (_root == nullptr)
    37. 		{
    38. 			_root = new Node(kv);
    39. 			_root->_bf = 0;
    40. 			return true;
    41. 		}
    42. 		
    43. 		Node* parent = nullptr;
    44. 		Node* cur = _root;
    45. 		// 找到要插入的位置
    46. 		while (cur)
    47. 		{
    48. 			if (cur->_kv.first < kv.first)
    49. 			{
    50. 				parent = cur;
    51. 				cur = cur->_right;
    52. 			}
    53. 			else if (cur->_kv.first > kv.first)
    54. 			{
    55. 				parent = cur;
    56. 				cur = cur->_left;
    57. 			}
    58. 			else
    59. 			{
    60. 				return false;
    61. 			}
    62. 		}
    63.  
    64. 		// 插入该元素
    65. 		cur = new Node(kv);
    66. 		if (parent->_kv.first < kv.first)
    67. 		{
    68. 			parent->_right = cur;
    69. 		}
    70. 		else
    71. 		{
    72. 			parent->_left = cur;
    73. 		}
    74.  
    75. 		cur->_parent = parent;
    76.  
    77. 		// 更新平衡因子
    78. 		// 最远要更新到根为止
    79. 		while (parent)
    80. 		{
    81. 			if (cur == parent->_right)
    82. 			{
    83. 				parent->_bf++;
    84. 			}
    85. 			else
    86. 			{
    87. 				parent->_bf--;
    88. 			}
    89.  
    90. 			// 判断是否要继续更新
    91. 			// 1 or -1 -》 0  插入的节点填上了矮的那边
    92. 			if (parent->_bf == 0)
    93. 			{
    94. 				// 高度不变，更新结束
    95. 				break;
    96. 			}
    97. 			// 0 -》 1 or -1  插入节点导致一边变高了
    98. 			else if (parent->_bf == 1 || parent->_bf == -1)
    99. 			{
    100. 				// 子树的高度变了，继续更新祖先
    101. 				cur = cur->_parent;
    102. 				parent = parent->_parent;
    103. 			}
    104. 			// 1 or -1 -》 2 or -2  插入节点导致本来高的一边又变高了
    105. 			else if (parent->_bf == 2 || parent->_bf == -2)
    106. 			{
    107. 				// 子树不平衡  --需要旋转处理
    108. 				// 左单旋
    109. 				if (parent->_bf == 2 && cur->_bf == 1)
    110. 				{
    111. 					RotateL(parent);
    112. 				}
    113. 				// 右单旋
    114. 				else if (parent->_bf == -2 && cur->_bf == -1)
    115. 				{
    116. 					RotateR(parent);
    117. 				}
    118. 				// 左右双旋
    119. 				else if (parent->_bf == -2 && cur->_bf == 1)
    120. 				{
    121. 					RotateLR(parent);
    122. 				}
    123. 				// 右左双旋
    124. 				else if (parent->_bf == 2 && cur->_bf == -1)
    125. 				{
    126. 					RotateRL(parent);
    127. 				}
    128. 				
    129. 				break;
    130. 			}
    131. 			else
    132. 			{
    133. 				// 插入之前AVL就存在不平衡子树（平衡因子的绝对值>= 2的节点）
    134. 				assert(false);
    135. 			}
    136. 		}
    137.  
    138. 		return true;
    139. 	}
    140. private:
    141. 	void RotateL(Node* parent)
    142. 	{
    143. 		Node* subR = parent->_right;
    144. 		Node* subRL = subR->_left;
    145.  
    146. 		Node* ppNode = parent->_parent;
    147.  
    148. 		parent->_right = subRL;
    149. 		parent->_parent = subR;
    150. 		if (subRL)
    151. 		{
    152. 			subRL->_parent = parent;
    153. 		}
    154. 		subR->_left = parent;
    155. 		
    156. 		if (parent == _root)
    157. 		{
    158. 			_root = subR;
    159. 			_root->_parent = nullptr;
    160. 		}
    161. 		else
    162. 		{
    163. 			if (ppNode->_left == parent)
    164. 			{
    165. 				ppNode->_left = subR;
    166. 			}
    167. 			else
    168. 			{
    169. 				ppNode->_right = subR;
    170. 			}
    171.  
    172. 			subR->_parent = ppNode;
    173. 		}
    174.  
    175. 		// 更新平衡因子
    176. 		subR->_bf = 0;
    177. 		parent->_bf = 0;
    178. 	}
    179.  
    180. 	void RotateR(Node* parent)
    181. 	{
    182. 		Node* subL = parent->_left;
    183. 		Node* subLR = subL->_right;
    184.  
    185. 		Node* ppNode = parent->_parent;
    186.  
    187. 		parent->_left = subLR;
    188. 		parent->_parent = subL;
    189.  
    190. 		if (subLR)
    191. 		{
    192. 			subLR->_parent = parent;
    193. 		}
    194. 		subL->_right = parent;
    195. 		
    196. 		if (parent == _root)
    197. 		{
    198. 			_root = subL;
    199. 			_root->_parent = nullptr;
    200. 		}
    201. 		else
    202. 		{
    203. 			if (parent == ppNode->_left)
    204. 			{
    205. 				ppNode->_left = subL;
    206. 			}
    207. 			else
    208. 			{
    209. 				ppNode->_right = subL;
    210. 			}
    211.  
    212. 			subL->_parent = ppNode;
    213. 		}
    214.  
    215. 		subL->_bf = 0;
    216. 		parent->_bf = 0;
    217. 	}
    218.  
    219. 	void RotateLR(Node* parent)
    220. 	{
    221. 		Node* subL = parent->_left;
    222. 		Node* subLR = subL->_right;
    223. 		int bf = subLR->_bf;
    224.  
    225. 		RotateL(parent->_left);
    226. 		RotateR(parent);
    227.  
    228. 		// 更新平衡因子(分三种情况)
    229. 		if (bf == 0)
    230. 		{
    231. 			parent->_bf = 0;
    232. 			subL->_bf = 0;
    233. 			subLR->_bf = 0;
    234. 		}
    235. 		else if (bf == 1)
    236. 		{
    237. 			parent->_bf = 0;
    238. 			subL->_bf = -1;
    239. 			subLR->_bf = 0;
    240. 		}
    241. 		else if (bf == -1)
    242. 		{
    243. 			parent->_bf = 1;
    244. 			subL->_bf = 0;
    245. 			subLR->_bf = 0;
    246. 		}
    247. 		else
    248. 		{
    249. 			// subLR->_bf旋转前就有问题
    250. 			assert(false);
    251. 		}
    252. 	}
    253.  
    254. 	void RotateRL(Node* parent)
    255. 	{
    256. 		Node* subR = parent->_right;
    257. 		Node* subRL = subR->_left;
    258. 		int bf = subRL->_bf;
    259.  
    260. 		RotateR(parent->_right);
    261. 		RotateL(parent);
    262.  
    263. 		// 更新平衡因子(分三种情况)
    264. 		if (bf == 0)
    265. 		{
    266. 			parent->_bf = 0;
    267. 			subR->_bf = 0;
    268. 			subRL->_bf = 0;
    269. 		}
    270. 		else if (bf == 1)
    271. 		{
    272. 			parent->_bf = -1;
    273. 			subR->_bf = 0;
    274. 			subRL->_bf = 0;
    275. 		}
    276. 		else if (bf == -1)
    277. 		{
    278. 			parent->_bf = 0;
    279. 			subR->_bf = 1;
    280. 			subRL->_bf = 0;
    281. 		}
    282. 		else
    283. 		{
    284. 			// subRL->_bf旋转前就有问题
    285. 			assert(false);
    286. 		}
    287. 	}
    288.  
    289. 	bool _IsBalanceTree(Node* root)
    290. 	{
    291. 		// 空树也是AVL树
    292. 		if (nullptr == root)
    293. 			return true;
    294.  
    295. 		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
    296. 		int leftHeight = _Height(root->_left);
    297. 		int rightHeight = _Height(root->_right);
    298. 		int diff = rightHeight - leftHeight;
    299.  
    300. 		// 如果计算出的平衡因子与pRoot的平衡因子不相等，
    301. 		// 或者pRoot平衡因子的绝对值超过1，则一定不是AVL树
    302. 		if (abs(diff) >= 2)
    303. 		{
    304. 			cout << root->_kv.first << "节点平衡因子异常" << endl;
    305. 			return false;
    306. 		}
    307.  
    308. 		if (diff != root->_bf)
    309. 		{
    310. 			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
    311. 			return false;
    312. 		}
    313.  
    314. 		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
    315. 		return _IsBalanceTree(root->_left)
    316. 			&& _IsBalanceTree(root->_right);
    317. 	}
    318. public:
    319. 	bool IsBalanceTree()
    320. 	{
    321. 		return _IsBalanceTree(_root);
    322. 	}
    323. private:
    324. 	Node* _root = nullptr;
    325. };
  • 相关阅读:
    （仿牛客社区项目）Java开发笔记7.7：生成长图
    低功耗蓝牙（BLE）开发——Qt
    Java进阶（十）File、方法递归、IO流
    【计算机视觉 | 图像分割】arxiv 计算机视觉关于图像分割的学术速递（9 月 6 日论文合集）
    点阵 LED 显示设计实验
    软件测试工程师的职场发展顺序，月薪30k的测试岗技术要求是真的高...
    计算机网络
    移动web响应式布局
    探索DeFi元宇宙：NFT、Web3和DAPP的数藏Swap合约应用开发
    type和interface的异同？
  • 原文地址：https://blog.csdn.net/qq_60750110/article/details/126171395