• C++数据结构(上):模拟实现AVL

     "我们无法一直活在过去,亦如我们从未能挽救死亡"

    (1)AVL树:

    概念:平衡搜索二叉树。

    性质:

    ①根节点的左右子树 是AVL树

    ②左右子树的高度的差 不超过1

    ③比根节点大的 插在根节点的右边。 小的 在左边。

    (2)AVL树模拟实现: 

     关于AVL树概念上的东西，多讲无用。我们现在直接来实现。

    ① 结构框架:

    注:这里实现的是key值版。

    1. //AVL树的 节点
    2. template<class T>
    3. struct AVLTreeNode
    4. {
    5. 	//节点指针
    6. 	AVLTreeNode* _left;
    7. 	AVLTreeNode* _right;
    8. 	AVLTreeNode* _parent;
    9. 	//节点数值
    10. 	T _key;  
    11.  
    12. 	//为了调节平衡 这里引入平衡因子;
    13. 	int _bf;
    14.  
    15. 	//构造
    16. 	AVLTreeNode(const T& key)
    17. 		:_left(nullptr),
    18. 		: _right(nullptr),
    19. 		_parent(nullptr),
    20. 		_key(key),
    21. 		_bf(0)      //任何新插入的 节点 平衡因子都默认设置为0
    22. 	{}
    23.  
    24. };
    25.  
    26. template<class K>
    27. class AVLTree
    28. {
    29. 	typedef AVLTreeNode Node;
    30.  
    31. 	AVLTree()
    32. 		:_root(nullptr)
    33. 	{}
    34.  
    35. private:
    36. 	Node* _root;
    37. };

    对于AVL树而言，显然难点在插入的部分。所以这留到最后讲。那么这部分进行相关功能的实现。

     ②查找+中序遍历:

    1. 	Node* find(const K& key)
    2. 	{
    3. 		Node* cur = _root;
    4. 		while (cur)
    5. 		{
    6. 			if (key > cur->_key)
    7. 			{
    8. 				cur = cur->_right;
    9. 			}
    10. 			else if(key < cur->_key)
    11. 			{
    12. 				cur = cur->_left;
    13. 			}
    14. 			else
    15. 			{
    16. 				//找到了
    17. 				return cur;
    18. 			}
    19. 		}
    20. 		return nullptr;
    21. 	}
    22.  
    23.  
    24. 	void _InOrder(Node* root)
    25. 	{
    26. 		if (root == nullptr)
    27. 			return;
    28.  
    29. 		_InOrder(root->_left);
    30. 		cout << root->_key << endl;
    31. 		_InOrder(root->_right);
    32. 	}
    33.  
    34. 	void InOrder()
    35. 	{
    36. 		_InOrder(_root);
    37. 	}

    ③检查平衡+析构:

    1. 	
    2. 	void _Destory(Node* root)
    3. 	{
    4. 		if (root == nullptr)
    5. 			return;
    6. 		_Destory(root->_left);
    7. 		_Destory(root->_right);
    8. 		delete root;
    9. 	}
    10.  
    11.      ~AVLTree()
    12. 	{
    13. 		_Destory(_root);
    14. 		_root =nullptr;
    15. 	} 
    16.  
    17.  
    18.     int TreeHight(Node* root)
    19. 	{
    20. 		if (root == nullptr)
    21. 			return 0;
    22.  
    23. 		int leftdepth = TreeHight(root->_left);
    24. 		int rightdepth = TreeHight(root->_right);
    25.  
    26. 		//返回 左右子树 大的那个
    27. 		return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
    28. 	}
    29.  
    30. 	bool _isBalance(Node* root)
    31. 	{
    32. 		if (root == nullptr)
    33. 			return true;  //空树也是平衡树
    34.  
    35. 		int Maxleft = TreeHight(_root->_left);
    36. 		int Maxright = TreeHight(_root->_right);
    37.  
    38. 		return abs(Maxleft - Maxright) < 2
    39. 			&& _isBalance(root->_left)
    40. 			&& _isBalance(root->_right);
    41. 	}
    42.  
    43. 	bool _isBalance()
    44. 	{
    45.          return _isBalance(_root);
    46. 	}

     关于如何理解检查这棵树是否平衡的函数，也就不多赘述。因为在前面二叉树篇讲过。

    下面就进入重头戏~

    ④AVL的插入;

            

    1. 	//如果是第一次插入 直接去做根 root
    2. 		if (_root == nullptr)
    3. 		{
    4. 			_root = new Node(k);
    5. 			return true;
    6. 		}
    7.  
    8. 		//不是第一个值
    9. 		Node* cur = _root;
    10. 		Node* parent = nullptr;
    11. 		while (cur)  //这里和find的思想一样 
    12. 		{
    13. 			if (key > cur->_key)
    14. 			{
    15. 				parent = cur;
    16. 				cur = cur->_right;
    17. 			}
    18. 			else if (key < cur->_key)
    19. 			{
    20. 				parent = cur;
    21. 				cur = cur->_left;
    22. 			}
    23. 			else
    24. 			{
    25. 				//如果走到这里 说明 已经插入了和key 一样的数
    26. 				return true;
    27. 			}
    28. 		}
    29.  
    30. 		//cur 走到空的位置了
    31. 		cur = new Node(key);
    32. 		Node* newnode = cur;
    33.  
    34. 		//更新与parent的关系
    35. 		if (cur->_key  > parent->_key)
    36. 		{
    37. 			parent->_right = cur;
    38. 		}
    39. 		else
    40. 		{
    41. 			parent->_left = cur;
    42. 		}
    43. 		//注意我们设计的是三叉连 结构
    44. 		//cur 还有反过来 指向parent
    45. 		cur->_parent = parent;

     

    任何一次对树数据的操作，都可能造成对树结构的破坏。

    所以，为了 保护树的结构。我们需要根据不同情况，对树进行位置的更换

    (1)平衡因子:

     我们让在根节点 右插入对 _bf ++ 

                                    左插入 _bf--;

    由此,每棵树节点的 平衡因子会分为三种情况。

     [0]  [-1,1]  [2,-2]

     

    1. 	//调节平衡因子;
    2. 		//while(parent)
    3. 		while (cur != root)
    4. 		{
    5. 		   //更新节点bf
    6. 			if (cur == parent->_left)
    7. 			{
    8. 				parent->_bf--;
    9. 			}
    10. 			else
    11. 			{
    12. 				parent->_bf++;
    13. 			}
    14.  
    15.  
    16. 			//根据平衡因子 进行调整
    17. 			if (parent->_bf == 0)
    18. 			{
    19. 				break;  //不做任何事情
    20. 			}
    21. 			else if(parent->_bf ==-1 || parent->_bf == 1)
    22. 			{
    23. 				//向上调整 
    24. 				cur = parent;
    25. 				parent->_parent;
    26. 			}
    27. 			else if(parent->_bf == -2 || parent->_bf == 2)
    28. 			{
    29. 				//调整
    30. 			}
    31. 			else
    32. 			{
    33. 				//理论上不会走到这里来
    34. 				//如果走到这里来 也是调整前 已经不是AVL数
    35. 				assert(false);
    36. 			}
    37. 		}

     

    (2)左右单旋:

     我们在看单旋图中,就是bf=-1,1 的节点(也就是parent) 是旋转的轴。

    1. 	else if(parent->_bf == -2 || parent->_bf == 2)
    2. 			{
    3. 				//调整
    4. 				//左边新增节点
    5. 				if (parent->_bf == -2)  
    6. 				{
    7. 					if (cur->_bf == -1) //新节点在左边插入
    8. 					{
    9. 						//左高 右边低 需要右翻转
    10. 						RotateR(parent);
    11. 					}
    12. 					else  //新增节点插入在右边
    13. 					{
    14.  
    15. 					}
    16. 				}
    17. 				else //右边新增节点
    18. 				{
    19. 					if (cur->_bf == 1)  //新节点从右边插入
    20. 					{
    21. 						//此时 右高 左低 需要 右翻转
    22. 						RotateL(parent);
    23. 					}
    24. 					else //新增节点在左边
    25. 					{
    26.  
    27. 					}
    28. 				}
    29. 				//翻转完 就跳出
    30. 				break;
    31. 			}

    这也就是单旋插入的逻辑。

    右单旋实现:

    也及时sub subLR parent 三方的关系;

     

    1. 	void RotateR(Node* parent)
    2. 	{
    3. 		Node* sub = parent->_left;
    4. 		Node* subLR = sub->_right;
    5.  
    6. 		//让subLR去做parent的左
    7. 		parent->_left = subLR;
    8. 		//subLR可能不存在
    9. 		if(subLR)
    10. 		subLR->_parent = parent;
    11.  
    12. 		sub->_right = parent;
    13. 		//记录 父节点 因为 sub 可能不是唯一独立的树
    14. 		Node* grandparent = parent->_parent;
    15. 		parent->_parent = sub;
    16.  
    17. 		if (parent == _root)
    18. 		{
    19. 			//独立树
    20. 			_root = sub;
    21. 			sub->_parent = nullptr;
    22. 		}
    23. 		else
    24. 		{
    25. 			//子树
    26. 			//parent的 父亲仍然保留着 节点地址
    27. 			if (grandparent->_left == parent)
    28. 			{
    29. 				grandparent->_left = sub;
    30. 			}
    31. 			else
    32. 			{
    33. 				grandparent->_right = sub;
    34. 			}
    35. 			//更新回来
    36. 			sub->_parent = grandparent;
    37. 		}
    38. 		
    39. 		//调节平衡因子
    40. 		parent->_bf = sub->_bf = 0;
    41. 	}

     

     

    1. 	RotateL(Node* parent)
    2. 	{
    3. 		Node* sub = parent->_right;
    4. 		Node* subRL = sub->_left;
    5.  
    6. 		//让subRL 去做parent的右边
    7. 		parent->_right = subRL;
    8. 		//仍然注意避坑
    9. 		if(subRL)
    10. 			subRL->_parent = parent;
    11.  
    12. 		Node* grandparent = parent->_parent;
    13. 		sub->_left = parent;
    14. 		parent->_parent = sub;
    15.  
    16. 		if (parent == _root)
    17. 		{
    18. 			_root = sub;
    19. 			sub->_parent = nullptr;
    20. 		}
    21. 		else
    22. 		{
    23. 			if (grandparent->_left == parent)
    24. 			{
    25. 				grandparent->_left = sub;
    26. 			}
    27. 			else
    28. 			{
    29. 				grandparent->_right = sub;
    30. 			}
    31. 			sub->_parent = grandparent;
    32. 		}
    33. 	
    34. 		parent->_bf = sub->_bf = 0;
    35. 	}

    (3)双旋转:

    左右双旋转:
     

    1. 	void RotateLR(Node* parent)
    2. 	{
    3. 		Node* sub = parent->_left;
    4. 		Node* subLR = sub->_right;
    5. 		//保存插入处 的平衡因子~
    6. 		int bf = subLR->_bf;
    7.  
    8. 		RotateL(sub);
    9. 		RotateR(parent);
    10.  
    11. 		//调整平衡因子
    12. 		if (bf == -1)  //左边B插入
    13. 		{
    14. 			sub->_bf = 0;
    15. 			subRL->_bf = 0;
    16. 			parent->_bf = 1;
    17. 		}
    18. 		else if(bf ==1)
    19. 		{
    20. 			sub->_bf = -1;
    21. 			subRL->_bf = 0;
    22. 			parent->_bf = 0;
    23. 		}
    24. 		else if(bf ==0)
    25. 		{
    26. 			sub->_bf = 0;
    27. 			subRL->_bf = 0;
    28. 			parent->_bf = 0;
    29. 		}
    30. 		else
    31. 		{
    32. 			assert(false);
    33. 		}
    34. 	}

    右左双旋:

    这个同上也就 不再多分析。

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

    ④测试;

    插入也就到此为止,我们先来试着跑几组数据看是否正确。

     

     (3)K、V版AVL 树

    1. namespace dy
    2. {
    3. 	template<class K, class V>
    4. 	struct AVLTreeNode
    5. 	{
    6. 		//节点指针
    7. 		AVLTreeNode* _left;
    8. 		AVLTreeNode* _right;
    9. 		AVLTreeNode* _parent;
    10. 		//节点数值
    11. 		pair _kv;
    12.  
    13. 		//为了调节平衡 这里引入平衡因子;
    14. 		int _bf;
    15.  
    16. 		//构造
    17. 		AVLTreeNode(const pair& kv)
    18. 			:_left(nullptr),
    19. 			_right(nullptr),
    20. 			_parent(nullptr),
    21. 			_kv(kv),
    22. 			_bf(0)      //任何新插入的 节点 平衡因子都默认设置为0
    23. 		{}
    24. 	};
    25.  
    26. 	template<class K,class V>
    27. 	struct AVLTreeKV
    28. 	{
    29. 		typedef AVLTreeNode Node;
    30. 		Node* _root;
    31.  
    32. 		AVLTreeKV()
    33. 			:_root(nullptr)
    34. 		{}
    35.  
    36. 		void _InOrder(Node* root)
    37. 		{
    38. 			if (root == nullptr)
    39. 				return;
    40.  
    41. 			_InOrder(root->_left);
    42. 			cout << root->_kv.first << ":"<_kv.second<
    43. 			_InOrder(root->_right);
    44. 		}
    45.  
    46.  
    47. 		//没封装迭代器 暂且用Node* 替
    48. 		pairbool> insert(const pair kv)
    49. 		{
    50. 			//如果是第一次插入 直接去做根 root
    51. 			if (_root == nullptr)
    52. 			{
    53. 				_root = new Node(kv);
    54. 				return make_pair(_root,true);
    55. 			}
    56.  
    57. 			//不是第一个值
    58. 			Node* cur = _root;
    59. 			Node* parent = nullptr;
    60. 			while (cur)  //这里和find的思想一样 
    61. 			{
    62. 				if (kv.first > cur->_kv.first)
    63. 				{
    64. 					parent = cur;
    65. 					cur = cur->_right;
    66. 				}
    67. 				else if (kv.first < cur->_kv.first)
    68. 				{
    69. 					parent = cur;
    70. 					cur = cur->_left;
    71. 				}
    72. 				else
    73. 				{
    74. 					//如果走到这里 说明 已经插入了和key 一样的数
    75. 					return make_pair(cur,true);
    76. 				}
    77. 			}
    78.  
    79. 			//cur 走到空的位置了
    80. 			cur = new Node(kv);
    81. 			Node* newnode = cur;
    82.  
    83. 			//更新与parent的关系
    84. 			if (cur->_kv.first > parent->_kv.first)
    85. 			{
    86. 				parent->_right = cur;
    87. 			}
    88. 			else
    89. 			{
    90. 				parent->_left = cur;
    91. 			}
    92. 			//注意我们设计的是三叉连 结构
    93. 			//cur 还有反过来 指向parent
    94. 			cur->_parent = parent;
    95.  
    96. 			//调节平衡因子;
    97. 			//while(parent)
    98. 			while (cur != _root)
    99. 			{
    100. 				//更新节点bf
    101. 				if (cur == parent->_left)
    102. 				{
    103. 					parent->_bf--;
    104. 				}
    105. 				else
    106. 				{
    107. 					parent->_bf++;
    108. 				}
    109.  
    110.  
    111. 				//根据平衡因子 进行调整
    112. 				if (parent->_bf == 0)
    113. 				{
    114. 					break;  //不做任何事情
    115. 				}
    116. 				else if (parent->_bf == -1 || parent->_bf == 1)
    117. 				{
    118. 					//向上调整 
    119. 					cur = parent;
    120. 					parent = parent->_parent;
    121. 				}
    122. 				else if (parent->_bf == -2 || parent->_bf == 2)
    123. 				{
    124. 					//调整
    125. 					//左边新增节点
    126. 					if (parent->_bf == -2)
    127. 					{
    128. 						if (cur->_bf == -1) //新节点在左边插入
    129. 						{
    130. 							//左高 右边低 需要右翻转
    131. 							RotateR(parent);
    132. 						}
    133. 						else  //新增节点插入在右边
    134. 						{
    135. 							//此时 是折线
    136. 						   //使用双旋
    137. 							RotateLR(parent);
    138. 						}
    139. 					}
    140. 					else //右边新增节点
    141. 					{
    142. 						if (cur->_bf == 1)  //新节点从右边插入
    143. 						{
    144. 							//此时 右高 左低 需要 右翻转
    145. 							RotateL(parent);
    146. 						}
    147. 						else //新增节点在左边
    148. 						{
    149. 							RotateRL(parent);
    150. 						}
    151. 					}
    152. 					//翻转完 就跳出
    153. 					break;
    154. 				}
    155. 				else
    156. 				{
    157. 					//理论上不会走到这里来
    158. 					//如果走到这里来 也是调整前 已经不是AVL数
    159. 					assert(false);
    160. 				}
    161. 			}
    162. 			return make_pair(newnode,true);
    163. 		}
    164.  
    165. }

     

    总结: 

    ①AVL树 插入节点时很看重平衡因子。

    ②平衡因子条件 [0] [-1,1] [-2,2]

    ③单旋是直线 双旋 为折线

    内容到这里也就结束啦，感谢你的阅读。

    祝你好运~

     

  • 相关阅读:
    PMP每日一练 | 考试不迷路-11.29（包含敏捷+多选）
    springboot 整合使用redis发布订阅功能
    Docker搭建ctfd平台
    jmeter-常用的一些java代码
    java中的IO缓冲流（高效流）---原始流的升级版
    tomcat优化
    Vue脚手架的初次了解/使用
    Mysql 语句优化方案—官方原版
    Vue--》详解Vue组件生命周期的三个阶段
    Web安全—Web漏扫工具Nikto安装与使用
  • 原文地址：https://blog.csdn.net/RNGWGzZs/article/details/126016218