devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构-AVL树（平衡二叉树）

作者：盐析白兔 | 2024-04-30 04:55:11

赞

踩

avl树

目录

AVL树的概念及结构

概念

结构

AVL树的插入

右旋转

左旋转

左右双旋

右左旋转 

AVL树的删除 

插入与删除的总结 

AVL树的基本操作

构造

析构

= 重载

[ ] 重载

中序遍历

判断一棵树是否为AVL树

代码

AVL树的概念及结构

概念

   对于普通二叉搜索树，如果在数据有序或者接近有序时插入删除，二叉搜索树会退化成单支树，也就是类似单链表的结构；因此为了避免普通二叉搜索树的高度增长过快，降低二叉搜索树的效率与性能。

   规定在插入和删除二叉搜索树的结点时，要保证任意结点的左右子树高度差的绝对值不超过1，我们将这样特殊的二叉搜索树称为AVL树（平衡二叉树）。每一个结点中有记录其左右子树高度差的平衡因子，也即平衡因子的值只可能是-1,0,1。（1如果某结点的左子树高度比右子树高度高一则平衡因子为-1，如果某结点的左子树高度比右子树高度低一则平衡因子为1，如果某结点的左子树高度与右子树高度一样则平衡因子为0）。6e47882cdb75476f918055a6f1ec1220.png

   AVL树有以下性质：

1，每个结点的左右子树都是AVL树

2，左子树与右子树的高度差只能为-1，0，1（规定平衡因子等于右子树的高度减左子树的高度）

3，如果AVL树非常平衡，则整体结构接近满二叉树，所以当结点为N个时，其高度为log（2）N

结构

   为了便于更新平衡因子与旋转处理AVL树的链式结构采用三叉链，也就是AVL树的每个结点都包含：双亲结点地址，左孩子地址，右孩子地址，平衡因子，KV数据。6224ef42109345d6af710afc9780fd64.png

AVL树的插入

第一步：按照二叉搜索树的插入操作进行新结点的插入，但需要注意的是要将新插入结点中的_parent指向改为其双亲。d6a878894c824c22a45888a72c5f64a7.png

第二步：更新平衡因子，从插入结点的双亲开始往上更新；如果插入的结点是双亲的右孩子则双亲的平衡因子加一，如果插入的结点是双亲的左孩子则双亲的平衡因子减一；更新过的平衡因子有三种情况：

1，如果平衡因子变为0，则说明原来的平衡因子为-1或者1，也就是原来左右子树的高度差绝对值为1，经过插入新结点，使该结点的左右子树达到平衡，所以无须继续往上更新平衡因子。

2，如果平衡因子变为-1或者1，则说明原来的平衡因子为0，也就是原来左右子树的高度一致，经过插入新结点，使该结点的左右子树的高度差绝对值变为1，所以需要继续往上更新平衡因子。

3，如果平衡因子变为-2或者2，则说明原来的平衡因子为-1或者1，也就是原来左右子树高度差绝对值为1，经过插入新结点，使该结点的左右子树高度差绝对值为2，造成不满足AVL树性质要求需要进行旋转处理。71ed694dc3da4fa39bb05ac3e410f828.png

第三步：旋转处理，使不平衡的AVL树变为平衡的AVL树；造成平衡的AVL树变为不平衡的AVL树的原因有4种，也就是说使不平衡的AVL树变为平衡的AVL树的旋转处理方式也有4种，每一种原因对应一种旋转处理方式。

右旋转

   在A结点的左孩子B的左子树上插入新结点，导致以A为根的子树失去平衡（左子树比右子树高），需要进行右旋转处理c8866d33b36346dd895780f6e5a34e61.png

右旋转的具体操作：先让B结点的_right指向A结点，再让A结点的_left指向原B结点的右子树b。57ba98a0e3514890ba0ff218b3cab7fb.png

5746e220e2974c7999a8de1b16dfa96a.png

左旋转

   在A结点的右孩子B的右子树上插入新结点，导致以A为根的子树失去平衡（左子树比右子树低），需要进行左旋转处理。4d78627a477a441ca960076df3cd5d0c.png

左旋转的具体操作：先让B结点的_left指向A结点，再让A结点的_right指向原B结点的左子树b。4e9057a686884ac38da0831dee45018d.png

149071fff2894e62ad5e1e9aee208cd7.png

