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

    目录

    AVL树的概念及结构

    概念

    结构

    AVL树的插入

    右旋转

    左旋转

    左右双旋

    右左旋转 

    AVL树的删除 

    插入与删除的总结 

    AVL树的基本操作

    构造

    析构

    = 重载

    [ ] 重载

    中序遍历

    判断一棵树是否为AVL树

    代码

    AVL树的概念及结构

    概念

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

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

       AVL树有以下性质：

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

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

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

    结构

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

    AVL树的插入

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

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

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

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

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

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

    右旋转

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

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

    左旋转

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

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

    左右双旋

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

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

    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结点为轴。

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

    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树的删除 

    第一步：先找到要删除的结点

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

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

    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的左孩子---右左双旋

    插入与删除的总结 

    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. 		pairbool> ret = Insert(make_pair(key,V()));
    4. 		return (ret.first)->_kv.second;
    5. 	}

    中序遍历

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

    判断一棵树是否为AVL树

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

    代码

    1. // .hpp
    2. #pragma once
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. template <class K,class V>
    8. struct AVLTreeNode
    9. {
    10. 	short _bf; // 平衡因子---记录其左右子树的高度差（右子树高度减左子树高度）
    11.  
    12. 	struct AVLTreeNode* _parent; // 记录其双亲的地址
    13. 	struct AVLTreeNode* _left; // 记录其左孩子的地址
    14. 	struct AVLTreeNode* _right; // 记录其右孩子的地址
    15.  
    16. 	pair _kv; // kv值
    17.  
    18. 	AVLTreeNode(const pair& 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 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 <
    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. 		pairbool> 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. 	pairbool> Insert(const pair& 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& kv)
    455. 	{
    456. 		if (_root == nullptr)
    457. 		{
    458. 			return false;
    459. 		}
    460.  
    461. 		Node* prev = _root;
    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 == _root)
    481. 					{
    482. 						_root = curr->_right;
    483. 						if (curr->_right)
    484. 						{
    485. 							curr->_right->_parent = _root;
    486. 						}
    487. 						delete curr;
    488. 						return true;
    489. 					}
    490. 					else
    491. 					{
    492. 						UpdateBF(prev, curr);
    493.  
    494. 						if (prev->_left == curr)
    495. 						{
    496. 							prev->_left = curr->_right;
    497. 							if (curr->_right)
    498. 							{
    499. 								curr->_right->_parent = prev->_left;
    500. 							}
    501. 						}
    502. 						else
    503. 						{
    504. 							prev->_right = curr->_right;
    505. 							if (curr->_right)
    506. 							{
    507. 								curr->_right->_parent = prev->_right;
    508. 							}
    509. 						}
    510. 						delete curr;
    511. 						return true;
    512. 					}
    513. 					
    514. 				}
    515. 				else if (curr->_right == nullptr)
    516. 				{
    517. 					if (prev == _root)
    518. 					{
    519. 						_root = curr->_left;
    520. 						if (curr->_left)
    521. 						{
    522. 							curr->_left->_parent = _root;
    523. 						}
    524. 						delete curr;
    525. 						return true;
    526. 					}
    527. 					else
    528. 					{
    529. 						UpdateBF(prev, curr);
    530. 						if (prev->_left == curr)
    531. 						{
    532. 							prev->_left = curr->_left;
    533. 							if (curr->_left)
    534. 							{
    535. 								curr->_left->_parent = prev->_left;
    536. 							}
    537. 						}
    538. 						else
    539. 						{
    540. 							prev->_right = curr->_left;
    541. 							if (curr->_left)
    542. 							{
    543. 								curr->_left->_parent = prev->_right;
    544. 							}
    545. 						}
    546. 						delete curr;
    547. 						return true;
    548. 					}
    549. 					
    550. 				}
    551. 				else
    552. 				{
    553. 					Node* min = curr->_right;
    554. 					while (min->_left)
    555. 					{
    556. 						min = min->_left;
    557. 					}
    558. 					pair tmp = min->_kv;
    559. 					Erase(tmp);
    560. 					curr->_kv = tmp;
    561. 					return true;
    562. 				}
    563. 			}
    564. 		}
    565.  
    566. 		return false;
    567. 	}
    568.  
    569. 	void InOrder()
    570. 	{
    571. 		_InOrder(_root);
    572. 		cout << endl;
    573. 	}
    574.  
    575. 	Node* Find(const K& key)
    576. 	{
    577. 		Node* curr = _root;
    578. 		while (curr)
    579. 		{
    580. 			if (curr->_kv.first > key)
    581. 			{
    582. 				curr = curr->_left;
    583. 			}
    584. 			else if (curr->_kv.first < key)
    585. 			{
    586. 				curr = curr->_right;
    587. 			}
    588. 			else
    589. 			{
    590. 				return curr;
    591. 			}
    592. 		}
    593. 		return nullptr;
    594. 	}
    595.  
    596. 	int AVLTreeDepth(Node* root)
    597. 	{
    598. 		if (root == nullptr)
    599. 		{
    600. 			return 0;
    601. 		}
    602.  
    603. 		int leftDepth = AVLTreeDepth(root->_left);
    604. 		int rightDepth = AVLTreeDepth(root->_right);
    605.  
    606. 		return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    607. 	}
    608.  
    609. 	bool IsAVLTree()
    610. 	{
    611. 		return _IsAVLTree(_root);
    612. 	}
    613. };

  • 相关阅读:
    Ubuntu下安装anaconda流程
    计算机毕业设计Java江西婺源旅游文化推广系统(源码+系统+mysql数据库+lw文档)
    〖Python APP 自动化测试实战篇②〗 - 大话闲扯 APP 自动化工具的演进史
    Java 中的 void 和 Kotlin 的 Unit
    如何快速定位 dpdk memzone 内存泄露问题？
    Java版分布式微服务云开发架构 Spring Cloud+Spring Boot+Mybatis 电子招标采购系统功能清单
    CSS 伪类选择器 last-child 和 last-of-type 的区别
    概率论与数理统计
    Leetcode.4 寻找两个正序数组的中位数
    我国农业科学数据共享协议
  • 原文地址：https://blog.csdn.net/m0_61433144/article/details/126292579