• AVL树实现

    目录

    ​编辑

    一，AVL树的概念

    二，实现AVL树（部分）

    1.AVL树的节点

    2.AVL数的插入

    1.当根节点为nullptr时要执行如下代码：

    2.当根节点不为nullptr时

    1.当parent的_bf变为0时，parent之前的_bf的大小就是-1或者1如下：

    2.当parent的平衡因子被更新为1或者-1时：

    3.当parent的平衡因子更新后变成-2或者2时

    三，一些其他函数

    四，全部代码

    一，AVL树的概念

    首先我们得先知道AVL树是个啥，AVL树是个啥呢？百度一下你就知道：

    在百度上的概念如上。根据AVL树的概念我们可以总结出AVL树有如下特点：

    1.本身首先是一棵二叉搜索树。

    2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

    二，实现AVL树（部分）

    1.AVL树的节点

     首先我们根据AVL树的特点可以想到的AVL树节点成员有：

    1.因为AVL树还是一棵二叉树，所以AVL树中必有指针left与right，而且还有一个变量表示节点值。

    2.因为二AVL树需要记录高度差，所以在节点内就会有一个变量来记录高度差，这个变量便是平衡因子。并且这个变量的类型是int。

    3.最后为了方便后续操作，我们的节点内还会存放一个指针叫做parent，这个节点指向当前节点的父节点。

    所以写出的节点代码如下：

    1. template <class K,class V>
    2. 	struct AVL_Node//节点
    3. 	{
    4. 		AVL_Node(pair& key)
    5. 			:parent(nullptr)
    6. 			,_left(nullptr)
    7. 			,_right(nullptr)
    8. 			,_bf(0)
    9. 			,_key(key)
    10. 		{}
    11.  
    12. 		AVL_Node* parent;//父节点指针
    13. 		AVL_Node* _left;//左孩子指针
    14. 		AVL_Node* _right;//右孩子指针
    15. 		int _bf;//平衡因子
    16. 		pair_key;//val
    17. 	};

    2.AVL数的插入

    AVL树的插入是我们这次实现的重头戏，在插入时要理解的重点内容便是：

    1.插入时的旋转。

    2.平衡因子的调整。

    现在先来写在旋转前的代码：

    1.当根节点为nullptr时要执行如下代码：
    1. if (_root == nullptr)//当根节点为空时
    2. {
    3. 	_root = new AVL_Node(key);
    4. }
    2.当根节点不为nullptr时

    1.先找到插入位置：

    1. AVL_Node* cur = _root;
    2. AVL_Node* parent = cur;
    3. while (cur)
    4. {
    5. if (key < cur->_key)
    6. {
    7.   parent = cur;
    8.   cur = cur->_left;
    9. }
    10. else if (key > cur->_key)
    11. {
    12. 	parent = cur;
    13. 	cur = cur->_right;
    14. }
    15. else
    16. {
    17. 	return false;
    18. }
    19. }

    这段寻找插入位置的代码和二叉搜索树的代码相同。

    2.找到插入位置以后便开始进行插入

    1. cur = new AVL_Node(key);
    2. if (key.first > parent->_key.first)
    3. {
    4. 	parent->_right = cur;
    5. }
    6. 	else
    7. {
    8.   parent->_left = cur;
    9. }
    10.  
    11.  cur->_parent = parent;//更新父节点

    3.调整上一个节点的平衡因子。依据：_bf = 右节点的高度--左节点的高度

    所以当我插入左边时：

    1. if (cur == parent->_left)//左边添加节点，parent的_bf减1
    2. {
    3. 	parent->_bf--;
    4. }

    当我插入右边时：

    1. else if (cur == parent->_right)//右边添加节点，parntt的高度加1
    2. {
    3.   parent->_bf++;
    4. }

    4.根据父节点的_bf的大小来决定是否需要往上调整

    1.当parent的_bf变为0时，parent之前的_bf的大小就是-1或者1如下：

    其实我的parent变成0以后AVL树的高度下降，所以对我的其它节点的平衡因子的大小是没有什么影响的，所以在这种情况下我便可以直接退出：

    1. if (parent->_bf == 0)//子树高度不变不影响整棵树高度
    2. {
    3.   break;
    4. }
    2.当parent的平衡因子被更新为1或者-1时：

    能变更新成这种情况，那我之前的平衡因子一定为0了。这时候，我整棵树的高度肯定是增加了，所以平衡因子必须改变所以代码如下:

    1. else if (parent->_bf == 1 || parent->_bf == -1)//子树高度变了，但是在接受范围内，节点的平衡因子要做调整
    2. {
    3.    cur = parent;
    4.   parent = parent->_parent;
    5. }

    这段代码是不全的，这里只展示了节点向上调整的操作，如果想看整段代码请往后看。

    3.当parent的平衡因子更新后变成-2或者2时

    这个时候就发生异常了，这个时候就要开始旋转了。这个时候的旋转又分为四种：

    1.单纯的右边高

    如以下情况：

    可以看到在插入新的节点以后，树的高度发生了变化并且都是右边的高度高且出现了异常情况。所以这个时候就要发生左旋来调整高度，示意图如下：

    根据这个过程写出如下代码：

    1. void Leftuniflex(AVL_Node* parent)
    2. 	{
    3.         //记录要旋转的节点
    4. 		AVL_Node* subR = parent->_right;
    5. 		AVL_Node* subRL = subR->_left;
    6.  
    7.         //旋转
    8. 		parent->_right = subRL;
    9. 		subR->_left = parent;
    10.  
    11. 		//更新父节点
    12. 		AVL_Node* ppNode = parent->_parent;
    13. 		parent->_parent = subR;
    14. 		if (subRL)
    15. 			subRL->_parent = parent;
    16.  
    17. 		if (parent == _root)
    18. 		{
    19. 			_root = subR;
    20. 		}
    21. 		 
    22. 		subR->_parent = ppNode;
    23.  
    24. 		//更新平衡因子
    25. 		parent->_bf = subR->_bf = 0;
    26. 	}

    因为在示意图里没有显示父节点的更新，所以在这里要注意对于父节点的更新。

    2.单纯的左边高

    如下情况：

    看到这个示意图是否有一种似曾相识的感觉呢？其实单纯的左边高的旋转操作方法和单纯右边高的操作方法一样，只不过旋转的方向改变了。根据示意图写出代码如下：
     

    1. void Rightuniflex(AVL_Node* parent)
    2. 	{
    3. 		//旋转
    4. 		AVL_Node* subL = parent->_left;
    5. 		AVL_Node* subLR = subL->_right;
    6. 		parent->_left = subLR;
    7. 		subL->_right = parent;
    8.  
    9. 		//更新父节点
    10. 		AVL_Node* ppNode = parent->_parent;
    11. 		parent->_parent = subL;
    12. 		if (subLR)
    13. 			subLR->_parent = parent;
    14.  
    15. 		if (parent == _root)
    16. 		{
    17. 			_root = subL;
    18. 		}
    19.  
    20. 		subL->_parent = ppNode;
    21.  
    22. 		//更新平衡因子
    23. 		parent->_bf = subL->_bf = 0;
    24. 	}

    3.右边整体高但是局部矮

    解决方法：1.将整棵AVL树通过右单旋调整成单纯的右边高然后再将整棵树通过左单旋调整成平衡的AVL树。比如如以下情况：

    一，新增节点插入到60的右节点b处，此时60的_bf为-1

    在这种情况下，首先便要以90这个节点为parent进行右单旋让整棵树变成单纯的右边高。如下图所示：

    在转化为单纯的右边高以后，便可以执行第二步了。第二步的操作便是和左旋操作是一样的，如图所示：

    二，新增节点插入到60的右节点c处，此时60的_bf为1

    画出示意图如下：

    然后还是一样的操作将这棵树变成单纯的右边高：

    然后继续执行第二步，也是单纯的左旋操作：

    三，当h为0时，新增节点为60。此时60的_bf = 0

    在这个时候还是一样的操作：先变成单纯的右边高

    然后再操作：

    再右边整体高，局部左边高的节点插入情况便是以上三种。其实这些情况的旋转操作都是一样的但是对应的平衡因子_bf的更新是不一样的。

    根据以上情况写出代码如下：

    1. //右左双旋
    2. 	void RLuniflex(AVL_Node* parent)
    3. 	{
    4. 		AVL_Node* subR = parent->_right;
    5. 		AVL_Node* subRL = subR->_left;
    6. 		int bf = subRL->_bf;
    7.  
    8. 		Rightuniflex(subR);//先局部右旋
    9. 		Leftuniflex(parent);//再整体左旋
    10.  
    11.  
    12. 		//更新平衡因子
    13. 		if (bf == 0)//subRL自己就是新增
    14. 		{
    15. 			parent->_bf = subR->_bf = subRL->_bf = 0;
    16. 		}
    17.  
    18. 		else if (bf == -1)
    19. 		{
    20. 			subR->_bf = 1;
    21. 			parent->_bf = subRL->_bf = 0;
    22. 		}
    23.  
    24. 		else if (bf == 1)
    25. 		{
    26. 			parent->_bf = -1;
    27. 			subRL->_bf = subR->_bf = 0;
    28. 		}
    29. 		else
    30. 		{
    31. 			assert(false);
    32. 		}
    33. 		
    34. 	}

    4.当左边整体高但是右边局部高时：

    在这种情况下的分析方法和《当右边整体高但是左边局部高》的分析方法相同。也分为三步：

    1.现局部左旋让AVL树变成单纯的左边高。

    2.再整体右旋调整树的平衡。

    3.调整平衡因子。

    分析方法和上述代码相同，在这里就直接写代码了：

    1. //左右双旋(狗日的平衡因子，让我搞了半天，哭了)
    2. 	void LRuniflex(AVL_Node* parent)
    3. 	{
    4. 		AVL_Node* subL = parent->_left;
    5. 		AVL_Node* subLR = subL->_right;
    6. 		int bf = subLR->_bf;
    7.  
    8. 		Leftuniflex(subL);//先局部左旋
    9. 		Rightuniflex(parent);//再整体右旋
    10.  
    11.  
    12. 		//更新平衡因子
    13. 		if (bf == 0)//subRL自己就是新增
    14. 		{
    15. 			parent->_bf = subL->_bf = subLR->_bf = 0;
    16. 		}
    17.  
    18. 		else if (bf == -1)
    19. 		{
    20. 			subL->_bf = 0;
    21. 			parent->_bf = 1;
    22. 		    subLR->_bf = 0;
    23. 		}
    24.  
    25. 		else if (bf == 1)
    26. 		{
    27. 			parent->_bf = 0;
    28. 			subLR->_bf = 0;
    29. 			subL->_bf = -1;
    30. 		}
    31. 		else
    32. 		{
    33. 			assert(false);
    34. 		}
    35.  
    36. 	}

    兄弟们在写代码时千万不要和我一样粗心，找bug找了好久！！！！

    三，一些其他函数

    1.中序遍历函数

    1. void Inorder()
    2. {
    3.   _Inorder(_root);
    4. }
    1. void _Inorder(AVL_Node* root)
    2. {
    3. 	if (root == nullptr)
    4. 	{
    5. 		return;
    6. 	}
    7.  
    8.   _Inorder(root->_left);
    9.   cout << root->_key.first << " ";
    10.  _Inorder(root->_right);
    11. }

    记住，AVL树的中序遍历也是一个有序的数列。

    2.判断平衡的函数

    1. int Height(AVL_Node* root)
    2. 		{
    3. 			if (root == nullptr)
    4. 			{
    5. 				return 0;
    6. 			}
    7.  
    8. 			int L = Height(root->_left);
    9. 			int R = Height(root->_right);
    10.  
    11. 			return L > R ? L + 1 : R + 1;
    12. 		}
    13.  
    14. 		bool _Isblance(AVL_Node* root)
    15. 		{
    16. 			if (root == nullptr)
    17. 			{
    18. 				return true;
    19. 			}
    20.  
    21. 			int R = Height(root->_right);
    22. 			int L = Height(root->_left);
    23. 			int bf = root->_bf;
    24.  
    25. 			if (R - L!=bf)
    26. 			{
    27. 				cout << "R-L:" << R - L << endl;
    28. 				cout << root->_key.first << "->" << root->_bf <<"平衡因子异常" << endl;
    29. 				return false;
    30. 			}
    31.  
    32. 			return (abs(R-L)<2)&& _Isblance(root->_left) && _Isblance(root->_right);
    33. 			 
    34. 		}

    四，全部代码

    1. #include
    2. #include
    3. using namespace std;
    4. using std::pair;
    5.  
    6. namespace AVL
    7. {
    8. 	template <class K,class V>
    9. 	struct AVL_Node//节点
    10. 	{
    11. 		AVL_Node(pair& key)
    12. 			:_parent(nullptr)
    13. 			,_left(nullptr)
    14. 			,_right(nullptr)
    15. 			,_bf(0)
    16. 			,_key(key)
    17. 		{}
    18.  
    19. 		AVL_Node* _parent;
    20. 		AVL_Node* _left;
    21. 		AVL_Node* _right;
    22. 		int _bf;
    23. 		pair_key;
    24. 	};
    25.  
    26.  
    27. 	template <class K, class V>
    28. 	class AVL_Tree
    29. 	{
    30. 	public:
    31. 		bool insert( pair key)
    32. 		{
    33. 			if (_root == nullptr)//当根节点为空时
    34. 			{
    35. 				_root = new AVL_Node(key);
    36. 			}
    37.  
    38. 			else//当根节点不为空时
    39. 			{
    40. 				AVL_Node* cur = _root;
    41. 				AVL_Node* parent = cur;
    42. 				while (cur)
    43. 				{
    44. 					if (key.first < cur->_key.first)
    45. 					{
    46. 						parent = cur;
    47. 						cur = cur->_left;
    48. 					}
    49. 					else if (key.first > cur->_key.first)
    50. 					{
    51. 						parent = cur;
    52. 						cur = cur->_right;
    53. 					}
    54. 					else
    55. 					{
    56. 						return false;
    57. 					}
    58. 				}
    59.  
    60. 				cur = new AVL_Node(key);
    61. 				if (key.first > parent->_key.first)
    62. 				{
    63. 					parent->_right = cur;
    64. 				 }
    65. 				else
    66. 				{
    67. 					parent->_left = cur;
    68. 				}
    69.  
    70. 				cur->_parent = parent;
    71.  
    72. 				while (parent)
    73. 				{
    74. 					if (cur == parent->_left)//左边添加节点，parent的高度减1
    75. 					{
    76. 						parent->_bf--;
    77. 					}
    78. 					else if (cur == parent->_right)//右边添加节点，parent的高度加1
    79. 					{
    80. 						parent->_bf++;
    81. 					}
    82.  
    83. 					if (parent->_bf == 0)//子树高度不变不影响整棵树高度
    84. 					{
    85. 						break;
    86. 					}
    87. 					else if (parent->_bf == 1 || parent->_bf == -1)//子树高度变了，但是在接受范围内，节点的平衡因子要做调整
    88. 					{
    89. 						cur = cur->_parent;
    90. 						parent = parent->_parent;
    91. 					}
    92. 					else if (parent->_bf == 2 || parent->_bf == -2)
    93. 					{
    94. 						//Inorder();
    95. 						//出现异常该旋转了
    96. 						//单纯右边高，发生左单旋
    97. 						if (parent->_bf == 2 && cur->_bf == 1)
    98. 						{
    99. 							 Leftuniflex(parent);
    100. 						}
    101. 						//单纯左边高，发生右单旋
    102. 						else if (parent->_bf == -2 && cur->_bf == -1)
    103. 						{
    104. 							 Rightuniflex(parent);
    105.  
    106. 						}
    107. 						//右边整体高，局部矮
    108. 						else if (parent->_bf == 2 && cur->_bf == -1)
    109. 						{
    110. 							RLuniflex(parent);
    111. 						}
    112. 						//左边整体高，局部矮
    113. 						else if (parent->_bf == -2 && cur->_bf == 1)
    114. 						{
    115. 							LRuniflex(parent);
    116. 						}
    117. 					    
    118. 						else
    119. 						{
    120. 							assert(false);
    121. 						}
    122. 						break;
    123. 					}
    124.  
    125. 					else
    126. 					{
    127. 						assert(false);
    128. 					}
    129. 			
    130. 				}
    131. 			}
    132. 				return true;
    133. 	    }
    134.  
    135. 	void Leftuniflex(AVL_Node* parent)
    136. 	{
    137. 		AVL_Node* subR = parent->_right;
    138. 		AVL_Node* subRL = subR->_left;
    139. 		parent->_right = subRL;
    140. 		subR->_left = parent;
    141.  
    142. 		//更新父节点
    143. 		AVL_Node* ppNode = parent->_parent;
    144. 		parent->_parent = subR;
    145. 		if (subRL)
    146. 			subRL->_parent = parent;
    147.  
    148. 		if (parent == _root)
    149. 		{
    150. 			_root = subR;
    151. 		}
    152. 		 
    153. 		else
    154. 		{
    155. 			if (parent == ppNode->_left)
    156. 			{
    157. 				ppNode->_left = subR;
    158. 			}
    159. 			else
    160. 			{
    161. 				ppNode->_right = subR;
    162. 			}
    163. 		}
    164. 		subR->_parent = ppNode;
    165.  
    166. 		//更新平衡因子
    167. 		parent->_bf = subR->_bf = 0;
    168. 	}
    169.  
    170.  
    171. 	void Rightuniflex(AVL_Node* parent)
    172. 	{
    173. 		//旋转
    174. 		AVL_Node* subL = parent->_left;
    175. 		AVL_Node* subLR = subL->_right;
    176. 		parent->_left = subLR;
    177. 		subL->_right = parent;
    178.  
    179. 		//更新父节点
    180. 		AVL_Node* ppNode = parent->_parent;
    181. 		parent->_parent = subL;
    182. 		if (subLR)
    183. 			subLR->_parent = parent;
    184.  
    185. 		if (parent == _root)
    186. 		{
    187. 			_root = subL;
    188. 		}
    189.  
    190. 		else
    191. 		{
    192. 			if (parent == ppNode->_left)
    193. 			{
    194. 				ppNode->_left = subL;
    195. 			}
    196. 			else
    197. 			{
    198. 				ppNode->_right = subL;
    199. 			}
    200. 		}
    201. 		subL->_parent = ppNode;
    202.  
    203. 		//更新平衡因子
    204. 		parent->_bf = subL->_bf = 0;
    205. 	}
    206.  
    207. 	//右左双旋
    208. 	void RLuniflex(AVL_Node* parent)
    209. 	{
    210. 		AVL_Node* subR = parent->_right;
    211. 		AVL_Node* subRL = subR->_left;
    212. 		int bf = subRL->_bf;
    213.  
    214. 		Rightuniflex(subR);//先局部右旋
    215. 		Leftuniflex(parent);//再整体左旋
    216.  
    217.  
    218. 		//更新平衡因子
    219. 		if (bf == 0)//subRL自己就是新增
    220. 		{
    221. 			parent->_bf = subR->_bf = subRL->_bf = 0;
    222. 		}
    223.  
    224. 		else if (bf == -1)
    225. 		{
    226. 			subR->_bf = 1;
    227. 			parent->_bf = subRL->_bf = 0;
    228. 		}
    229.  
    230. 		else if (bf == 1)
    231. 		{
    232. 			parent->_bf = -1;
    233. 			subRL->_bf = subR->_bf = 0;
    234. 		}
    235. 		else
    236. 		{
    237. 			assert(false);
    238. 		}
    239. 		
    240. 	}
    241.  
    242. 	//左右双旋(狗日的平衡因子，让我搞了半天，哭了)
    243. 	void LRuniflex(AVL_Node* parent)
    244. 	{
    245. 		AVL_Node* subL = parent->_left;
    246. 		AVL_Node* subLR = subL->_right;
    247. 		int bf = subLR->_bf;
    248.  
    249. 		Leftuniflex(subL);//先局部左旋
    250. 		Rightuniflex(parent);//再整体右旋
    251.  
    252.  
    253. 		//更新平衡因子
    254. 		if (bf == 0)//subRL自己就是新增
    255. 		{
    256. 			parent->_bf = subL->_bf = subLR->_bf = 0;
    257. 		}
    258.  
    259. 		else if (bf == -1)
    260. 		{
    261. 			subL->_bf = 0;
    262. 			parent->_bf = 1;
    263. 		    subLR->_bf = 0;
    264. 		}
    265.  
    266. 		else if (bf == 1)
    267. 		{
    268. 			parent->_bf = 0;
    269. 			subLR->_bf = 0;
    270. 			subL->_bf = -1;
    271. 		}
    272. 		else
    273. 		{
    274. 			assert(false);
    275. 		}
    276.  
    277. 	}
    278.  
    279.  
    280. 	void Inorder()
    281. 	{
    282. 		_Inorder(_root);
    283. 	}
    284.  
    285. 	void Isblance()
    286. 	{
    287. 		_Isblance(_root);
    288. 	}
    289. 	 
    290.  
    291.  
    292. 	private:
    293.  
    294. 		void _Inorder(AVL_Node* root)
    295. 		{
    296. 			if (root == nullptr)
    297. 			{
    298. 				return;
    299. 			}
    300.  
    301. 			_Inorder(root->_left);
    302. 			cout << root->_key.first << " ";
    303. 			_Inorder(root->_right);
    304. 		}
    305.  
    306. 		int Height(AVL_Node* root)
    307. 		{
    308. 			if (root == nullptr)
    309. 			{
    310. 				return 0;
    311. 			}
    312.  
    313. 			int L = Height(root->_left);
    314. 			int R = Height(root->_right);
    315.  
    316. 			return L > R ? L + 1 : R + 1;
    317. 		}
    318.  
    319. 		bool _Isblance(AVL_Node* root)
    320. 		{
    321. 			if (root == nullptr)
    322. 			{
    323. 				return true;
    324. 			}
    325.  
    326. 			int R = Height(root->_right);
    327. 			int L = Height(root->_left);
    328. 			int bf = root->_bf;
    329.  
    330. 			if (R - L!=bf)
    331. 			{
    332. 				cout << "R-L:" << R - L << endl;
    333. 				cout << root->_key.first << "->" << root->_bf <<"平衡因子异常" << endl;
    334. 				return false;
    335. 			}
    336.  
    337. 			return (abs(R-L)<2)&& _Isblance(root->_left) && _Isblance(root->_right);
    338. 			 
    339. 		}
    340.  
    341. 		AVL_Node* _root = nullptr;
    342. 	};
    343.  
    344. }

     

  • 相关阅读:
    海康威视综合安防管理平台任意文件上传
    Python的输入输出（来自菜鸟教程）
    你不知道的浏览器页面渲染机制
    Multi-granularity Correspondence Learning from Long-term Noisy Videos--论文笔记
    【vue3-element-admin】Husky + Lint-staged + Commitlint + Commitizen + cz-git 配置 Git 提交规范
    资源 | Python可视化系列文章资源(源码+数据)
    【PTA题目】6-20 使用函数判断完全平方数 分数 10
    HTTP 之 options预请求 nginx 解决跨域 postman调试跨域问题
    nvm详解（mac环境nvm安装步骤及踩坑问题）
    外滩大会今日开幕 近20位“两院”院士、诺贝尔奖和图灵奖得主齐聚
  • 原文地址：https://blog.csdn.net/qq_41934502/article/details/134450149