左右双旋

   由于在A的左孩子B的右子树上插入新结点，A的平衡因子由-1变为-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转再右旋转。左旋转是以B结点为轴，右旋转是以A结点为轴。5fd064be38ad4c6980e492cc8a72e4ae.png

具体操作：先将A结点的左孩子B的右子树的根节点C向左上旋转提升到B结点的位置，然后把该C结点向右上旋转提升到A结点的位置。93e1ab7e716c4bc2b9e3750524e98077.png

  1. // 左右旋
  2. 	void RotateLR(Node* parrnt)
  3. 	{
  4. 		Node* subL = parrnt->_left;
  5. 		Node* subLR = subL->_right;
  6. 		short bf = subLR->_bf;
  7.  
  8. 		RotateL(parrnt->_left);
  9. 		RotateR(parrnt);
  10.  
  11. 		if (bf == 1)
  12. 		{
  13. 			subLR->_bf = 0;
  14. 			subL->_bf = -1;
  15. 			parrnt->_bf = 0;
  16. 		}
  17. 		else if (bf == -1)
  18. 		{
  19. 			subLR->_bf = 0;
  20. 			subL->_bf = 0;
  21. 			parrnt->_bf = 1;
  22. 		}
  23. 		else if(bf==0)
  24. 		{
  25.  
  26. 			subLR->_bf = 0;
  27. 			subL->_bf = 0;
  28. 			parrnt->_bf = 0;
  29. 		}
  30. 		else
  31. 		{
  32. 			assert(false);
  33. 		}
  34. 	}

右左旋转 

   由于在A的右孩子B的左子树上插入新结点，A的平衡因子由1变为2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转在左旋转。右旋转是以B结点为轴，左旋转是以A结点为轴。8ca2556db2b14b21ad8587483c7b5e7a.png

具体操作：先将A结点的右孩子B的左子树的根节点C向右上旋转提升到B结点的位置，然后把该C结点向左上旋转提升到A结点的位置。38494f6cc8c24369aa8247f45deb94a7.png

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

AVL树的删除 

第一步：先找到要删除的结点78140275f2144466b126fb504fcd582d.png

第二步：按照要删除结点的类型进行分类删除：1，左子树为空   2，右子树为空   3，左右子树都为空   4，左右子树都不为空0f85573ac6e54a6c823f326974dfcf96.png

第三步：更新平衡因子。如果删除的结点在其双亲的左边则双亲的平衡因子++，如果删除的结点在其双亲结点的右边则双亲的平衡因子--。

1，如果更新后parent->_bf==0，说明parent->_bf原来是-1或者1，把高的那边删除掉了，高度变小了，继续往上更新。

2，如果更新后parent->_bf==-1或者parenr->_bf==1，说明parent->_bf原来是0，删除了其左右结点其中的一个，高度没有变，不需要继续往上更新。

3，如果更新后parent->_bf==-2或者parenr->_bf==2，说明AVL树不平衡，需要旋转处理。

第四步：旋转处理。

// 旋转规则(有四种情况):

// firstDepth是parent高度最高的孩子结点，secondDepth是firstDepth高度最后的结点
// 1，如果first是parent的左孩子，second是first的左孩子---右旋转
// 2，如果first是parent的左孩子，second是first的右孩子---左右双旋

// 3，如果first是parent的右孩子，second是first的右孩子---左旋转

// 4，如果first是parent的右孩子，second是first的左孩子---右左双旋

86a5e39870b64ee7a155cfd8da299ea3.png

8d82e9aeb5264073b720d3cd74ac4d25.png

插入与删除的总结 

9b376f7e76b940e9bb904c6f48b3cdde.png

AVL树的基本操作

构造

  1. // 无参构造
  2. AVLTree()
  3. 		:_root(nullptr)
  4. 	{
  5.  
  6. 	}
  1. // 拷贝构造
  2. 	Node* _CopyAVLTree(Node* root, Node* parent)
  3. 	{
  4. 		if (root == nullptr)
  5. 		{
  6. 			return nullptr;
  7. 		}
  8.  
  9. 		Node* newNode = new Node(root->_kv);
  10. 		newNode->_bf = root->_bf;
  11. 		newNode->_parent = parent;
  12. 		newNode->_left = _CopyAVLTree(root->_left,newNode);
  13. 		newNode->_right = _CopyAVLTree(root->_right,newNode);
  14.  
  15. 		return newNode;
  16. 	}
  17.  
  18. AVLTree(const AVLTree& t)
  19. 	{
  20. 		_root=_CopyAVLTree(t._root, nullptr);
  21. 	}

