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

史上最详细的AVL树（含代码实现）_avl树代码

作者：Gausst松鼠会 | 2024-04-26 16:58:09

赞

踩

avl树代码

目录

1.AVL树的相关概念 

2.平衡因子

3.平衡二叉搜索树节点的定义

 4.插入时失衡及其调整

5.AVL树的四种旋转方式

6.AVL树的插入

7.AVL树的删除

8.其他相关函数

1.AVL树的相关概念 

二叉搜索树在一定程度上可以提高搜索效率，但是当序列是有序时：如果所示

 此时二叉搜索树退化成单链表，搜索效率退化为O（N)。为了解决这个问题科学家引入了AVL树，又称平衡搜索二叉树

AVL简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：

  1. 可以是空树。
  2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝值不超过 1。

   平衡之意，如天平，即两边的分量大约相同。

   非平衡搜索二叉树

  平衡搜索二叉树：

2.平衡因子

定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。 

 

3.平衡二叉搜索树节点的定义

  1. struct AVLTreeNode {
  2. 		AVLTreeNode(const pair<K,V>&kv)
  3. 			:_left(nullptr)
  4. 			,_right(nullptr)
  5. 			,_kv(kv)
  6. 			,h(1)//一个节点的高度为1
  7. 		{}
  8.  
  9. 		AVLTreeNode<K, V>* _left;//左指针
  10. 		AVLTreeNode<K, V>* _right;//右指针
  11. 		pair<K, V> _kv;
  12. 		int h;.//高度
  13. 	};

 4.插入时失衡及其调整

在平衡搜索二叉树中插入一个节点1

 树结构变为：

 此时3和4这个节点失去平衡，在这里3

最小失衡树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

AVL树种解决失衡问题通过旋转最小失衡树来使整棵树达到平衡，旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

5.AVL树的四种旋转方式

5.1左旋（处理LL型违规）

5.2右旋（处理RR型违规）

5.3左右双旋（处理LR型违规）

5.4右左双旋（处理RL型违规）

5.1右旋

当插入节点1时树的结构变为：

此时树的平衡性被破坏此时从插入节点往上查，发现3这个节点不平衡原因是它的左树的高度太高，因此我们只需要对3这个节点进行右旋。

 右旋的基本步骤：

（1）节点的左孩子代表此节点

（2）节点的左孩子的右子树变为节点的左子树

（3）将此节点作为左孩子节点的右子树。

对应代码：

  1. 	Node* rightRotate(Node* cur) {
  2. 		Node* left = cur->_left;
  3. 		cur->_left = left->_right;
  4. 		left->_right = cur;
  5. 		cur->h = max((cur->_left != nullptr ? cur->_left->h : 0), (cur->_right != nullptr ? cur->_right->h : 0)) + 1;//更新高度
  6. 		left->h = max((left->_left != nullptr ? left->_left->h : 0), (left->_right != nullptr ? left->_right->h : 0)) + 1;//更新高度
  7. 		return left;//返回新的头
  8. 	}

 左单旋：

（1）节点的右孩子替代此节点位置

（2）右孩子的左子树变为该节点的右子树

（3）节点本身变为右孩子的左子树

 T，S,R均为抽象模型，代表对应的子树数字代表其高度。当我们在这颗树上插入节点10时，会使得8这个节点不平衡，此时是他的右树不平衡，此时我们只需要对8这个节点进行左单旋

 对应代码：

  1. 	Node* leftRotate(Node* cur) {
  2. 		Node* rightNode = cur->_right;
  3. 		cur->_right = rightNode->_left;
  4. 		rightNode->_left = cur;
  5. 		cur->h = max((cur->_left != nullptr ? cur->_left->h : 0), (cur->_right != nullptr ? cur->_right->h : 0)) + 1;//更新高度
  6. 		rightNode->h = max((rightNode->_left != nullptr ? rightNode->_left->h : 0), (rightNode->_right != nullptr ? rightNode->_right->h : 0)) + 1;//更新高度
  7. 		return rightNode;//返回新头部
  8. 	}

双旋

在上述过过程中的旋转都是直线过来的，因此经过一次旋转就可以使其达到平衡。但是如果是折线过来又改怎么旋转呢。

外面的数字代表树的高度，字母代表子树。在这里10这个节点的平衡性被破坏，但此时是因为10这个节点的左树的右树太高导致的。所以我们只要先对7进行左旋在对10进行右旋即可

 注意当同时满足LL型违规又满足LR型违规此时只能进行右旋而不能进行左右双旋。我们来看这个例子

此时整棵树既是LL型违规又是LR型违规，此时我们若只对10进行一个右旋是可以使整棵树带到平衡的。如图所示

 但是如果我们使用LR（左右双旋）不能使整棵树达到平衡，如图所示：

 旋转完成之后我们发现树并不平衡

右左双旋：

先对7进行右旋在对 10进行左旋

