• ＜AVL树＞——《C++高阶》

    目录

    1.AVL树

    1.1AVL树的概念

    1.2 AVL树节点的定义

    1.3 AVL树的插入

    1.4 AVL树的旋转

    1. 新节点插入较高左子树的左侧---左左：右单旋​

     2. 新节点插入较高右子树的右侧---右右：左单旋​

    3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋​

    4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋​

     1.5 AVL树的验证

    1.6 AVL树的删除(了解)

    1.7 AVL树的性能

    2.AVL树的实现：

    2.1功能函数：

    （1）定义AVL树的基本结构：​

    （2）Insert函数以及平衡因子bf的调整：​

    （3）左单旋RotateL:​

    （4）右单旋RotateR：​

    （5）左右双旋RotateLR：​ 

    （6）右左双旋RotateRL：​

    （7）遍历（递归版）:

    （8）求树的高度：​

    （9）判断是否为平衡二叉树： 

    （10）测试用例：​

    2.2完整源码：

    （1）AVLTree.h:

    （2）test.cpp：

    2.3总结：

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

     

    1.AVL树

    1.1AVL树的概念

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

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

    1.2 AVL树节点的定义

    AVL树节点的定义： 
    1. template<class T>
    2. struct AVLTreeNode
    3. {
    4. 	AVLTreeNode(const T& data)
    5. 		: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
    6. 		, _data(data), _bf(0)
    7. 	{}
    8. 	AVLTreeNode* _pLeft;   // 该节点的左孩子
    9. 	AVLTreeNode* _pRight;  // 该节点的右孩子
    10. 	AVLTreeNode* _pParent; // 该节点的双亲
    11. 	T _data;
    12. 	int _bf;                  // 该节点的平衡因子
    13. };

     1.3 AVL树的插入

    AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
    AVL树的插入过程可以分为两步：
    1. 按照二叉搜索树的方式插入新节点
    2. 调整节点的平衡因子 
    1. bool Insert(const T& data) 
    2. {
    3. 	// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
    4. 	// ...
    5.  
    6. 	// 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树
    7. 		//   的平衡性
    8.  
    9. 	 /*
    10. 	 pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
    11. 	 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
    12. 	  1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
    13. 	  2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
    14. 	  
    15. 	 此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2
    16. 	  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
    17. 	成0，此时满足
    18. 	     AVL树的性质，插入成功
    19. 	  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
    20. 	新成正负1，此
    21. 	     时以pParent为根的树的高度增加，需要继续向上更新
    22. 	  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进
    23. 	行旋转处理
    24. 	 */
    25. 		while (pParent)
    26. 		{
    27. 			// 更新双亲的平衡因子
    28. 			if (pCur == pParent->_pLeft)
    29. 				pParent->_bf--;
    30. 			else
    31. 				pParent->_bf++;
    32. 			// 更新后检测双亲的平衡因子
    33. 			if (0 == pParent->_bf)
    34. 			{
    35. 				break;
    36. 			}
    37. 			else if (1 == pParent->_bf || -1 == pParent->_bf)
    38. 			{
    39. 				// 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲
    40. 				为根的二叉树
    41. 					// 的高度增加了一层，因此需要继续向上调整
    42. 					pCur = pParent;
    43. 				pParent = pCur->_pParent;
    44. 			}
    45. 			else
    46. 			{
    47. 				// 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以pParent
    48. 				// 为根的树进行旋转处理
    49. 				if (2 == pParent->_bf)
    50. 				{
    51. 					// ...
    52. 				}
    53. 				else
    54. 				{
    55. 					// ...
    56. 				}
    57. 			}
    58. 		}
    59. 	return true;
    60. }

    1.4 AVL树的旋转

    如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

    1. 新节点插入较高左子树的左侧---左左：右单旋

    1. /*
    2.   上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，
    3.   导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层， 即将左子树往上提，
    4.   这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有 右子树，右子树根的值一定大于30，小于60，
    5.   只能将其放在60的左子树，旋转完成后，更新节点 的平衡因子即可。在旋转过程中，
    6.   有以下几种情况需要考虑： 
    7.   1. 30节点的右孩子可能存在，也可能不存在 
    8.   2. 60可能是根节点，也可能是子树 
    9. 			如果是根节点，旋转完成后，要更新根节点 如果是子树，
    10. 			可能是某个节点的左子树，也可能是右子树 
    11.   同学们再此处可举一些详细的例子进行画图，考虑各种情况，加深旋转的理解 */
    12. void _RotateR(PNode pParent) 
    13. { 
    14. 	// pSubL: pParent的左孩子 
    15. 	// pSubLR: pParent左孩子的右孩子，注意：该
    16. 	PNode pSubL = pParent->_pLeft; 
    17. 	PNode pSubLR = pSubL->_pRight; 
    18. 	// 旋转完成之后，30的右孩子作为双亲的左孩子 
    19. 	pParent->_pLeft = pSubLR; 
    20. 	// 如果30的左孩子的右孩子存在，更新亲双亲 
    21. 	if(pSubLR)
    22. 		pSubLR->_pParent = pParent; 
    23. 	// 60 作为 30的右孩子
    24. 	pSubL->_pRight = pParent;
    25.  
    26. 	// 因为60可能是棵子树，因此在更新其双亲前必须先保存60的双亲
    27. 	PNode pPParent = pParent->_pParent;
    28.  
    29. 	// 更新60的双亲
    30. 	pParent->_pParent = pSubL;
    31.  
    32. 	// 更新30的双亲
    33. 	pSubL->_pParent = pPParent;
    34. 	// 如果60是根节点，根新指向根节点的指针
    35. 	if (NULL == pPParent)
    36. 	{
    37. 		_pRoot = pSubL;
    38. 		pSubL->_pParent = NULL;
    39. 	}
    40. 	else
    41. 	{
    42. 		// 如果60是子树，可能是其双亲的左子树，也可能是右子树
    43. 		if (pPParent->_pLeft == pParent)
    44. 			pPParent->_pLeft = pSubL;
    45. 		else
    46. 			pPParent->_pRight = pSubL;
    47. 	}
    48. 	// 根据调整后的结构更新部分节点的平衡因子
    49. 	pParent->_bf = pSubL->_bf = 0;
    50. }

     2. 新节点插入较高右子树的右侧---右右：左单旋

    实现及情况考虑可参考右单旋。

    3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

    将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再
    考虑平衡因子的更新。 
    1. // 旋转之前，60的平衡因子可能是-1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整
    2. void _RotateLR(PNode pParent) 
    3. {
    4. 	PNode pSubL = pParent->_pLeft;
    5. 	PNode pSubLR = pSubL->_pRight;
    6.  
    7. 	// 旋转之前，保存pSubLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节
    8. 	点的平衡因子
    9. 		int bf = pSubLR->_bf;
    10.  
    11. 	// 先对30进行左单旋
    12. 	_RotateL(pParent->_pLeft);
    13.  
    14. 	// 再对90进行右单旋
    15. 	_RotateR(pParent);
    16. 	if (1 == bf)
    17. 		pSubL->_bf = -1;
    18. 	else if (-1 == bf)
    19. 		pParent->_bf = 1;
    20. }

    4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

    参考右左双旋。
    总结：
    假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
    1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
    当pSubR的平衡因子为1时，执行左单旋
    当pSubR的平衡因子为-1时，执行右左双旋
    2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
    • 当pSubL的平衡因子为-1是，执行右单旋
    • 当pSubL的平衡因子为1时，执行左右双旋
    旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

     1.5 AVL树的验证

    AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
    1. 验证其为二叉搜索树
    如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
    2. 验证其为平衡树
    • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
    • 节点的平衡因子是否计算正确 

    1. int _Height(PNode pRoot); 
    2. bool _IsBalanceTree(PNode pRoot) 
    3. { 
    4. 	// 空树也是AVL树 
    5. 	if (nullptr == pRoot) return true; 
    6. 	// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差 
    7. 	int leftHeight = _Height(pRoot->_pLeft); 
    8. 	int rightHeight = _Height(pRoot->_pRight);
    9. 	int diff = rightHeight - leftHeight;
    10. 	// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
    11.     // pRoot平衡因子的绝对值超过1，则一定不是AVL树
    12. 	if (diff != pRoot->_bf || (diff > 1 || diff < -1))
    13. 		return false;
    14. 	// pRoot的左和右如果都是AVL树，则该树一定是AVL树
    15. 	return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot - > _pRight);
    16. }
    3. 验证用例
    结合上述代码按照以下的数据次序，自己动手画AVL树的创建过程，验证代码
    是否有漏洞。
    • 常规场景1
          {16, 3, 7, 11, 9, 26, 18, 14, 15}
    • 特殊场景2
          {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

    1.6 AVL树的删除(了解)

    因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不 错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
    具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

    1.7 AVL树的性能

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

    2.AVL树的实现：

    通过功能函数的模块化，然后进行封装，实现AVL的数据插入、遍历、树的高度求解、树的平衡判断。在插入数据的过程中，会涉及到树的结构的调整，这就需要借助平衡因子使得调整更加方便。

    2.1功能函数：

    （1）定义AVL树的基本结构：

    （2）Insert函数以及平衡因子bf的调整： （3）左单旋RotateL:

    （4）右单旋RotateR： 

    （5）左右双旋RotateLR： 

    （6）右左双旋RotateRL： （7）遍历（递归版）:

     

    （8）求树的高度：

     

    （9）判断是否为平衡二叉树： 

    （10）测试用例： 

     

    2.2完整源码：

    （1）AVLTree.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. using namespace std;
    11.  
    12. template<class K,class V>
    13. struct AVLTreeNode
    14. {
    15. 	pair _kv;     //key<=>(pair*)->first   value<=>(pair*）->second
    16. 	AVLTreeNode* _left;
    17. 	AVLTreeNode* _right;
    18. 	AVLTreeNode* _parent;
    19.  
    20. 	int _bf; //balance factor  这里定义成右子树-左子树
    21. 	//AVL并无强制规定设计平衡因子，这里选择使用，方便控制平衡
    22.  
    23. 	AVLTreeNode(const pair& kv)
    24. 		:_kv(kv)
    25. 		, _left(nullptr)
    26. 		, _right(nullptr)
    27. 		, _parent(nullptr)
    28. 		, _bf(0)
    29. 	{}
    30. };
    31.  
    32. template<class K,class V>
    33. class AVLTree
    34. {
    35. 	typedef AVLTreeNode Node;
    36. public:
    37. 	//Find
    38. 	//Erase 
    39. 	//插入数据
    40. 	bool Insert(const pair& kv)
    41. 	{
    42. 		//1.先按照搜索树的规则插入数据
    43. 		//2.判断是否遵循平衡规则，若违反，就旋转进行调整
    44. 		if (_root == nullptr)
    45. 		{
    46. 			_root = new Node(kv);
    47. 			_root->_bf = 0;
    48. 			return true;
    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. 		cur = new Node(kv);
    70. 		if (parent->_kv.first < kv.first)
    71. 		{
    72. 			parent->_right = cur;
    73. 		}
    74. 		else
    75. 		{
    76. 			parent->_left = cur;
    77. 		}
    78.  
    79. 		cur->_parent = parent;
    80. 		//更新平衡因子：
    81. 		//插入新结点后：
    82. 		//1.树的高度层次增加，要一直更新到根结点（_root)的bf
    83. 		//2.树的高度不变，只更新当前的parent的bf，就更新完成
    84. 		//3.更新完成后，若违反规则，处理旋转
    85. 		//注：更新bf，parent和cur也会更新
    86. 		//插入结点后，平衡因子的判断、更新
    87. 		while (parent) 
    88. 		{
    89. 			//当前新插入这个结点的parent一定会更新，后面的需要进行判断
    90. 			if (cur == parent->_right)
    91. 			{
    92. 				parent->_bf++;
    93. 			}
    94. 			else
    95. 			{
    96. 				parent->_bf--;
    97. 			}
    98.  
    99. 			// 是否继续更新？
    100. 			if (parent->_bf == 0)      //原来的bf:1 or -1  -> 0  插入节点填上矮的那边
    101. 			{
    102. 				// 高度不变，更新结束
    103. 				break;
    104. 			}
    105. 			else if (parent->_bf == 1 || parent->_bf == -1) 
    106. 			{
    107. 				// 原来的bf:0  -> 1 或 -1  插入节点导致一边变高了
    108. 				// 子树的高度变了，继续更新，这里更新后，parent也变了，后续是否更新要进行判断
    109. 				cur = cur->_parent;
    110. 				parent = parent->_parent;
    111. 			}
    112. 			else if (parent->_bf == 2 || parent->_bf == -2)  
    113. 			{
    114. 				// -1 or 1  -> 2 或 -2     插入节点导致本来高一边又变高了
    115. 				// 子树不平衡 -- 需要旋转处理
    116. 				if (parent->_bf == 2 && cur->_bf == 1)        // 左单旋
    117. 				{
    118. 					RotateL(parent);
    119. 				}
    120. 				else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋
    121. 				{
    122. 					RotateR(parent);
    123. 				}
    124. 				else if (parent->_bf == -2 && cur->_bf == 1)  // 左右双旋
    125. 				{
    126. 					RotateLR(parent);
    127. 				}
    128. 				else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
    129. 				{
    130. 					RotateRL(parent);
    131. 				}
    132.  
    133. 				break;
    134. 			}
    135. 			else
    136. 			{
    137. 				// 插入之前AVL就存在不平衡子树，|平衡因子| >= 2的节点
    138. 				assert(false);
    139. 			}
    140.  
    141. 		}
    142. 		return true;
    143. 	}
    144. private:
    145. 	//1.右边高，向左单旋转
    146. 	void RotateL(Node* parent)
    147. 	{
    148. 		Node* subR = parent->_right;
    149. 		Node* subRL = subR->_left;
    150.  
    151. 		parent->_right = subRL;
    152. 		if (subRL)
    153. 			subRL->_parent = parent;
    154.  
    155. 		Node* ppNode = parent->_parent;
    156.  
    157. 		subR->_left = parent;
    158. 		parent->_parent = subR;
    159.  
    160. 		if (parent == _root)
    161. 		{
    162. 			_root = subR;
    163. 			_root->_parent = nullptr;
    164. 		}
    165. 		else
    166. 		{
    167. 			if (parent == ppNode->_left)
    168. 			{
    169. 				ppNode->_left = subR;
    170. 			}
    171. 			else
    172. 			{
    173. 				ppNode->_right = subR;
    174. 			}
    175.  
    176. 			subR->_parent = ppNode;
    177. 		}
    178. 		// 更新平衡因子
    179. 		parent->_bf = 0;
    180. 		subR->_bf = 0;
    181. 	}
    182. 	//2.左边高，向右单旋转
    183. 	void RotateR(Node* parent)
    184. 	{
    185. 		Node* subL = parent->_left;
    186. 		Node* subLR = subL->_right;
    187.  
    188. 		parent->_left = subLR;
    189. 		if (subLR)
    190. 			subLR->_parent = parent;
    191.  
    192. 		Node* ppNode = parent->_parent;
    193.  
    194. 		subL->_right = parent;
    195. 		parent->_parent = subL;
    196.  
    197. 		if (parent == _root)
    198. 		{
    199. 			_root = subL;
    200. 			_root->_parent = nullptr;
    201. 		}
    202. 		else
    203. 		{
    204. 			if (ppNode->_left == parent)
    205. 			{
    206. 				ppNode->_left = subL;
    207. 			}
    208. 			else
    209. 			{
    210. 				ppNode->_right = subL;
    211. 			}
    212. 			subL->_parent = ppNode;
    213. 		}
    214.  
    215. 		subL->_bf = parent->_bf = 0;
    216. 		
    217. 	}
    218. 	//3.左右双旋
    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. 	//4.右左双旋
    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. 		if (bf == 0)
    264. 		{
    265. 			subRL->_bf = 0;
    266. 			parent->_bf = 0;
    267. 			subR->_bf = 0;
    268. 		}
    269. 		else if (bf == 1)
    270. 		{
    271. 			subRL->_bf = 0;
    272. 			parent->_bf = -1;
    273. 			subR->_bf = 0;
    274. 		}
    275. 		else if (bf == -1)
    276. 		{
    277. 			subRL->_bf = 0;
    278. 			parent->_bf = 0;
    279. 			subR->_bf = 1;
    280. 		}
    281. 		else
    282. 		{
    283. 			// subLR->_bf旋转前就有问题
    284. 			assert(false);
    285. 		}
    286. 	}
    287. 	//中序遍历（递归版）
    288. 	void _InOrder(Node* root)
    289. 	{
    290. 		if (root == nullptr)
    291. 			return;
    292.  
    293. 		_InOrder(root->_left);
    294. 		cout << root->_kv.first << " ";
    295. 		_InOrder(root->_right);
    296. 	}
    297. 	//前序遍历（递归版）
    298. 	void _PrevOrder(Node* root)
    299. 	{
    300. 		if (root == nullptr)
    301. 			return;
    302.  
    303. 		cout << root->_kv.first << " ";
    304. 		_PrevOrder(root->_left);
    305. 		_PrevOrder(root->_right);
    306. 	}
    307. 	//后序遍历（递归版）
    308. 	void _PostOrder(Node* root)
    309. 	{
    310. 		if (root == nullptr)
    311. 			return;
    312.  
    313. 		_PostOrder(root->_left);
    314. 		_PostOrder(root->_right);
    315. 		cout << root->_kv.first << " ";
    316.  
    317. 	}
    318. 	//求树的高度
    319. 	int _Height(Node* root)
    320. 	{
    321. 		if (root == nullptr)
    322. 			return 0;
    323.  
    324. 		int lh = _Height(root->_left);
    325. 		int rh = _Height(root->_right);
    326.  
    327. 		return lh > rh ? lh + 1 : rh + 1;
    328. 	}
    329. 	//判断是否为平衡树
    330. 	bool _IsBalanceTree(Node* root)
    331. 	{
    332. 		// 空树也是AVL树
    333. 		if (nullptr == root)
    334. 			return true;
    335.  
    336. 		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
    337. 		int leftHeight = _Height(root->_left);
    338. 		int rightHeight = _Height(root->_right);
    339. 		int diff = rightHeight - leftHeight;
    340.  
    341. 		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
    342. 		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
    343. 		if (abs(diff) >= 2)
    344. 		{
    345. 			cout << root->_kv.first << "节点平衡因子异常！" << endl;
    346. 			return false;
    347. 		}
    348.  
    349. 		if (diff != root->_bf)
    350. 		{
    351. 			cout << root->_kv.first << "节点平衡因子不符合实际！" << endl;
    352. 			return false;
    353. 		}
    354.  
    355. 		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
    356. 		return _IsBalanceTree(root->_left)
    357. 			&& _IsBalanceTree(root->_right);
    358. 	}
    359. public:
    360. 	//1.中序遍历（递归版）
    361. 	void InOrder()
    362. 	{
    363. 		_InOrder(_root);
    364. 		cout << endl;
    365. 	}
    366. 	//2.前序遍历（递归版）
    367. 	void PrevOrder()
    368. 	{
    369. 		_PrevOrder(_root);
    370. 		cout << endl;
    371. 	}
    372. 	//3.后序序遍历（递归版）
    373. 	void PostOrder()
    374. 	{
    375. 		_PostOrder(_root);
    376. 		cout << endl;
    377. 	}
    378. 	//4.层序遍历
    379. 	vectorint>> levelOrder()
    380. 	{
    381. 		vectorint>> vv;
    382. 		if (_root == nullptr)
    383. 			return vv;
    384.  
    385. 		queue q;
    386. 		int levelSize = 1;
    387. 		q.push(_root);
    388.  
    389. 		while (!q.empty())
    390. 		{
    391. 			// levelSize控制一层一层出
    392. 			vector<int> levelV;
    393. 			while (levelSize--)
    394. 			{
    395. 				Node* front = q.front();
    396. 				q.pop();
    397. 				levelV.push_back(front->_kv.first);
    398. 				if (front->_left)
    399. 					q.push(front->_left);
    400.  
    401. 				if (front->_right)
    402. 					q.push(front->_right);
    403. 			}
    404. 			vv.push_back(levelV);
    405. 			for (auto e : levelV)
    406. 			{
    407. 				cout << e << " ";
    408. 			}
    409. 			cout << endl;
    410.  
    411. 			// 上一层出完，下一层就都进队列
    412. 			levelSize = q.size();
    413. 		}
    414.  
    415. 		return vv;
    416. 	}
    417.  
    418. 	bool IsBalanceTree()
    419. 	{
    420. 		return _IsBalanceTree(_root);
    421. 	}
    422.  
    423. 	int Height()
    424. 	{
    425. 		return _Height(_root);
    426. 	}
    427. private:
    428. 	Node* _root = nullptr;
    429. };

    （2）test.cpp：

    1. #include"AVLTree.h"
    2. void TestAVLTree1()
    3. {
    4. 	AVLTree<int, int> t;
    5. 	t.Insert(make_pair(1, 1));
    6. 	t.Insert(make_pair(2, 2));
    7. 	t.Insert(make_pair(4, 3));
    8. 	t.Insert(make_pair(4, 4));
    9. 	
    10. }
    11. void TestAVLTree2()
    12. {
    13. 	int a[] = { 5,3,7,1,4,6,8,0,2,9 };
    14. 	AVLTree<int, int> t;
    15. 	for (auto e : a)
    16. 	{
    17. 		t.Insert(make_pair(e, e));
    18. 	}
    19. 	cout << endl;
    20. 	t.levelOrder();
    21. 	t.Insert(make_pair(10,10));
    22. 	t.Insert(make_pair(11,11));
    23. 	t.levelOrder();
    24.  
    25. }
    26. void TestAVLTree3()
    27. {
    28. 	//使用随机值测试
    29. 	const size_t N = 100;
    30. 	vector<int> v;
    31. 	v.reserve(N);
    32. 	srand(time(0));
    33. 	for (size_t i = 0; i < N; ++i)
    34. 	{
    35. 		v.push_back(rand());
    36. 	}
    37.  
    38. 	AVLTree<int, int> t;
    39. 	for (auto e : v)
    40. 	{
    41. 		t.Insert(make_pair(e, e));
    42. 	}
    43.  
    44. 	t.levelOrder();
    45. 	cout << endl;
    46. }
    47. void TestAVLTree4()
    48. {
    49.  
    50. 	//使用有序测试
    51. 	const size_t N = 20;  //测试N个数据
    52. 	vector<int> v;
    53. 	v.reserve(N);
    54. 	srand(time(0));
    55. 	for (size_t i = 0; i < N; ++i)
    56. 	{
    57. 		//v.push_back(rand());
    58. 		v.push_back(i);
    59. 	}
    60.  
    61. 	AVLTree<int, int> t;
    62. 	for (auto e : v)
    63. 	{
    64. 		t.Insert(make_pair(e, e));
    65. 	}
    66.  
    67. 	//t.levelOrder();
    68. 	//t.InOrder();
    69. 	//t.PrevOrder();
    70. 	//t.PostOrder();
    71. 	cout << "是否平衡?(返回值1代表是，返回值0代表不是）:" << t.IsBalanceTree() << endl;
    72. 	cout << "高度:" << t.Height() << endl;
    73. 	cout << endl;
    74. }
    75. void TestAVLTree5()
    76. {
    77. 	int a[] = { 5,3,7,1,4,6,8,0,2,9 };
    78. 	//int a[] = {0,1,2,3,4,5,6,7,8,9 };
    79. 	//int a[] = { 1,1,1,1,1,1,1,1,1 };
    80.  
    81. 	AVLTree<int, int> t;
    82. 	for (auto e : a)
    83. 	{
    84. 		t.Insert(make_pair(e, e));
    85. 	}
    86. 	
    87. 	t.levelOrder();
    88. 	cout << "是否为平衡树?(1：是  0：不是）:" << t.IsBalanceTree() << endl;
    89. 	cout << "树的高度:" << t.Height() << endl;
    90. 	cout << endl;
    91. 	t.Insert(make_pair(10, 10));
    92. 	t.Insert(make_pair(11, 11));
    93. 	
    94. 	t.levelOrder();
    95. 	cout << endl;
    96. 	//t.InOrder();
    97. 	//t.PrevOrder();
    98. 	//t.PostOrder();
    99. 	cout << "是否为平衡树?(1：是  0：不是）:" << t.IsBalanceTree() << endl;
    100. 	cout << "树的高度:" << t.Height() << endl;
    101. 	cout << endl;
    102. }
    103. int main()
    104. {
    105. 	//TestAVLTree1();
    106. 	//TestAVLTree2();
    107. 	TestAVLTree3();
    108. 	//TestAVLTree4();
    109. 	//TestAVLTree5();
    110.  
    111. 	return 0;
    112. }

    2.3总结：

    通过上述过程，实现了对Insert过程中对二叉树调整、判断等。而AVL树还有Find、Erase等操作，由于难度较大，具体实现可参考教材或其他资料。

    这里的AVL借助了平衡因子使得二叉树结构的判断以及调整更加方便，遇到难以理解的过程要画图分析或编译器调试。

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

  • 相关阅读:
    程序员如何运营好博客平台
    Unity优化（1）——合并Mesh
    系统运维（零）：安装系统时挂载点设置不当导致的麻烦
    Ceph文件系统
    windows服务器证书算法升级
    WPF handyControl 学习样例
    Android的PendingIntent.getBroadcast()PendingIntent.FLAG_IMMUTABLE问题
    独立产品灵感周刊 DecoHack #039 - 制作自己的音乐墙
    Vue - 列表拖曳排序 / 鼠标拖动改变顺序排列高效简洁组件（支持PC端与移动端触屏拖动，也可在滚动条内排序自动滚动，流畅丝滑无 BUG）
    CSS中去掉li前面的圆点方法
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126306455