• [ 数据结构 - C++] AVL树原理及实现

    问题引入：

    在上文我们提到了二叉搜索树在按值顺序插入时，会形成单边树，会大大降低二叉搜索树的性能。因此我们要将二叉搜索树进行平衡，采取适当的平衡措施，从而减低二叉搜索树的高度，使二叉搜索树达到一个接近于完全二叉树的样子（如下图所示），提高二叉搜索树的性能。本节我们要介绍的平衡树为AVL树。

    目录

    1.AVL树

    1.1 AVL树的概念

    2.AVL树节点的定义

    3.AVL树的插入与旋转

    3.1 左单旋

    代码实现左单旋

    3.2 右单旋

    代码实现右单旋

    3.3 先左单旋再右单旋

    左右双旋代码实现：

    3.4 先右单旋再左单旋

    右左双旋代码实现

    Insert实现代码

    4.判断一棵树是否是AVL树

    验证AVL树代码实现：

    5.AVL树的验证与查看

    验证与查看：

    1.顺序插入

    2.随机值

    6.AVL树的性能

    附录：

    1.AVL树

    1.1 AVL树的概念

    在上述我们所提到，二叉搜索树虽然可以缩短查找的效率，但如果数据有序或接近有序时，二叉搜索树将退化为单支树（单边树），查找元素相当于在顺序表中搜索元素，效率十分低下。因此，两位俄罗斯数学家G.M.Adelson-Velski和E.M.Landis 在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

    一颗AVL树或者空树具有一下性质：

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

    如果一颗二叉搜索树是高度平衡的，他就是AVL树。如果它有n个节点，其高度可保持在O(log N)，搜索时间复杂度为O(logN)。

    此时我们大致了解了AVL树的平衡规则，接下来我们将手动模拟实现一下AVL树的主要功能。

    2.AVL树节点的定义

    AVL树节点的定义

    我们在此处实现的是KV模型的AVL树，K模型的较为简单，大家可以自己尝试实现。

    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; // balance factor 
    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. };

    从节点的定义我们可以看出，有普通的二叉搜树不同的是，AVL树中节点的设置添加了节点的parent节点，此处也是为了方便后续功能的实现（接着往下看就明白了）。除此之外，节点也定义了一个控制平衡因子_bf，用来表示当前节点右子树与左子树的高度差。

    3.AVL树的插入与旋转

    AVL树的插入就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看做一个二叉搜索树。

    AVL树的插入过程可以分为两步：

    1. 按照二叉搜索树的方式插入新节点
    2. 调整节点的平衡因子

    AVL树在插入的过程中，如果插入新节点后导致AVL树中某些节点的平衡因子的绝对值大于等于1时，要进行旋转操作，根据节点插入位置的不同，AVL树的旋转分为四种。接下来我们逐一分析可能出现的情况与解决该问题的旋转方法。

    3.1 左单旋

    什么时候我们需要进行左单旋转呢?当新节点插入较高右子树的右侧时，我们看一个需要左单旋的最简单的情况。

    在下图中，当树要插入节点90，此时根节点的平衡因子为2，已经不满足AVL树的规则，因此要进行旋转。我们发现新节点插入了较高右子树的右侧。因此需要进行左单旋（即就是将右子树提上去）。

    左单旋的步骤：

    1.让插入节点的父节点，也就是这里的60的左子树变成节点30的右子树，30这颗子树成为60的左子树。

    2.调整改变节点的平衡因子。

    由于我们这里是最简单的情况，如果我们变成较为复杂的情况，如下图所示。

    在这个图中，无论在b还是c树下插入新节点，都是在30的右树下插入新节点，因此这里将有4中可能性（分别是b的左右孩子，c的左右孩子处），这里以c的孩子为例。但是情况均为右单旋情况。

    旋转步骤为：将60的左树变为30的右树，再让30成为60的左树，最后更改旋转因子。

    需要考虑的特殊情况：

    1. 60的节点的左孩子可能存在，也可能不存在。
    2. 30可能是根节点，也可能是子树：如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也能是右子树。

    代码实现左单旋

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

    3.2 右单旋

    右单旋是当新节点插入较高的左子树的左侧时进行使用。我们也来看一个最简单的右单旋的情况。

    在下图中，当我们要新插入节点10，我们发现30的左子树增加了一层，导致以60位根的二叉树不平衡，要让60平衡，只能将60的左子树的高度减少一层，右子树增加一层。即将左子树提上来。

    旋转步骤为：将30的右子树变成60的左子树，再让60变成30的左子树。旋转完成后更新节点的平衡因子即可。

    由于我们这里是最简单的情况，如果我们变成较为复杂的情况，如下图所示。

    右单旋需要考虑的情况：

    1. 30节点的右孩子可能存在也可能不存在
    2. 60可能是根节点，也可能是子树。如果是根节点，旋转完成后要更新跟节点。如果是子树，可能是某个节点的左子树也可能是右子树。

    代码实现右单旋

    1. void RotateR(Node* parent)
    2. 	{
    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 (ppNode->_left == parent)
    24. 			{
    25. 				ppNode->_left = subL;
    26. 			}
    27. 			else
    28. 			{
    29. 				ppNode->_right = subL;
    30. 			}
    31. 			subL->_parent = ppNode;
    32. 		}
    33.  
    34. 		subL->_bf = parent->_bf = 0;
    35. 	}

    3.3 先左单旋再右单旋

    这是一种很复杂的情况，当新节点插入较高左子树的右侧时，要发生左右单旋。

    我们来看具体例子直观感受这种情况。将双旋变成单旋再旋转，即对30进行左单旋再对90进行右单旋，旋转完再考虑平衡因子的更新。

    左右双旋代码实现：

    1. //左右双旋
    2. 	void RotateLR(Node* parent)
    3. 	{
    4. 		Node* subL = parent->_left;
    5. 		Node* subLR = subL->_right;
    6.  
    7. 		int bf = subLR->_bf;
    8. 		RotateL(parent->_left);//左
    9. 		RotateR(parent);//右
    10.  
    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. 			// subLR->_bf 旋转前就出现问题
    33. 			assert(false);
    34. 		}
    35. 	}

    3.4 先右单旋再左单旋

    当新节点插入较高右子树的左侧时就要进行右左单旋。我们直接来看具体情况

    将右左双旋变成单旋再旋转，即对90进行右单旋再对30进行左单旋，旋转完再考虑平衡因子的更新。

    右左双旋代码实现

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

    AVL树的旋转共以上四种情况。

    总结：

    加入pParent为根的子树不平衡是，即pParent的平衡因子为2或者-2，分以下情况考虑

    1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根伟pSubR
    • 当pSubR的平衡因子为1时，执行左单旋
    • 当pSubR的平衡因子为-1时，执行右左双旋转
    1. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的跟为pSubL
    • 当pSubL的平衡因子为-1时，执行右单旋
    • 当pSubL的平衡因子为1是，执行左右双旋

    旋转完成后，原pParent为跟的子树的高度降低，已经平衡，不需要再向上更新了。

    考虑完所有的旋转情况后，我们此时实现insert插入。

    insert插入大框架还是二叉搜索树的insert,只不过加入了平衡因子，不平衡时进行旋转。

    Insert实现代码

    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. 		while (cur)
    15. 		{
    16. 			if (cur->_kv.first < kv.first)
    17. 			{
    18. 				parent = cur;
    19. 				cur = cur->_right;
    20. 			}
    21. 			else if (cur->_kv.first > kv.first)
    22. 			{
    23. 				parent = cur;
    24. 				cur = cur->_left;
    25. 			}
    26. 			else
    27. 			{
    28. 				return false;
    29. 			}
    30. 		}
    31.  
    32. 		cur = new Node(kv);
    33. 		if (parent->_kv.first < kv.first)
    34. 		{
    35. 			parent->_right = cur;
    36. 		}
    37. 		else
    38. 		{
    39. 			parent->_left = cur;
    40. 		}
    41.  
    42. 		cur->_parent = parent;
    43.  
    44. 		//.....
    45. 		//更新平衡因子
    46.  
    47. 		while (parent)
    48. 		{
    49. 			if (cur == parent->_right)
    50. 			{
    51. 				parent->_bf++;
    52. 			}
    53. 			else
    54. 			{
    55. 				parent->_bf--;
    56. 			}
    57.  
    58. 			//是否继续更新？
    59. 			// 1 or -1  ->插入节点填上了矮的那边
    60. 			if (parent->_bf == 0)
    61. 			{
    62. 				break;
    63. 			}
    64. 			//0->1 或者 -1 插入节点导致一边变高了
    65. 			else if (parent->_bf == 1 || parent->_bf == -1)
    66. 			{
    67. 				//子树的高度变了，继续更新祖先
    68. 				cur = cur->_parent;
    69. 				parent = parent->_parent;
    70. 			}
    71. 			// -1 or 1 -》 2 or -2 插入几点导致本来高的一边更高了
    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. 				break;
    92. 			}
    93. 			else
    94. 			{
    95. 				//插入之前AVL树就存在不平衡子树
    96. 				assert(false);
    97. 			}
    98. 		}
    99. 		return true;
    100. 	}

    4.判断一棵树是否是AVL树

    由于AVL是在二叉搜索树的基础上加入了平衡机制，因此验证AVL树可以分为两步：

    1. 首先验证其是否为二叉搜索树

    如果中序遍历可得到一个有序的序列，就说明是二叉搜索树

    1. 验证其是否为平衡树（把握AVL树的规则）
      1. 每个节点子树高度差的绝对值不超过1（注意节点如果没有平衡因子）
      2. 节点的平衡因子是否计算正确
      3. 每个AVL树的左右子树也为AVL树，因此可以使用递归判断其左右子树是否为AVL树

    验证AVL树代码实现：

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

    5.AVL树的验证与查看

    我们使用层序遍历的方式输出打印可以直观查看AVL树。使用层序遍历需要借助队列。

    1. //层序输出
    2. 	vectorint>> levelOrder() {
    3. 		vectorint>> vv;
    4. 		if (_root == nullptr)
    5. 			return vv;
    6.  
    7. 		queue q;
    8. 		int levelSize = 1;
    9. 		q.push(_root);
    10.  
    11. 		while (!q.empty())
    12. 		{
    13. 			// levelSize控制一层一层出
    14. 			vector<int> levelV;
    15. 			while (levelSize--)
    16. 			{
    17. 				Node* front = q.front();
    18. 				q.pop();
    19. 				levelV.push_back(front->_kv.first);
    20. 				if (front->_left)
    21. 					q.push(front->_left);
    22.  
    23. 				if (front->_right)
    24. 					q.push(front->_right);
    25. 			}
    26. 			vv.push_back(levelV);
    27. 			for (auto e : levelV)
    28. 			{
    29. 				cout << e << " ";
    30. 			}
    31. 			cout << endl;
    32.  
    33. 			// 上一层出完，下一层就都进队列
    34. 			levelSize = q.size();
    35. 		}
    36.  
    37. 		return vv;
    38. 	}

    验证与查看：

    我们手动模拟一些值，让其插入输出。

    1.顺序插入

    1. void TestAVLTree2()
    2. {
    3. 	const size_t N = 10;
    4. 	vector<int> v;
    5. 	v.reserve(N);
    6. 	srand(time(0));//生成随机树
    7. 	for (size_t i = 0; i < N; ++i)
    8. 	{
    9. 		//v.push_back(rand());
    10. 		v.push_back(i);
    11. 	}
    12.  
    13. 	AVLTree<int, int> t;
    14. 	for (auto e : v)
    15. 	{
    16. 		t.Insert(make_pair(e, e));
    17. 	}
    18.  
    19. 	t.levelOrder();
    20. 	cout << endl;
    21. 	cout << "是否平衡?" << t.IsBalanceTree() << endl;
    22. 	cout << "高度:" << t.Height() << endl;
    23.  
    24.  
    25. 	//t.InOrder();
    26. }

    2.随机值

    6.AVL树的性能

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

    （本篇完）

    附录：

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. using namespace std;
    10.  
    11. template<class K, class V>
    12. struct AVLTreeNode
    13. {
    14. 	pair _kv;
    15. 	AVLTreeNode* _left;
    16. 	AVLTreeNode* _right;
    17. 	AVLTreeNode* _parent;
    18.  
    19. 	// 右子树-左子树  的高度差
    20. 	int _bf; // balance factor 
    21.  
    22. 	AVLTreeNode(const pair& kv)
    23. 		:_kv(kv)
    24. 		, _left(nullptr)
    25. 		, _right(nullptr)
    26. 		, _parent(nullptr)
    27. 		, _bf(0)
    28. 	{}
    29.  
    30. 	// AVL树并没有规定必须要设计平衡因子
    31. 	// 只是一个实现的选择，方便控制平衡
    32. };
    33.  
    34. template<class K, class V>
    35. class AVLTree
    36. {
    37. 	typedef AVLTreeNode Node;
    38. public:
    39. 	bool Insert(const pair& kv)
    40. 	{
    41. 		//1、按照搜索树的规则插入
    42. 		//2、看是否违反平衡规则，如果违反就需要处理：旋转
    43. 		if (_root == nullptr)
    44. 		{
    45. 			_root = new Node(kv);
    46. 			_root->_bf = 0;
    47. 			return true;
    48. 		}
    49.  
    50. 		Node* parent = nullptr;
    51. 		Node* cur = _root;
    52. 		while (cur)
    53. 		{
    54. 			if (cur->_kv.first < kv.first)
    55. 			{
    56. 				parent = cur;
    57. 				cur = cur->_right;
    58. 			}
    59. 			else if (cur->_kv.first > kv.first)
    60. 			{
    61. 				parent = cur;
    62. 				cur = cur->_left;
    63. 			}
    64. 			else
    65. 			{
    66. 				return false;
    67. 			}
    68. 		}
    69.  
    70. 		cur = new Node(kv);
    71. 		if (parent->_kv.first < kv.first)
    72. 		{
    73. 			parent->_right = cur;
    74. 		}
    75. 		else
    76. 		{
    77. 			parent->_left = cur;
    78. 		}
    79.  
    80. 		cur->_parent = parent;
    81.  
    82. 		//.....
    83. 		//更新平衡因子
    84.  
    85. 		while (parent)
    86. 		{
    87. 			if (cur == parent->_right)
    88. 			{
    89. 				parent->_bf++;
    90. 			}
    91. 			else
    92. 			{
    93. 				parent->_bf--;
    94. 			}
    95.  
    96. 			//是否继续更新？
    97. 			// 1 or -1  ->插入节点填上了矮的那边
    98. 			if (parent->_bf == 0)
    99. 			{
    100. 				break;
    101. 			}
    102. 			//0->1 或者 -1 插入节点导致一边变高了
    103. 			else if (parent->_bf == 1 || parent->_bf == -1)
    104. 			{
    105. 				//子树的高度变了，继续更新祖先
    106. 				cur = cur->_parent;
    107. 				parent = parent->_parent;
    108. 			}
    109. 			// -1 or 1 -》 2 or -2 插入几点导致本来高的一边更高了
    110. 			else if (parent->_bf == 2 || parent->_bf == -2)
    111. 			{
    112. 				//子树不平衡-- 需要旋转处理
    113. 				if (parent->_bf == 2 && cur->_bf == 1)//左单旋
    114. 				{
    115. 					RotateL(parent);
    116. 				}
    117. 				else if (parent->_bf == -2 && cur->_bf == -1)//右
    118. 				{
    119. 					RotateR(parent);
    120. 				}
    121. 				else if (parent->_bf == -2 && cur->_bf == -1)//左右双旋
    122. 				{
    123. 					RotateLR(parent);
    124. 				}
    125. 				else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
    126. 				{
    127. 					RotateRL(parent);
    128. 				}
    129. 				break;
    130. 			}
    131. 			else
    132. 			{
    133. 				//插入之前AVL树就存在不平衡子树
    134. 				assert(false);
    135. 			}
    136. 		}
    137. 		return true;
    138. 	}
    139. private:
    140. 	void RotateL(Node* parent)
    141. 	{
    142. 		//左旋
    143. 		Node* subR = parent->_right;
    144. 		Node* subRL = subR->_left;
    145. 		parent->_right = subRL;
    146. 		if (subRL)
    147. 			subRL->_parent = parent;
    148.  
    149. 		Node* ppNode = parent->_parent;
    150.  
    151. 		subR->_left = parent;
    152. 		parent->_parent = subR;
    153.  
    154. 		if (parent == _root)
    155. 		{
    156. 			_root = subR;
    157. 			_root->_parent = nullptr;
    158. 		}
    159. 		else
    160. 		{
    161. 			if (parent == ppNode->_left)
    162. 			{
    163. 				ppNode->_left = subR;
    164. 			}
    165. 			else
    166. 			{
    167. 				ppNode->_right = subR;
    168. 			}
    169.  
    170. 			subR->_parent = ppNode;
    171. 		}
    172.  
    173. 		//更新平衡因子
    174. 		parent->_bf = 0;
    175. 		subR->_bf = 0;
    176. 	}
    177.  
    178. 	void RotateR(Node* parent)
    179. 	{
    180. 		//右旋
    181. 		Node* subL = parent->_left;
    182. 		Node* subLR = subL->_right;
    183.  
    184. 		parent->_left = subLR;
    185. 		if (subLR)
    186. 			subLR->_parent = parent;
    187.  
    188. 		Node* ppNode = parent->_parent;
    189.  
    190. 		subL->_right = parent;
    191. 		parent->_parent = subL;
    192.  
    193. 		if (parent == _root)
    194. 		{
    195. 			_root = subL;
    196. 			_root->_parent = nullptr;
    197. 		}
    198. 		else
    199. 		{
    200. 			if (ppNode->_left == parent)
    201. 			{
    202. 				ppNode->_left = subL;
    203. 			}
    204. 			else
    205. 			{
    206. 				ppNode->_right = subL;
    207. 			}
    208. 			subL->_parent = ppNode;
    209. 		}
    210.  
    211. 		subL->_bf = parent->_bf = 0;
    212. 	}
    213.  
    214. 	//左右双旋
    215. 	void RotateLR(Node* parent)
    216. 	{
    217. 		Node* subL = parent->_left;
    218. 		Node* subLR = subL->_right;
    219.  
    220. 		int bf = subLR->_bf;
    221. 		RotateL(parent->_left);//左
    222. 		RotateR(parent);//右
    223.  
    224. 		//更新平衡因子
    225. 		if (bf == 0)
    226. 		{
    227. 			parent->_bf = 0;
    228. 			subL->_bf = 0;
    229. 			subLR->_bf = 0;
    230. 		}
    231. 		else if (bf == 1)
    232. 		{
    233. 			parent->_bf = 0;
    234. 			subL->_bf = -1;
    235. 			subLR->_bf = 0;
    236. 		}
    237. 		else if (bf == -1)
    238. 		{
    239. 			parent->_bf = 1;
    240. 			subL->_bf = 0;
    241. 			subLR->_bf = 0;
    242. 		}
    243. 		else
    244. 		{
    245. 			// subLR->_bf 旋转前就出现问题
    246. 			assert(false);
    247. 		}
    248. 	}
    249. 	//右左双旋
    250. 	void RotateRL(Node* parent)
    251. 	{
    252. 		Node* subR = parent->_right;
    253. 		Node* subRL = subR->_left;
    254. 		int bf = subRL->_bf;
    255.  
    256. 		RotateR(parent->_right);
    257. 		RotateL(parent);
    258.  
    259. 		if (bf == 0)
    260. 		{
    261. 			subRL->_bf = 0;
    262. 			parent->_bf = 0;
    263. 			subR->_bf = 0;
    264. 		}
    265. 		else if (bf == 1)
    266. 		{
    267. 			subRL->_bf = 0;
    268. 			parent->_bf = -1;
    269. 			subR->_bf = 0;
    270. 		}
    271. 		else if(bf == -1)
    272. 		{
    273. 			subRL->_bf = 0;
    274. 			parent->_bf = 0;
    275. 			subR->_bf = 1;
    276. 		}
    277. 		else
    278. 		{
    279. 			// subLR->_bf 旋转前就有问题
    280. 			assert(false);
    281. 		}
    282. 	}
    283.  
    284. 	void _InOrder(Node* root)
    285. 	{
    286. 		if (root == nullptr)
    287. 			return;
    288. 		_InOrder(root->_left);
    289. 		cout << root->_kv.first << " ";
    290. 		_InOrder(root->_right);
    291. 	}
    292.  
    293. 	int _Height(Node* root)
    294. 	{
    295. 		if (root == nullptr)
    296. 			return 0;
    297. 		int lh = _Height(root->_left);
    298. 		int rh = _Height(root->_right);
    299.  
    300. 		return lh > rh ? lh + 1 : rh + 1;
    301. 	}
    302.  
    303. 	//是否是平衡树
    304. 	bool _IsBalanceTree(Node* root)
    305. 	{
    306. 		// 空树也是AVL树
    307. 		if (nullptr == root)
    308. 			return true;
    309.  
    310. 		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
    311. 		int leftHeight = _Height(root->_left);
    312. 		int rightHeight = _Height(root->_right);
    313. 		int diff = rightHeight - leftHeight;
    314.  
    315. 		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
    316. 		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
    317. 		if (abs(diff) >= 2)
    318. 		{
    319. 			cout << root->_kv.first << "节点平衡因子异常" << endl;
    320. 			return false;
    321. 		}
    322.  
    323. 		if (diff != root->_bf)
    324. 		{
    325. 			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
    326. 			return false;
    327. 		}
    328.  
    329. 		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
    330. 		return _IsBalanceTree(root->_left)
    331. 			&& _IsBalanceTree(root->_right);
    332. 	}
    333. public:
    334. 	void InOrder()
    335. 	{
    336. 		_InOrder(_root);
    337. 		cout << endl;
    338. 	}
    339. 	bool IsBalanceTree()
    340. 	{
    341. 		return _IsBalanceTree(_root);
    342. 	}
    343.  
    344. 	int Height()
    345. 	{
    346. 		return _Height(_root);
    347. 	}
    348. 	//层序输出
    349. 	vectorint>> levelOrder() {
    350. 		vectorint>> vv;
    351. 		if (_root == nullptr)
    352. 			return vv;
    353.  
    354. 		queue q;
    355. 		int levelSize = 1;
    356. 		q.push(_root);
    357.  
    358. 		while (!q.empty())
    359. 		{
    360. 			// levelSize控制一层一层出
    361. 			vector<int> levelV;
    362. 			while (levelSize--)
    363. 			{
    364. 				Node* front = q.front();
    365. 				q.pop();
    366. 				levelV.push_back(front->_kv.first);
    367. 				if (front->_left)
    368. 					q.push(front->_left);
    369.  
    370. 				if (front->_right)
    371. 					q.push(front->_right);
    372. 			}
    373. 			vv.push_back(levelV);
    374. 			for (auto e : levelV)
    375. 			{
    376. 				cout << e << " ";
    377. 			}
    378. 			cout << endl;
    379.  
    380. 			// 上一层出完，下一层就都进队列
    381. 			levelSize = q.size();
    382. 		}
    383.  
    384. 		return vv;
    385. 	}
    386.  
    387. private:
    388. 	Node* _root = nullptr;
    389. };
    390.  
    391. void TestAVLTree()
    392. {
    393. 	AVLTree<int, int> t;
    394. 	t.Insert(make_pair(1, 1));
    395. 	t.Insert(make_pair(2, 2));
    396. 	t.Insert(make_pair(3, 3));
    397. }
    398.  
    399. void TestAVLTree1()
    400. {
    401. 	int a[] = { 30,29,28,27,26,25,24,11,8,7,6,5,4,3,2,1 };
    402. 	//int a[] = { 30,1,3,15,33,14,2,7,8,20,27,25 };
    403. 	AVLTree<int, int> t;
    404. 	for (auto e : a)
    405. 	{
    406. 		t.Insert(make_pair(e, e));
    407. 	}
    408. 	t.levelOrder();
    409. }
    410.  
    411. void TestAVLTree2()
    412. {
    413. 	const size_t N = 10;
    414. 	vector<int> v;
    415. 	v.reserve(N);
    416. 	srand(time(0));//生成随机树
    417. 	for (size_t i = 0; i < N; ++i)
    418. 	{
    419. 		v.push_back(rand());
    420. 		//v.push_back(i);
    421. 	}
    422.  
    423. 	AVLTree<int, int> t;
    424. 	for (auto e : v)
    425. 	{
    426. 		t.Insert(make_pair(e, e));
    427. 	}
    428.  
    429. 	t.levelOrder();
    430. 	cout << endl;
    431. 	cout << "是否平衡?" << t.IsBalanceTree() << endl;
    432. 	cout << "高度:" << t.Height() << endl;
    433.  
    434.  
    435. 	//t.InOrder();
    436. }

  • 相关阅读:
    Qt的Pro文件
    Android: HttpURLConnection获取JSON数据
    防火墙(Firewall)
    PXE高效批量网络装机
    最常用的 9 个JavaScript 函数与示例
    转行网络安全是否可行？
    性能测试 —— 生成html测试报告、参数化、jvm监控
    Session详解
    三西格玛和六西格玛区别是什么？优思学院用一幅图告诉你
    element表格table点击添加背景色
  • 原文地址：https://blog.csdn.net/qq_58325487/article/details/127057530