对应调整代码：

  1. Node* maintain(Node* cur) {
  2. 		if (cur == nullptr) {
  3. 			return nullptr;
  4. 		}
  5. 		int leftHeight = cur->_left != nullptr ? cur->_left->h : 0;//计算出cur左树的高度
  6. 		int rightHeight = cur->_right != nullptr ? cur->_right->h : 0;//计算出cur右树的高度
  7. 		if (abs(leftHeight - rightHeight) > 1) {//出现不平衡
  8. 			if (leftHeight > rightHeight) {//如果是左树高
  9. 				//把左树的左右子树的高度来出来比较看到底是左边高还是右边高
  10. 				int leftLeftHeight = cur->_left != nullptr && cur->_left->_left != nullptr ? cur->_left->_left->h : 0;
  11. 				int leftRightHeight = cur->_left != nullptr && cur->_left->_right != nullptr ? cur->_left->_right->h : 0;
  12. 				if (leftLeftHeight >= leftRightHeight) {//注意想等时只能右旋
  13. 					cur = rightRotate(cur);
  14. 				}
  15. 				else {//左右双旋
  16. 					cur->_left = leftRotate(cur->_left);
  17. 					cur = rightRotate(cur);
  18. 				}
  19. 			}
  20. 			else {
  21. 				int rightLeftHeight = cur->_right != nullptr && cur->_right->_left != nullptr ? cur->_right->_left->h: 0;
  22. 				int rightRightHeight = cur->_right != nullptr && cur->_right->_right != nullptr ? cur->_right->_right->h : 0;
  23. 				if (rightRightHeight >= rightLeftHeight) {
  24. 					cur = leftRotate(cur);
  25. 				}
  26. 				else {//右左双旋
  27. 					cur->_right = rightRotate(cur->_right);
  28. 					cur = leftRotate(cur);
  29. 				}
  30. 			}
  31. 		}
  32. 		return cur;//返回调整好的新头
  33. 	}

6.AVL树的插入

AVL树的插入和搜索二叉树的插入基本一样，与搜索二叉树不同的是：AVL树插入之后要从插入的节点往上查它的祖先是否出现不平衡

对应代码：

  1. ode* add(Node* cur, const pair<K, V>& kv){
  2. 		if (cur == nullptr) {//空树直接new出节点并返回
  3. 			return new Node(kv);
  4. 		}
  5. 		else {
  6. 			if (cur->_kv.first < kv.first) {//比当前节点大
  7. 				cur->_right = add(cur->_right, kv);//去cur的右边插入并将新的头部返回
  8. 			}
  9.  
  10. 			else {
  11. 				cur->_left = add(cur->_left, kv);//去cur的左边插入并将新的头部返回
  12. 			}
  13. 			cur->h = max(cur->_left != nullptr ? cur->_left->h : 0, cur->_right != nullptr ? cur->_right->h : 0)+1;//重新计算高度
  14. 			return maintain(cur);//对cur这个树进行调整
  15. 		}
  16.  
  17. 	}
  18. 	bool insert(const pair<K, V>& kv) {
  19. 		Node* lastNode = findLastIndex(kv.first);
  20. 		if (lastNode && lastNode->_kv.first == kv.first) {//已经存在插入失败
  21. 			return false;
  22. 		}
  23. 		else {
  24. 			_size++;
  25. 			_root = add(_root, kv);
  26. 			return true;
  27. 		}
  28. 	}

7.AVL树的删除

AVL树的删除和搜索二叉树基本一样，只不过比搜索二叉树多了平衡性的调整

删除一共有五种情况：
第一种情况：没找到删除的节点，遍历到空节点直接返回了
（找到删除的节点）
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点


第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点


第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点


第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

但上述的第二种情况可以归类成第三种情况或者第四种情况，我们删除的原则是删除节点之后它还是一颗搜索二叉树。

删除叶子节点：

 只有左孩子：

 只有右孩子

 既有左孩子又有右孩子

  

对应代码：

  1. Node* Delete(Node* cur, K key) {
  2. 		if (cur->_kv.first < key) {
  3. 			cur->_right = Delete(cur->_right, key);//去我的右边删除并且返回新的头部
  4. 		}
  5. 		else if (cur->_kv.first > key) {
  6. 			cur->_left = Delete(cur->_left, key);//去我的左边删除并返回新的头部
  7. 		}
  8. 		else {
  9. 			if (cur->_left==nullptr && cur->_right==nullptr) {//叶子节点左右都为空
  10. 				delete cur;
  11. 				return nullptr;
  12. 				
  13. 			}
  14. 			else if (!cur->_left && cur->_right) {//左为空但右不为空
  15. 				Node* subR = cur->_right;
  16. 				delete cur;
  17. 				cur = subR;
  18. 			}
  19. 			else if (cur->_left && !cur->_right) {//右为空但左不为空
  20. 				Node* subL = cur->_left;
  21. 				delete cur;
  22. 				cur = subL;
  23. 			}
  24. 			else {//左右都不为空采用替换法删除既采用值的方式替代
  25. 				Node* des = cur->_right;//找到右树最左节点或者找到左树的最右节点都可以
  26. 				while (des->_left)
  27. 				{
  28. 					des = des->_left;
  29. 				}
  30. 				pair<K, V>Kv = des->_kv;//记录对应的值
  31. 				cur->_right = Delete(cur->_right, des->_kv.first);//找到我先不删调用Delete 将des删掉并将树调整好
  32. 				cur->_kv = Kv;//替换
  33. 			
  34. 			}
  35. 		}
  36. 		if (cur) {//重新计算高度
  37. 			cur->h = max(cur->_left ? cur->_left->h : 0, cur->_right ? cur->_right->h : 0) + 1;
  38. 		}
  39.  
  40. 		return maintain(cur);//调整cur这颗树
  41. 	}
  42. 	void Erase(K key) {
  43. 		if (_root == nullptr) {
  44. 			return;
  45. 		}
  46. 		if (containsKey(key)) {
  47. 			--_size;
  48. 			_root = Delete(_root, key);
  49. 		}
  50. 	}
  51. 	//查找树中是否有key的这个节点
  52. 	public bool containsKey(K key) {
  53. 	if(_root==nullptr) {
  54. 			return false;
  55. 		}
  56. 	  Node* lastNode = findLastIndex(key);
  57. 		return lastNode && key==lastNode->_kv.first ? true : false;
  58. 	}