析构

  1. //析构
  2. ~AVLTree()
  3. 	{
  4. 		_Destroy(_root);
  5. 		_root = nullptr;
  6. 	}
  7.  
  8. //销毁
  9. 	void _Destroy(Node* root)
  10. 	{
  11. 		if (root == nullptr)
  12. 		{
  13. 			return;
  14. 		}
  15. 		_Destroy(root->_left);
  16. 		_Destroy(root->_right);
  17. 		delete root;
  18. 	}

= 重载

  1. AVLTree& operator=(AVLTree t)
  2. 	{
  3. 		swap(_root, t._root);
  4. 		return *this;
  5. 	}

[ ] 重载

  1. V& operator[](const K& key)
  2. 	{
  3. 		pair<Node*, bool> ret = Insert(make_pair(key,V()));
  4. 		return (ret.first)->_kv.second;
  5. 	}

中序遍历

  1. void InOrder()
  2. 	{
  3. 		_InOrder(_root);
  4. 		cout << endl;
  5. 	}

e6f272e3b9c64604b8e22454508728fb.png

判断一棵树是否为AVL树

  1. bool IsAVLTree()
  2. 	{
  3. 		return _IsAVLTree(_root);
  4. 	}

99b4290d2dda4f7ab36487340742b263.png

代码

  1. // .hpp
  2. #pragma once
  3. #include <iostream>
  4. #include <cassert>
  5. using namespace std;
  6.  
  7. template <class K,class V>
  8. struct AVLTreeNode
  9. {
  10. 	short _bf; // 平衡因子---记录其左右子树的高度差（右子树高度减左子树高度）
  11.  
  12. 	struct AVLTreeNode<K, V>* _parent; // 记录其双亲的地址
  13. 	struct AVLTreeNode<K, V>* _left; // 记录其左孩子的地址
  14. 	struct AVLTreeNode<K, V>* _right; // 记录其右孩子的地址
  15.  
  16. 	pair<K, V> _kv; // kv值
  17.  
  18. 	AVLTreeNode(const pair<K,V>& kv)
  19. 		:_bf(0)
  20. 		,_parent(nullptr)
  21. 		,_left(nullptr)
  22. 		,_right(nullptr)
  23. 		,_kv(kv)
  24. 	{
  25.  
  26. 	}
  27. };
  28.  
  29. template <class K,class V>
  30. class AVLTree
  31. {
  32. 	typedef struct AVLTreeNode<K, V> Node;
  33. private:
  34. 	Node* _root;
  35.  
  36. 	// 左旋转---左子树低
  37. 	void RotateL(Node* parent) // parent是平衡因子为-2或者2的结点
  38. 	{
  39. 		Node* parentParent = parent->_parent; // 记录其双亲
  40. 		Node* subR = parent->_right; // 记录其右孩子
  41. 		Node* subRL = subR->_left; // 记录其右孩子的左孩子
  42. 		
  43. 		// 让subR的左孩子指向parent，parent的双亲指向subR
  44. 		subR->_left = parent;
  45. 		parent->_parent = subR;
  46.  
  47. 		// 让parent的右孩子指向subR的左孩子
  48. 		parent->_right = subRL;
  49. 		if (subRL) // 如果subRL不为空，则让subR的左孩子的_parent指向parent
  50. 		{
  51. 			subRL->_parent = parent;
  52. 		}
  53.  
  54. 		// 更新parent的双亲结点中的左孩子或者右孩子指向，并更新subR的_parent的指向
  55. 		if (parent == _root)
  56. 		{
  57. 			_root = subR;
  58. 			subR->_parent = nullptr;
  59. 		}
  60. 		else
  61. 		{
  62. 			if (parentParent->_left == parent)
  63. 			{
  64. 				parentParent->_left = subR;
  65. 			}
  66. 			else if(parentParent->_right==parent)
  67. 			{
  68. 				parentParent->_right = subR;
  69. 			}
  70. 			subR->_parent = parentParent;
  71. 		}
  72.  
  73. 		// 更新旋转处理后的平衡因子
  74. 		parent->_bf = 0;
  75. 		subR->_bf = 0;
  76. 	}
  77.  
  78. 	// 右旋转
  79. 	void RotateR(Node* parent) // parent是平衡因子为-2或者2的结点
  80. 	{
  81. 		Node* parentParent = parent->_parent; // 记录其双亲
  82. 		Node* subL = parent->_left; // 记录其左孩子
  83. 		Node* subLR = subL->_right; // 记录其左孩子的右孩子
  84.  
  85. 		// parent的双亲指向subL，subL的右孩子指向parent
  86. 		parent->_parent = subL;
  87. 		subL->_right = parent;
  88.  
  89. 		// parent的左孩子指向subL的右孩子
  90. 		parent->_left = subLR;
  91. 		if (subLR) // 如果subLR不为空，则让subLR的双亲指向parent
  92. 		{
  93. 			subLR->_parent = parent;
  94. 		}
  95.  
  96. 		if (_root == parent) // parent的双亲为空则说明parent是整棵树的根节点
  97. 		{
  98. 			_root = subL; // 让subL当整棵树的根节点
  99. 			subL->_parent = nullptr; // 并让subL的双亲指向空
  100. 		}
  101. 		else // 否则parent是某棵子树的根节点，更新parentParent左孩子或者右孩子的指向
  102. 		{
  103. 			if (parentParent->_left == parent)
  104. 			{
  105. 				parentParent->_left = subL;
  106. 			}
  107. 			else
  108. 			{
  109. 				parentParent->_right = subL;
  110. 			}
  111. 			subL->_parent = parentParent; // 更新subL双亲的指向
  112. 		}
  113.  
  114. 		parent->_bf = subL->_bf = 0; // 经过旋转更新平衡因子
  115. 	}
  116.  
  117. 	// 左右旋
  118. 	void RotateLR(Node* parrnt)
  119. 	{
  120. 		Node* subL = parrnt->_left;
  121. 		Node* subLR = subL->_right;
  122. 		short bf = subLR->_bf;
  123.  
  124. 		RotateL(parrnt->_left);
  125. 		RotateR(parrnt);
  126.  
  127. 		if (bf == 1)
  128. 		{
  129. 			subLR->_bf = 0;
  130. 			subL->_bf = -1;
  131. 			parrnt->_bf = 0;
  132. 		}
  133. 		else if (bf == -1)
  134. 		{
  135. 			subLR->_bf = 0;
  136. 			subL->_bf = 0;
  137. 			parrnt->_bf = 1;
  138. 		}
  139. 		else if(bf==0)
  140. 		{
  141.  
  142. 			subLR->_bf = 0;
  143. 			subL->_bf = 0;
  144. 			parrnt->_bf = 0;
  145. 		}
  146. 		else
  147. 		{
  148. 			assert(false);
  149. 		}
  150. 	}
  151.  
  152. 	// 右左旋
  153. 	void RotateRL(Node* parent)
  154. 	{
  155. 		Node* subR = parent->_right;
  156. 		Node* subRL = subR->_left;
  157. 		short bf = subRL->_bf;
  158.  
  159. 		RotateR(parent->_right);
  160. 		RotateL(parent);
  161.  
  162. 		if (bf == 1)
  163. 		{
  164. 			subRL->_bf = 0;
  165. 			subR->_bf = 0;
  166. 			parent->_bf = -1;
  167. 		}
  168. 		else if (bf==-1)
  169. 		{
  170. 			subRL->_bf = 0;
  171. 			subR->_bf = 1;
  172. 			parent->_bf = 0;
  173. 		}
  174. 		else if(bf==0)
  175. 		{
  176. 			subRL->_bf = 0;
  177. 			subR->_bf = 0;
  178. 			parent->_bf = 0;
  179. 		}
  180. 		else
  181. 		{
  182. 			assert(false);
  183. 		}
  184. 	}
  185.  
  186. 	// parent为删除结点的双亲，child为删除的结点
  187. 	void UpdateBF(Node* parent,Node* child)
  188. 	{
  189. 		while (parent != nullptr)
  190. 		{
  191. 			if (parent->_left == child)
  192. 			{
  193. 				parent->_bf++;
  194. 			}
  195. 			else if (parent->_right == child)
  196. 			{
  197. 				parent->_bf--;
  198. 			}
  199.  
  200. 			// 检查平衡因子是否异常
  201. 			if (parent->_bf == 0)
  202. 			{
  203. 				child = parent;
  204. 				parent = parent->_parent;
  205. 			}
  206. 			else if (parent->_bf == 1 || parent->_bf == -1)
  207. 			{
  208. 				break;
  209. 			}
  210. 			else if (parent->_bf == 2 || parent->_bf == -2)
  211. 			{
  212. 				// 求出平衡因子异常结点的左右子树中高的那一棵子树
  213. 				Node* firstDepth = parent->_left;
  214. 				int maxDepth = AVLTreeDepth(parent->_left);
  215. 				int minDepth = AVLTreeDepth(parent->_right);
  216. 				if (maxDepth < minDepth)
  217. 				{
  218. 					firstDepth = parent->_right;
  219. 				}
  220.  
  221. 				// 求出firstDepth结点的左右子树中高的那一棵子树
  222. 				Node* secondDepth = firstDepth->_left;
  223. 				maxDepth = AVLTreeDepth(firstDepth->_left);
  224. 				minDepth = AVLTreeDepth(firstDepth->_right);
  225. 				if (maxDepth < minDepth)
  226. 				{
  227. 					secondDepth = firstDepth->_right;
  228. 				}
  229.  
  230. 				// 旋转规则(有四种情况):
  231. 				// firstDepth是parent高度最高的孩子结点，secondDepth是firstDepth高度最后的结点
  232. 				// 1，如果first是parent的左孩子，second是first的左孩子---右旋转
  233. 				// 2，如果first是parent的左孩子，second是first的右孩子---左右双旋
  234. 				// 3，如果first是parent的右孩子，second是first的右孩子---左旋转
  235. 				// 4，如果first是parent的右孩子，second是first的左孩子---右左双旋
  236. 				if (parent->_left == firstDepth)
  237. 				{
  238. 					if (firstDepth->_left == secondDepth)
  239. 					{
  240. 						RotateR(parent);
  241. 					}
  242. 					else if (firstDepth->_right == secondDepth)
  243. 					{
  244. 						RotateLR(parent);
  245. 					}
  246. 				}
  247. 				else if (parent->_right == firstDepth)
  248. 				{
  249. 					if (firstDepth->_left == secondDepth)
  250. 					{
  251. 						RotateRL(parent);
  252. 					}
  253. 					else if (firstDepth->_right == secondDepth)
  254. 					{
  255. 						RotateL(parent);
  256. 					}
  257. 				}
  258. 				break;
  259. 			}
  260. 			else
  261. 			{
  262. 				assert(false);
  263. 			}
  264. 		}
  265. 	}
  266.  
  267. 	void _InOrder(Node* root)
  268. 	{
  269. 		if (root == nullptr)
  270. 		{
  271. 			return;
  272. 		}
  273.  
  274. 		_InOrder(root->_left);
  275.  
  276. 		cout << " K:" << root->_kv.first << " V:" << root->_kv.second << " bf:" << root->_bf <<endl;
  277.  
  278. 		_InOrder(root->_right);
  279. 	}
  280.  
  281. 	// 判断是否为AVL树
  282. 	bool _IsAVLTree(Node* root)
  283. 	{
  284. 		if (root == nullptr)
  285. 		{
  286. 			return true;
  287. 		}
  288.  
  289. 		int left = AVLTreeDepth(root->_left);
  290. 		int right = AVLTreeDepth(root->_right);
  291.  
  292. 		return abs(left - right) < 2 && _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
  293. 	}
  294.  
  295. 	// 拷贝构造
  296. 	Node* _CopyAVLTree(Node* root, Node* parent)
  297. 	{
  298. 		if (root == nullptr)
  299. 		{
  300. 			return nullptr;
  301. 		}
  302.  
  303. 		Node* newNode = new Node(root->_kv);
  304. 		newNode->_bf = root->_bf;
  305. 		newNode->_parent = parent;
  306. 		newNode->_left = _CopyAVLTree(root->_left,newNode);
  307. 		newNode->_right = _CopyAVLTree(root->_right,newNode);
  308.  
  309. 		return newNode;
  310. 	}
  311.  
  312. 	//销毁
  313. 	void _Destroy(Node* root)
  314. 	{
  315. 		if (root == nullptr)
  316. 		{
  317. 			return;
  318. 		}
  319. 		_Destroy(root->_left);
  320. 		_Destroy(root->_right);
  321. 		delete root;
  322. 	}
  323.  
  324. public:
  325. 	AVLTree()
  326. 		:_root(nullptr)
  327. 	{
  328.  
  329. 	}
  330.  
  331. 	AVLTree(const AVLTree& t)
  332. 	{
  333. 		_root=_CopyAVLTree(t._root, nullptr);
  334. 	}
  335.  
  336. 	~AVLTree()
  337. 	{
  338. 		_Destroy(_root);
  339. 		_root = nullptr;
  340. 	}
  341.  
  342. 	V& operator[](const K& key)
  343. 	{
  344. 		pair<Node*, bool> ret = Insert(make_pair(key,V()));
  345. 		return (ret.first)->_kv.second;
  346. 	}
  347.  
  348. 	AVLTree& operator=(AVLTree t)
  349. 	{
  350. 		swap(_root, t._root);
  351. 		return *this;
  352. 	}
  353.  
  354. 	pair<Node*,bool> Insert(const pair<K, V>& kv)
  355. 	{
  356. 		if (_root == nullptr) // 若AVL为空树，则直接插入
  357. 		{
  358. 			_root = new Node(kv);
  359. 			return make_pair(_root,true);
  360. 		}
  361.  
  362. 		Node* prev = nullptr; // 记录插入结点所在路径的最后一个结点
  363. 		Node* curr = _root; // 引导prev走到最后一个结点
  364.  
  365. 		// 寻找插入位置
  366. 		while (curr)
  367. 		{ 
  368. 			if (curr->_kv.first > kv.first) // 要插入的值比较小，往左走
  369. 			{
  370. 				prev = curr;
  371. 				curr = curr->_left;
  372. 			}
  373. 			else if (curr->_kv.first < kv.first) // 要插入的值比根结点的值大，往右走
  374. 			{
  375. 				prev = curr;
  376. 				curr = curr->_right;
  377. 			}
  378. 			else // 要插入的值比根结点的值大，则插入失败
  379. 			{
  380. 				return make_pair(curr,false);
  381. 			}
  382. 		}
  383.  
  384. 		// 开始插入
  385. 		curr = new Node(kv);
  386. 		Node* ret = curr;
  387. 		if (prev->_kv.first > kv.first) // 左插入 
  388. 		{
  389. 			prev->_left = curr;
  390. 			curr->_parent = prev; // 
  391. 		}
  392. 		else if (prev->_kv.first < kv.first) // 右插入
  393. 		{
  394. 			prev->_right = curr;
  395. 			curr->_parent = prev; // 
  396. 		}
  397.  
  398. 		// 更新平衡因子---将新插入结点curr的祖先的平衡因子更新
  399. 		// while(curr!=_root)
  400. 		while (prev != nullptr)
  401. 		{
  402. 			if (prev->_left == curr)
  403. 			{
  404. 				prev->_bf--; // 如果是往其左子树插入，则_bf--;
  405. 			}
  406. 			else if (prev->_right == curr)
  407. 			{
  408. 				prev->_bf++; // 如果是往其右子树插入，则_bf++;
  409. 			}
  410.  
  411. 			if (prev->_bf == 0) // 左右子树达到平衡，不需要继续往上更新平衡因子
  412. 			{
  413. 				break;
  414. 			}
  415. 			else if (prev->_bf == 1 || prev->_bf == -1) // 需要继续往上更新平衡因子
  416. 			{
  417. 				curr = prev;
  418. 				prev = prev->_parent;
  419. 			}
  420. 			else if (prev->_bf == 2 || prev->_bf == -2) // 左右子树不平衡，需要继续旋转调整
  421. 			{
  422. 				if (prev->_bf == 2)
  423. 				{
  424. 					if (curr->_bf == 1) // 右子树高---右结点的右子树上插入
  425. 					{
  426. 						RotateL(prev); // 左旋转
  427. 					}
  428. 					else if (curr->_bf == -1) // 右子树高---右结点的左子树上插入
  429. 					{
  430. 						RotateRL(prev); // 先右旋再左旋
  431. 					}
  432. 				}
  433. 				else
  434. 				{
  435. 					if (curr->_bf == 1) // 左子树高---左结点的右子树上插入
  436. 					{
  437. 						RotateLR(prev); // 先左旋再右旋
  438. 					}
  439. 					else if (curr->_bf == -1) // 左子树高---左结点的左子树上插入
  440. 					{
  441. 						RotateR(prev);
  442. 					}
  443. 				}
  444. 				break;
  445. 			}
  446. 			else
  447. 			{
  448. 				assert(false);
  449. 			}
  450. 		}
  451. 		return make_pair(ret, true);
  452. 	}
  453.  
  454. 	bool Erase(const pair<K, V>& kv)
  455. 	{
  456. 		if (_root == nullptr) // 如果AVL树为空则不需要删除
  457. 		{
  458. 			return false;
  459. 		}
  460.  
  461. 		Node* prev = nullptr; // 记录删除结点的双亲
  462. 		Node* curr = _root; // 记录删除的结点
  463.  
  464. 		while (curr) // 寻找要删除的结点
  465. 		{
  466. 			if (curr->_kv.first > kv.first) // 往左寻找
  467. 			{
  468. 				prev = curr;
  469. 				curr = curr->_left;
  470. 			}
  471. 			else if (curr->_kv.first < kv.first) // 往右寻找
  472. 			{
  473. 				prev = curr;
  474. 				curr = curr->_right;
  475. 			}
  476. 			else // 找到了---开始删除
  477. 			{
  478. 				if (curr->_left == nullptr) // 删除结点的左子树为空
  479. 				{
  480. 					if (prev == nullptr) // 删除根结点
  481. 					{
  482. 						_root = curr->_right;
  483. 						if (curr->_right)
  484. 						{
  485. 							curr->_right->_parent = nullptr;
  486. 						}		
  487. 					}
  488. 					else // 删除非根结点
  489. 					{
  490. 						UpdateBF(prev, curr); // 删除之前调整平衡因子
  491.  
  492. 						if (prev->_left == curr)
  493. 						{
  494. 							prev->_left = curr->_right;
  495. 							
  496. 						}
  497. 						else
  498. 						{
  499. 							prev->_right = curr->_right;
  500. 							
  501. 						}
  502.  
  503. 						if (curr->_right)
  504. 						{
  505. 							curr->_right->_parent = prev;
  506. 						}		
  507. 					}
  508.  
  509. 					delete curr;
  510. 					return true;
  511. 				}
  512. 				else if (curr->_right == nullptr) // 删除结点的右子树为空
  513. 				{
  514. 					if (prev == nullptr) // 删除根结点，更新_root
  515. 					{
  516. 						_root = curr->_left;
  517. 						if (curr->_left)
  518. 						{
  519. 							curr->_left->_parent = nullptr;
  520. 						}	
  521. 					}
  522. 					else // 删除非根结点
  523. 					{
  524. 						UpdateBF(prev, curr);
  525. 						if (prev->_left == curr)
  526. 						{
  527. 							prev->_left = curr->_left;
  528. 							
  529. 						}
  530. 						else
  531. 						{
  532. 							prev->_right = curr->_left;
  533. 							
  534. 						}
  535.  
  536. 						if (curr->_left)
  537. 						{
  538. 							curr->_left->_parent = prev;
  539. 						}
  540. 					}
  541.  
  542. 					delete curr;
  543. 					return true;
  544. 				}
  545. 				else // 删除结点的左右子树都不为空
  546. 				{
  547. 					Node* min = curr->_right;
  548. 					while (min->_left)
  549. 					{
  550. 						min = min->_left;
  551. 					}
  552. 					pair<K, V> tmp = min->_kv;
  553. 					Erase(tmp); // 替换删除
  554. 					curr->_kv = tmp;
  555. 					return true;
  556. 				}
  557. 			}
  558. 		}
  559. 		return false;
  560. 	}
  561.  
  562. 	void InOrder()
  563. 	{
  564. 		_InOrder(_root);
  565. 		cout << endl;
  566. 	}
  567.  
  568. 	Node* Find(const K& key)
  569. 	{
  570. 		Node* curr = _root;
  571. 		while (curr)
  572. 		{
  573. 			if (curr->_kv.first > key)
  574. 			{
  575. 				curr = curr->_left;
  576. 			}
  577. 			else if (curr->_kv.first < key)
  578. 			{
  579. 				curr = curr->_right;
  580. 			}
  581. 			else
  582. 			{
  583. 				return curr;
  584. 			}
  585. 		}
  586. 		return nullptr;
  587. 	}
  588.  
  589. 	int AVLTreeDepth(Node* root)
  590. 	{
  591. 		if (root == nullptr)
  592. 		{
  593. 			return 0;
  594. 		}
  595.  
  596. 		int leftDepth = AVLTreeDepth(root->_left);
  597. 		int rightDepth = AVLTreeDepth(root->_right);
  598.  
  599. 		return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
  600. 	}
  601.  
  602. 	bool IsAVLTree()
  603. 	{
  604. 		return _IsAVLTree(_root);
  605. 	}
  606. };

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/511504
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号