8.其他相关函数

  1. //找到最离key最近的节点
  2. 	Node* findLastIndex(K key) {
  3.  
  4. 		Node* pre = _root;//记录前一个节点
  5. 		Node* cur = _root;
  6. 		while (cur) {
  7. 			pre = cur;
  8. 			if (cur->_kv.first == key) {
  9. 				break;
  10. 			}
  11. 			else if (cur->_kv.first > key) {
  12. 				cur = cur->_left;
  13. 			}
  14. 			else {
  15. 				cur = cur->_right;
  16. 			}
  17. 		}
  18. 		return pre;
  19. 	}
  20. 	//找到离key最近的最小节点
  21. 	Node* findLastNoSmallIndex(K key) {
  22. 		Node* ans = nullptr;
  23. 		Node* cur = _root;
  24. 		while (cur) {
  25. 			if (cur->_kv.first == key) {
  26. 				ans = cur;
  27. 				break;
  28. 			}
  29. 			else if (cur->_kv.first > key) {
  30. 				ans = cur;
  31. 				cur = cur->_left;
  32. 			}
  33. 			else {
  34. 				cur = cur->_right;
  35. 			}
  36. 		}
  37. 		return ans;
  38. 	}
  39. 	//找到离key最近的最大节点
  40. 	Node* findLastNoBigIndex(K key) {
  41. 		Node* ans = nullptr;
  42. 		Node* cur = _root;
  43. 		while (cur) {
  44. 			if (cur->_kv.first == key) {
  45. 				ans = cur;
  46. 				break;
  47. 			}
  48. 			else if (cur->_kv.first > key) {
  49. 				cur = cur->_left;
  50. 			}
  51. 			else {
  52. 				ans = cur;
  53. 				cur = cur->_right;
  54. 			}
  55. 		}
  56. 		return ans;
  57. 	}
  58. 	//查找树中是否有key的这个节点
  59. 	public bool containsKey(K key) {
  60. 	if(_root==nullptr) {
  61. 			return false;
  62. 		}
  63. 	  Node* lastNode = findLastIndex(key);
  64. 		return lastNode && key==lastNode->_kv.first ? true : false;
  65. 	}
  66. 	
  67. 	int maxDepth(Node* root)//求高度
  68. 	{
  69. 		if (root == NULL)
  70. 		{
  71. 			return 0;
  72. 		}
  73. 		int leftDepth = maxDepth(root->_left);
  74. 		int rightDepth = maxDepth(root->_right);
  75. 		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
  76. 	}
  77. 	bool _isBalanced(Node* root)//判断是否平衡
  78. 	{
  79. 		if (root == nullptr)
  80. 		{
  81. 			return true;
  82. 		}
  83. 		int leftHight = maxDepth(root->_left);
  84. 		int rightHight = maxDepth(root->_right);
  85. 		return abs(leftHight - rightHight) < 2
  86. 			&& _isBalanced(root->_left)
  87. 			&& _isBalanced(root->_right);
  88.  
  89. 	}
  90.  
  91. 	bool isBalanced()
  92. 	{
  93. 		return _isBalanced(_root);
  94.  
  95. 	}
  96. 	void _Inorder(Node* root) {//中序遍历
  97. 		if (!root)
  98. 			return;
  99. 		_Inorder(root->_left);
  100. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
  101. 		_Inorder(root->_right);
  102. 	}
  103. 	void Inorder() {
  104. 		_Inorder(_root);
  105. 	}
  106. 	size_t size() {
  107. 		return _size;
  108. 	}

对应总代码：

  1. #include<iostream>
  2. using namespace std;
  3. 	template<class K,class V>
  4. 	struct AVLTreeNode {
  5. 		AVLTreeNode(const pair<K,V>&kv)
  6. 			:_left(nullptr)
  7. 			,_right(nullptr)
  8. 			,_kv(kv)
  9. 			,h(1)//一个节点的高度为1
  10. 		{}
  11.  
  12. 		AVLTreeNode<K, V>* _left;//左指针
  13. 		AVLTreeNode<K, V>* _right;//右指针
  14. 		pair<K, V> _kv;
  15. 		int h;//高度
  16. 	};
  17.  
  18. 	template<class K, class V>
  19. 	class AVLTree {
  20. 	public:
  21. 		
  22. 	typedef struct AVLTreeNode<K, V> Node;
  23. 	AVLTree(int size = 0, Node* root = nullptr)
  24. 		:_size(size)
  25. 		, _root(root)
  26. 	{}
  27. 	Node* add(Node* cur, const pair<K, V>& kv){
  28. 		if (cur == nullptr) {//空树直接new出节点并返回
  29. 			return new Node(kv);
  30. 		}
  31. 		else {
  32. 			if (cur->_kv.first < kv.first) {//比当前节点大
  33. 				cur->_right = add(cur->_right, kv);//去cur的右边插入并将新的头部返回
  34. 			}
  35.  
  36. 			else {
  37. 				cur->_left = add(cur->_left, kv);//去cur的左边插入并将新的头部返回
  38. 			}
  39. 			cur->h = max(cur->_left != nullptr ? cur->_left->h : 0, cur->_right != nullptr ? cur->_right->h : 0)+1;//重新计算高度
  40. 			return maintain(cur);//对cur这个树进行调整
  41. 		}
  42.  
  43. 	}
  44. 	bool insert(const pair<K, V>& kv) {
  45. 		Node* lastNode = findLastIndex(kv.first);
  46. 		if (lastNode && lastNode->_kv.first == kv.first) {
  47. 			return false;
  48. 		}
  49. 		else {
  50. 			_size++;
  51. 			_root = add(_root, kv);
  52. 			return true;
  53. 		}
  54. 	}
  55.  
  56. 	Node* Delete(Node* cur, K key) {
  57. 		if (cur->_kv.first < key) {
  58. 			cur->_right = Delete(cur->_right, key);//去我的右边删除并且返回新的头部
  59. 		}
  60. 		else if (cur->_kv.first > key) {
  61. 			cur->_left = Delete(cur->_left, key);//去我的左边删除并返回新的头部
  62. 		}
  63. 		else {
  64. 			if (cur->_left==nullptr && cur->_right==nullptr) {//叶子节点左右都为空
  65. 				delete cur;
  66. 				return nullptr;
  67. 				
  68. 			}
  69. 			else if (!cur->_left && cur->_right) {//左为空但右不为空
  70. 				Node* subR = cur->_right;
  71. 				delete cur;
  72. 				cur = subR;
  73. 			}
  74. 			else if (cur->_left && !cur->_right) {//右为空但左不为空
  75. 				Node* subL = cur->_left;
  76. 				delete cur;
  77. 				cur = subL;
  78. 			}
  79. 			else {//左右都不为空采用替换法删除既采用值的方式替代
  80. 				Node* des = cur->_right;//找到右树最左节点或者找到左树的最右节点都可以
  81. 				while (des->_left)
  82. 				{
  83. 					des = des->_left;
  84. 				}
  85. 				pair<K, V>Kv = des->_kv;//记录对应的值
  86. 				cur->_right = Delete(cur->_right, des->_kv.first);//找到我先不删调用Delete 将des删掉并将树调整好
  87. 				cur->_kv = Kv;//替换
  88. 			
  89. 			}
  90. 		}
  91. 		if (cur) {//重新计算高度
  92. 			cur->h = max(cur->_left ? cur->_left->h : 0, cur->_right ? cur->_right->h : 0) + 1;
  93. 		}
  94.  
  95. 		return maintain(cur);//调整cur这颗树
  96. 	}
  97. 	void Erase(K key) {
  98. 		if (_root == nullptr) {
  99. 			return;
  100. 		}
  101. 		if (containsKey(key)) {
  102. 			--_size;
  103. 			_root = Delete(_root, key);
  104. 		}
  105. 	}
  106. 	//找到最离key最近的节点
  107. 	Node* findLastIndex(K key) {
  108.  
  109. 		Node* pre = _root;//记录前一个节点
  110. 		Node* cur = _root;
  111. 		while (cur) {
  112. 			pre = cur;
  113. 			if (cur->_kv.first == key) {
  114. 				break;
  115. 			}
  116. 			else if (cur->_kv.first > key) {
  117. 				cur = cur->_left;
  118. 			}
  119. 			else {
  120. 				cur = cur->_left;
  121. 			}
  122. 		}
  123. 		return pre;
  124. 	}
  125. 	//找到离key最近的最小节点
  126. 	Node* findLastNoSmallIndex(K key) {
  127. 		Node* ans = nullptr;
  128. 		Node* cur = _root;
  129. 		while (cur) {
  130. 			if (cur->_kv.first == key) {
  131. 				ans = cur;
  132. 				break;
  133. 			}
  134. 			else if (cur->_kv.first > key) {
  135. 				ans = cur;
  136. 				cur = cur->_left;
  137. 			}
  138. 			else {
  139. 				cur = cur->_right;
  140. 			}
  141. 		}
  142. 		return ans;
  143. 	}
  144. 	//找到离key最近的最大节点
  145. 	Node* findLastNoBigIndex(K key) {
  146. 		Node* ans = nullptr;
  147. 		Node* cur = _root;
  148. 		while (cur) {
  149. 			if (cur->_kv.first == key) {
  150. 				ans = cur;
  151. 				break;
  152. 			}
  153. 			else if (cur->_kv.first > key) {
  154. 				cur = cur->_left;
  155. 			}
  156. 			else {
  157. 				ans = cur;
  158. 				cur = cur->_right;
  159. 			}
  160. 		}
  161. 		return ans;
  162. 	}
  163. 	//查找树中是否有key的这个节点
  164. 	public bool containsKey(K key) {
  165. 	if(_root==nullptr) {
  166. 			return false;
  167. 		}
  168. 	  Node* lastNode = findLastIndex(key);
  169. 		return lastNode && key==lastNode->_kv.first ? true : false;
  170. 	}
  171. 	
  172. 	int maxDepth(Node* root)//求高度
  173. 	{
  174. 		if (root == NULL)
  175. 		{
  176. 			return 0;
  177. 		}
  178. 		int leftDepth = maxDepth(root->_left);
  179. 		int rightDepth = maxDepth(root->_right);
  180. 		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
  181. 	}
  182. 	bool _isBalanced(Node* root)//判断是否平衡
  183. 	{
  184. 		if (root == nullptr)
  185. 		{
  186. 			return true;
  187. 		}
  188. 		int leftHight = maxDepth(root->_left);
  189. 		int rightHight = maxDepth(root->_right);
  190. 		return abs(leftHight - rightHight) < 2
  191. 			&& _isBalanced(root->_left)
  192. 			&& _isBalanced(root->_right);
  193.  
  194. 	}
  195.  
  196. 	bool isBalanced()
  197. 	{
  198. 		return _isBalanced(_root);
  199.  
  200. 	}
  201. 	void _Inorder(Node* root) {//中序遍历
  202. 		if (!root)
  203. 			return;
  204. 		_Inorder(root->_left);
  205. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
  206. 		_Inorder(root->_right);
  207. 	}
  208. 	void Inorder() {
  209. 		_Inorder(_root);
  210. 	}
  211. 	size_t size() {
  212. 		return _size;
  213. 	}
  214. 	Node* rightRotate(Node* cur) {
  215. 		Node* left = cur->_left;
  216. 		cur->_left = left->_right;
  217. 		left->_right = cur;
  218. 		cur->h = max((cur->_left != nullptr ? cur->_left->h : 0), (cur->_right != nullptr ? cur->_right->h : 0)) + 1;//更新高度
  219. 		left->h = max((left->_left != nullptr ? left->_left->h : 0), (left->_right != nullptr ? left->_right->h : 0)) + 1;//更新高度
  220. 		return left;//返回新的头
  221. 	}
  222. 	Node* leftRotate(Node* cur) {
  223. 		Node* rightNode = cur->_right;
  224. 		cur->_right = rightNode->_left;
  225. 		rightNode->_left = cur;
  226. 		cur->h = max((cur->_left != nullptr ? cur->_left->h : 0), (cur->_right != nullptr ? cur->_right->h : 0)) + 1;//更新高度
  227. 		rightNode->h = max((rightNode->_left != nullptr ? rightNode->_left->h : 0), (rightNode->_right != nullptr ? rightNode->_right->h : 0)) + 1;//更新高度
  228. 		return rightNode;//
  229. 	}
  230.  
  231. 	Node* maintain(Node* cur) {
  232. 		if (cur == nullptr) {
  233. 			return nullptr;
  234. 		}
  235. 		int leftHeight = cur->_left != nullptr ? cur->_left->h : 0;//计算出cur左树的高度
  236. 		int rightHeight = cur->_right != nullptr ? cur->_right->h : 0;//计算出cur右树的高度
  237. 		if (abs(leftHeight - rightHeight) > 1) {//出现不平衡
  238. 			if (leftHeight > rightHeight) {//如果是左树高
  239. 				//把左树的左右子树的高度来出来比较看到底是左边高还是右边高
  240. 				int leftLeftHeight = cur->_left != nullptr && cur->_left->_left != nullptr ? cur->_left->_left->h : 0;
  241. 				int leftRightHeight = cur->_left != nullptr && cur->_left->_right != nullptr ? cur->_left->_right->h : 0;
  242. 				if (leftLeftHeight >= leftRightHeight) {//注意想等时只能右旋
  243. 					cur = rightRotate(cur);
  244. 				}
  245. 				else {//左右双旋
  246. 					cur->_left = leftRotate(cur->_left);
  247. 					cur = rightRotate(cur);
  248. 				}
  249. 			}
  250. 			else {
  251. 				int rightLeftHeight = cur->_right != nullptr && cur->_right->_left != nullptr ? cur->_right->_left->h: 0;
  252. 				int rightRightHeight = cur->_right != nullptr && cur->_right->_right != nullptr ? cur->_right->_right->h : 0;
  253. 				if (rightRightHeight >= rightLeftHeight) {
  254. 					cur = leftRotate(cur);
  255. 				}
  256. 				else {//右左双旋
  257. 					cur->_right = rightRotate(cur->_right);
  258. 					cur = leftRotate(cur);
  259. 				}
  260. 			}
  261. 		}
  262. 		return cur;//返回调整好的新头
  263. 	}
  264. 	
  265.  
  266. 	private:
  267. 		Node* _root = nullptr;
  268. 		int _size = 0;
  269. 	};

对应迭代代码：

由于迭代不能和递归一样向上返回因此迭代中加了一个父亲指针和平衡因子，老铁可以自己下去研究，思路一样的。

  1. #pragma once
  2. using namespace std;
  3. #include <iostream>
  4. #include<queue>
  5. template<class K, class V>
  6. struct AVLTreeNode
  7. {
  8. 	AVLTreeNode(const pair<K, V>& kv = pair<K, V>())
  9. 		: _left(nullptr)
  10. 		, _right(nullptr)
  11. 		, _parent(nullptr)
  12. 		, _bf(0)
  13. 		, _kv(kv)
  14. 	{}
  15. 	AVLTreeNode<K, V>* _left;
  16. 	AVLTreeNode<K, V>* _right;
  17. 	AVLTreeNode<K, V>* _parent;
  18.  
  19. 	int _bf;//balance factor 平衡因子
  20.  
  21. 	pair<K, V> _kv;
  22. };
  23.  
  24. template<class K, class V>
  25. class AVLTree
  26. {
  27. public:
  28. 	typedef struct AVLTreeNode<K, V>  Node;
  29. 	//右单旋
  30. 	void RotateR(Node* parent)
  31. 	{
  32. 		Node* cur = parent->_left;
  33. 		Node* curR = cur->_right;//cur的右子树
  34. 		Node* pparent = parent->_parent;//保存parent的父亲节点
  35.  
  36. 		//将cur右子树链接到parent的左侧
  37. 		parent->_left = curR;
  38. 		if (curR)
  39. 			curR->_parent = parent;
  40.  
  41. 		//将parent连接到cur的右侧
  42. 		cur->_right = parent;
  43. 		parent->_parent = cur;
  44.  
  45. 		//将cur与pparent链接起来
  46. 		if (pparent == nullptr)//cur变成新的根
  47. 		{
  48. 			_root = cur;
  49. 			cur->_parent = nullptr;
  50. 		}
  51. 		else//pparent不为根
  52. 		{
  53. 			cur->_parent = pparent;
  54. 			if (parent == pparent->_left)//parent在父亲节点的左侧
  55. 			{
  56. 				pparent->_left = cur;
  57. 			}
  58. 			else
  59. 			{
  60. 				pparent->_right = cur;
  61. 			}
  62. 		}
  63.  
  64. 		//平衡因子更新
  65. 		parent->_bf = 0;
  66. 		cur->_bf = 0;
  67.  
  68. 	}
  69. 	//左单旋
  70. 	void RotateL(Node* parent)//左旋
  71. 	{
  72. 		Node* cur = parent->_right;//右变高，不可能为空
  73. 		Node* curL = cur->_left;
  74. 		Node* pprent = parent->_parent;
  75.  
  76. 		//curL连接到parent上
  77. 		parent->_right = curL;
  78. 		if (curL)
  79. 			curL->_parent = parent;
  80.  
  81. 		//parent连接到cur上
  82. 		cur->_left = parent;
  83. 		parent->_parent = cur;
  84.  
  85. 		//cur链接到pprent上
  86. 		if (pprent == nullptr)//根
  87. 		{
  88. 			_root = cur;
  89. 			cur->_parent = nullptr;
  90. 		}
  91. 		else//不为根
  92. 		{
  93. 			cur->_parent = pprent;
  94. 			//判断链接在哪一侧
  95. 			if (pprent->_left == parent)
  96. 			{
  97. 				pprent->_left = cur;
  98. 			}
  99. 			else
  100. 			{
  101. 				pprent->_right = cur;
  102. 			}
  103. 		}
  104.  
  105. 		//平衡因子的更新
  106. 		parent->_bf = 0;
  107. 		cur->_bf = 0;
  108. 	}
  109.  
  110. 	//左右双旋
  111. 	void RotateLR(Node* parent)
  112. 	{
  113. 		Node* cur = parent->_left;
  114. 		Node* curR = cur->_right;//此时不可能为空，因为右子树高
  115.  
  116. 		int bf = curR->_bf;//保存一份平衡因子
  117.  
  118. 		RotateL(cur);//先左旋
  119. 		RotateR(parent);//再右旋
  120.  
  121. 		//左旋、右旋会将平衡因子全部处理成0，因此要对平衡因子进行更改
  122.  
  123. 		if (bf == 1)//在curR的右侧插入
  124. 		{
  125. 			curR->_bf = 0;
  126. 			cur->_bf = -1;
  127. 			parent->_bf = 0;
  128. 		}
  129. 		else if (bf == -1)//在curR左侧插入
  130. 		{
  131. 			curR->_bf = 0;
  132. 			cur->_bf = 0;
  133. 			parent->_bf = 1;
  134. 		}
  135. 	}
  136. 	//右左双旋
  137. 	void RotateRL(Node* parent)
  138. 	{
  139. 		Node* cur = parent->_right;
  140. 		Node* curL = cur->_left;
  141.  
  142. 		int bf = curL->_bf;
  143.  
  144. 		RotateR(cur);//先右旋
  145. 		RotateL(parent);//再左旋
  146.  
  147. 		//平衡因子出来
  148.  
  149. 		if (bf == 1)//在subRL右侧插入时
  150. 		{
  151. 			curL->_bf = 0;
  152. 			parent->_bf = -1;
  153. 			cur->_bf = 0;
  154. 		}
  155. 		else if (bf == -1)//在左侧插入时
  156. 		{
  157. 			curL->_bf = 0;
  158. 			parent->_bf = 0;
  159. 			cur->_bf = 1;
  160. 		}
  161. 	}
  162. 	bool Insert(const pair<K, V>& kv)
  163. 	{
  164. 		if (_root == nullptr)
  165. 		{
  166. 			_root = new Node(kv);
  167. 			return true;
  168. 		}
  169.  
  170. 		//有根了，按照平衡二叉树的方法进行插入
  171. 		Node* parent = nullptr;
  172. 		Node* cur = _root;
  173. 		while (cur)
  174. 		{
  175. 			if (kv.first < cur->_kv.first)//K值比较，小于往左边走
  176. 			{
  177. 				parent = cur;
  178. 				cur = cur->_left;
  179. 			}
  180. 			else if (kv.first > cur->_kv.first)//往右走
  181. 			{
  182. 				parent = cur;
  183. 				cur = cur->_right;
  184. 			}
  185. 			else//相等，不进行插入
  186. 			{
  187. 				return false;
  188. 			}
  189. 		}
  190.  
  191. 		//此时已经找到插入的位置了,判断插入在parent的左边还是右边
  192. 		cur = new Node(kv);
  193. 		if (parent->_kv.first > kv.first)//插在左边
  194. 		{
  195. 			parent->_left = cur;
  196. 			cur->_parent = parent;//三叉链，cur父指针回指
  197. 		}
  198. 		else//插在右边
  199. 		{
  200. 			parent->_right = cur;
  201. 			cur->_parent = parent;//三叉链，cur父指针回指
  202. 		}
  203.  
  204.  
  205. 		//更新平衡因子
  206. 		while (parent)//不为空
  207. 		{
  208. 			if (parent->_left == cur)//cur在parent左侧
  209. 			{
  210. 				parent->_bf--;
  211. 			}
  212. 			else//cur在parent右侧
  213. 			{
  214. 				parent->_bf++;
  215. 			}
  216.  
  217. 			if (parent->_bf == 0)//当前树是平衡的，停止更新
  218. 				break;
  219. 			else if (parent->_bf == 1 || parent->_bf == -1)//继续往上面走
  220. 			{
  221. 				cur = parent;
  222. 				parent = parent->_parent;
  223. 			}
  224. 			else if (parent->_bf == 2 || parent->_bf == -2)//需要进行旋转处理
  225. 			{
  226. 				if (parent->_bf == -2)//左边高
  227. 				{
  228. 					if (cur->_bf == -1)//是在当前节点的左侧插入了节点 ->右单旋
  229. 					{
  230. 						RotateR(parent);
  231. 					}
  232. 					else//cur->_bf=1 ->曲线影响,需要进行左右双旋
  233. 					{
  234. 						RotateLR(parent);
  235. 					}
  236. 				}
  237. 				else//右边高
  238. 				{
  239. 					if (cur->_bf == 1)//在当前节点的右侧插入了节点 ->  左单旋
  240. 					{
  241. 						RotateL(parent);
  242. 					}
  243. 					else//cur->_bf=-1 曲线影响
  244. 					{
  245. 						RotateRL(parent);
  246. 					}
  247. 				}
  248. 				break;//旋转过后当前的树就是平衡的了，退出
  249. 			}
  250. 			else//0 1 2 -> 不可能走到这一步，走到这里说明发生了逻辑错误
  251. 			{
  252. 				exit(-1);
  253. 			}
  254. 		}
  255. 		return true;
  256. 	}
  257.  
  258. 	//删除函数
  259. 	bool Erase(const K& key)
  260. 	{
  261. 		//用于遍历二叉树
  262. 		Node* parent = nullptr;
  263. 		Node* cur = _root;
  264. 		//用于标记实际的删除结点及其父结点
  265. 		Node* delParentPos = nullptr;
  266. 		Node* delPos = nullptr;
  267. 		while (cur)
  268. 		{
  269. 			if (key < cur->_kv.first) //所给key值小于当前结点的key值
  270. 			{
  271. 				//往该结点的左子树走
  272. 				parent = cur;
  273. 				cur = cur->_left;
  274. 			}
  275. 			if (key > cur->_kv.first) //所给key值小于当前结点的key值
  276. 			{
  277. 				//往该结点的右子树走
  278. 				parent = cur;
  279. 				cur = cur->_right;
  280. 			}
  281. 			else //找到了待删除结点
  282. 			{
  283. 				if (cur->_left == nullptr) //待删除结点的左子树为空
  284. 				{
  285. 					if (cur == _root) //待删除结点是根结点
  286. 					{
  287. 						_root = _root->_right; //让根结点的右子树作为新的根结点
  288. 						//如果此时_root为空，此时寻找去父亲指针会对空指针解引用而报错，因此需要判断
  289. 						if (_root)
  290. 							_root->_parent = nullptr;
  291. 						delete cur; //删除原根结点
  292. 						return true; //根结点无祖先结点，无需进行平衡因子的更新操作
  293. 					}
  294. 					else
  295. 					{
  296. 						delParentPos = parent; //标记实际删除结点的父结点
  297. 						delPos = cur; //标记实际删除的结点
  298. 					}
  299. 					break; //删除结点有祖先结点，需更新平衡因子
  300. 				}
  301. 				else if (cur->_right == nullptr) //待删除结点的右子树为空
  302. 				{
  303. 					if (cur == _root) //待删除结点是根结点
  304. 					{
  305. 						_root = _root->_left; //让根结点的左子树作为新的根结点
  306. 						//如果此时_root为空，此时寻找去父亲指针会对空指针解引用而报错，因此需要判断
  307. 						if (_root)
  308. 							_root->_parent = nullptr;
  309. 						delete cur; //删除原根结点
  310. 						return true; //根结点无祖先结点，无需进行平衡因子的更新操作
  311. 					}
  312. 					else
  313. 					{
  314. 						delParentPos = parent; //标记实际删除结点的父结点
  315. 						delPos = cur; //标记实际删除的结点
  316. 					}
  317. 					break; //删除结点有祖先结点，需更新平衡因子
  318. 				}
  319. 				else //待删除结点的左右子树均不为空
  320. 				{
  321. 					//替换法删除
  322. 					//寻找待删除结点右子树当中key值最小的结点作为实际删除结点
  323. 					Node* minParent = cur;
  324. 					Node* minRight = cur->_right;
  325. 					while (minRight->_left)
  326. 					{
  327. 						minParent = minRight;
  328. 						minRight = minRight->_left;
  329. 					}
  330. 					cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key
  331. 					cur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value
  332. 					delParentPos = minParent; //标记实际删除结点的父结点
  333. 					delPos = minRight; //标记实际删除的结点
  334. 					break; //删除结点有祖先结点，需更新平衡因子
  335. 				}
  336. 			}
  337. 		}
  338. 		if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点
  339. 		{
  340. 			return false;
  341. 		}
  342.  
  343. 		//记录待删除结点及其父结点
  344. 		Node* del = delPos;
  345. 		Node* delP = delParentPos;
  346.  
  347. 		//更新平衡因子
  348. 		while (delPos != _root)
  349. 		{
  350. 			//判断删除的是在父亲的哪一边，然后更新平衡因子
  351. 			if (delPos == delParentPos->_left)
  352. 			{
  353. 				delParentPos->_bf++;
  354. 			}
  355. 			else if (delPos == delParentPos->_right)
  356. 			{
  357. 				delParentPos->_bf--;
  358. 			}
  359. 			//当前树是平衡的，停止更新
  360. 			if (delParentPos->_bf == -1 || delParentPos->_bf == 1)
  361. 			{
  362. 				break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
  363. 			}
  364. 			else if (delParentPos->_bf == 0)//需要继续往上更新平衡因子
  365. 			{
  366. 				//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
  367. 				delPos = delParentPos;
  368. 				delParentPos = delParentPos->_parent;
  369. 			}
  370.  
  371. 			else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转处理
  372. 			{
  373. 				if (delParentPos->_bf == -2)//左边高
  374. 				{
  375. 					if (delParentPos->_left->_bf == -1)//左边高，进行右单旋
  376. 					{
  377. 						Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
  378. 						RotateR(delParentPos); //右单旋
  379. 						delParentPos = tmp; //更新根结点
  380. 					}
  381. 					else if (delParentPos->_left->_bf == 1)//曲线影响,需要进行左右双旋
  382. 					{
  383. 						Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点
  384. 						RotateLR(delParentPos); //左右双旋
  385. 						delParentPos = tmp; //更新根结点
  386. 					}
  387. 					else //delParentPos->_left->_bf == 0
  388. 					{
  389. 						Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
  390. 						RotateR(delParentPos); //右单旋
  391. 						delParentPos = tmp; //更新根结点
  392. 						//平衡因子调整
  393. 						delParentPos->_bf = 1;
  394. 						delParentPos->_right->_bf = -1;
  395. 						break;
  396. 					}
  397. 				}
  398. 				else //delParentPos->_bf == 2
  399. 				{
  400. 					if (delParentPos->_right->_bf == -1)
  401. 					{
  402. 						Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点
  403. 						RotateRL(delParentPos); //右左双旋
  404. 						delParentPos = tmp; //更新根结点
  405. 					}
  406. 					else if (delParentPos->_right->_bf == 1)//曲线影响,需要进行左右双旋
  407. 					{
  408. 						Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
  409. 						RotateL(delParentPos); //左单旋
  410. 						delParentPos = tmp; //更新根结点
  411. 					}
  412. 					else //delParentPos->_right->_bf == 0
  413. 					{
  414. 						Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
  415. 						RotateL(delParentPos); //左单旋
  416. 						delParentPos = tmp; //更新根结点
  417. 						//平衡因子调整
  418. 						delParentPos->_bf = -1;
  419. 						delParentPos->_left->_bf = 1;
  420. 						break;
  421. 					}
  422. 				}
  423. 				//继续往上更新平衡因子
  424. 				delPos = delParentPos;
  425. 				delParentPos = delParentPos->_parent;
  426. 			}
  427. 			else
  428. 			{
  429. 				exit(-1); //不会到这里，到这里说明出现了错误
  430. 			}
  431. 		}
  432. 		//进行实际删除
  433. 		if (del->_left == nullptr) //实际删除结点的左子树为空
  434. 		{
  435. 			if (del == delP->_left) //实际删除结点是其父结点的左孩子
  436. 			{
  437. 				delP->_left = del->_right;
  438. 				if (del->_right)
  439. 					del->_right->_parent = parent;
  440. 			}
  441. 			else //实际删除结点是其父结点的右孩子
  442. 			{
  443. 				delP->_right = del->_right;
  444. 				if (del->_right)
  445. 					del->_right->_parent = parent;
  446. 			}
  447. 		}
  448. 		else //实际删除结点的右子树为空
  449. 		{
  450. 			if (del == delP->_left) //实际删除结点是其父结点的左孩子
  451. 			{
  452. 				delP->_left = del->_left;
  453. 				if (del->_left)
  454. 					del->_left->_parent = parent;
  455. 			}
  456. 			else //实际删除结点是其父结点的右孩子
  457. 			{
  458. 				delP->_right = del->_left;
  459. 				if (del->_left)
  460. 					del->_left->_parent = parent;
  461. 			}
  462. 		}
  463. 		delete del; //实际删除结点
  464. 		return true;
  465. 	}
  466.  
  467. 	//遍历的时候 root为private外面无法拿到
  468. 	//因此需要封装一层
  469. 	void _Inorder(Node* root)
  470. 	{
  471. 		if (root == nullptr)
  472. 			return;
  473. 		_Inorder(root->_left);
  474. 		cout << root->_kv.first << " " << root->_kv.second << endl;
  475. 		_Inorder(root->_right);
  476. 	}
  477. 	//中序遍历
  478. 	void Inorder()
  479. 	{
  480. 		_Inorder(_root);
  481. 	}
  482.  
  483. 	Node* Find(const K& k)
  484. 	{
  485. 		Node* cur = _root;
  486. 		while (cur)
  487. 		{
  488. 			if (cur->_kv.first > k)
  489. 				cur = cur->_left;
  490. 			else if (cur->_kv.first < k)
  491. 				cur = cur->_right;
  492. 			else
  493. 				return cur;
  494. 		}
  495. 		return false;
  496. 	}
  497.  
  498.  
  499. 	//求树的深度
  500. 	int maxDepth(Node* root)
  501. 	{
  502. 		if (root == NULL)
  503. 		{
  504. 			return 0;
  505. 		}
  506. 		int leftDepth = maxDepth(root->_left);
  507. 		int rightDepth = maxDepth(root->_right);
  508. 		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
  509. 	}
  510. 	bool _isBalanced(Node* root)
  511. 	{
  512. 		if (root == nullptr)
  513. 		{
  514. 			return true;
  515. 		}
  516. 		int leftHight = maxDepth(root->_left);
  517. 		int rightHight = maxDepth(root->_right);
  518. 		return abs(leftHight - rightHight) < 2
  519. 			&& _isBalanced(root->_left)
  520. 			&& _isBalanced(root->_right);
  521.  
  522. 	}
  523. 	bool isBalanced()
  524. 	{
  525. 		return _isBalanced(_root);
  526.  
  527. 	}
  528. private:
  529. 	Node* _root = nullptr;
  530. };

最后如果觉得对你有帮助的话劳烦您动动您的小手点个赞

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

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

  

闽ICP备14008679号