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

C++|AVL树(模拟实现，测试)_avl树测试

作者：Li_阴宅 | 2024-08-02 19:04:43

赞

踩

avl树测试

目录

一、概念

二、AVL树的实现

2.1节点定义

2.2AVL树的基础架构

2.3AVL树的插入 

2.3.1按照二叉搜索树的方式插入新节点

2.3.2调整节点的平衡因子

2.3.2.1 新节点插入较高右子树的右侧:进行左单旋

 2.3.2.2新结点插入较高左子树的左侧：进行右单旋

2.3.2.3新节点插入较高左子树的右侧：先左单旋再右单旋

2.3.2.4新结点插入较高右子树的左侧：先右单旋再左单旋

2.3.2.5调节平衡因子(完整版插入)

2.4AVL树的性能分析

三、AVL树的测试

一、概念

AVL树和红黑树都可以用来作为树形关联式容器的底层实现。但最终采用的是红黑树，虽然他们在时间复杂度上是一样的，但在某些场景下，红黑树更通用。他们依然是二叉搜索树，只不过实现二叉搜索树的方式不同，而被称做平衡二叉搜索树。

AVL树是由两名数学家(G.M.Adelson-Velskii和E.M.Landis)发明出来的一种解决二叉搜索树缺陷的方法，该树的名称也是这两位科学家的简称而得。

AVL树解决问题概念：当向二叉搜索树中插入新结点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1(若超过，需要进行调整，待后续讲解),即可降低树的高度，从而减少平均搜索长度。

AVL树性质：

  • 他的左右子树都是AVL树
  • 左右子树高度之差的绝对值不超过1(-1/0/1)，该高度之差也就是平衡因子

平衡因子= 右子树高度-左子树高度，也可以左减右，没有明确规定，那我采用的是右减左。

注意：是用高度之差计算出平衡因子，不是用平衡因子计算出平衡因子。其次平衡因子并不是必须的，他只是帮助我们更便捷的控制树

思考：既然了解了AVL树的规则，那为什么其高度差是不超过1，而不是0？

因为节点是一个一个插入的，有些情况无法做到左右子树高度相等，比如，2个节点的树，4个节点的树

更全面的平衡二叉搜索树如图：平衡因子记录高度差 

AVL树的高度是平衡的，高度可保持在log n,搜索时间复杂度为O(log N)。

二、AVL树的实现

2.1节点定义

节点中包括左指针，右指针，指向父节点的指针，平衡因子，要存储的数据值。 

  1. //节点
  2. 	template<class T>
  3. 	struct AVLTreeNode
  4. 	{
  5. 		AVLTreeNode(const T& data = T())
  6. 			:_left(nullptr)
  7. 			,_right(nullptr)
  8. 			,_parent(nullptr)
  9. 			,_bf(0)
  10. 			,_data(data)
  11. 		{
  12.  
  13. 		}
  14. 		AVLTreeNode<T>* _left;
  15. 		AVLTreeNode<T>* _right;
  16. 		AVLTreeNode<T>* _parent;
  17. 		T _bf;//平衡因子
  18. 		T _data;//要存储的值
  19. 	};

2.2AVL树的基础架构

  1.     template<class T>
  2. 	class AVLTree
  3. 	{
  4. 		typedef AVLTreeNode<T> Node;
  5. 		typedef Node* PNode;
  6. 	public:
  7. 		AVLTree()
  8. 			:_Root(nullptr)
  9. 		{}
  10.  
  11. 	private:
  12. 		PNode _Root;
  13. 	};

2.3AVL树的插入 

 AVL树的就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1.按照二叉搜索树的方式插入新节点

2.调整节点的平衡因子

2.3.1按照二叉搜索树的方式插入新节点

  1.  
  2. 		bool Insert(const T& data)
  3. 		{
  4. 			if (_Root == nullptr)
  5. 			{
  6. 				_Root = new Node(data);
  7. 				return true;
  8. 			}
  9. 			PNode cur = _Root;
  10. 			PNode parent = nullptr;
  11. 			//找插入点
  12. 			while (cur)
  13. 			{
  14. 				if (data < cur->_data)
  15. 				{
  16. 					parent = cur;
  17. 					cur = cur->_left;
  18. 					
  19. 				}
  20. 				else if (data > cur->_data)
  21. 				{
  22. 					parent = cur;
  23. 					cur = cur->_right;
  24. 	
  25. 				}
  26. 				else
  27. 					return false;
  28. 			}
  29. 			//插入
  30. 			PNode node = new Node(data);
  31. 			if (data < parent->_data)
  32. 			{
  33. 				parent->_left = node;
  34. 			}
  35. 			else
  36. 			{
  37. 				parent->_right = node;
  38. 			}
  39. 			node->_parent = parent;
  40.             return ture;
  41.         }

2.3.2调整节点的平衡因子

这里就有点漫长了，首先来了解一点，当我们插入节点时，会影响哪些节点的平衡因子？

会影响祖先的平衡因子，有时候是部分的，有时候是全部。至于为什么是这样，这就要来了解平衡因子的更新原则，如图：

 由上图可知根据节点的插入位置，来决定哪些祖先的平衡因子需要改变。

那么现在就要来重点讲一讲旋转问题了，当发生不平衡时，根据节点插入位置的不同，AVL树的旋转分为四种：

2.3.2.1 新节点插入较高右子树的右侧:进行左单旋

对于其插入，可以通过抽象图来做代表，通过具象图来进行更好的分析。 

 ​​​​​​​

 

根据图的分析，我们可将他转化为代码，其中要注意的是，当旋转完后，也要更新节点中指向父 节点的指针：

  1.         //左单旋
  2. 		void RotateL(PNode parent)
  3. 		{
  4. 			PNode subR = parent->_right;
  5. 			PNode subRL = subR->_left;
  6. 			PNode pparent = parent->_parent;
  7.  
  8. 			if (parent == _Root)//更新根节点
  9. 			{
  10. 				_Root = subR;
  11. 			}
  12. 			else
  13. 			{
  14. 				//更新parent的父节点指向
  15. 				if (parent == pparent->_left)
  16. 				{
  17. 					subR->_parent = pparent;
  18. 					pparent->_left = subR;
  19. 				}
  20. 				else
  21. 				{
  22. 					subR->_parent = pparent;
  23. 					pparent->_right = subR;
  24. 				}
  25. 			}
  26.  
  27. 			//parent的右指针指向subRL,subRL的父节点指向parent
  28. 			parent->_right = subR->_left;
  29. 			if(subRL)//subR的左节点可能不存在
  30. 				subRL->_parent = parent;
  31.  
  32. 			//subR的左指针指向parent,parent的父节点指向subR
  33. 			subR->_left = parent;
  34. 			parent->_parent = subR;
  35.  
  36. 			//更新平衡因子
  37. 			parent->_bf = subR->_bf = 0;
  38. 		}
 2.3.2.2新结点插入较高左子树的左侧：进行右单旋

 

根据图的分析，我们可将他转化为代码：

  1.         //右单旋
  2. 		void RotateR(PNode parent)
  3. 		{
  4. 			PNode subL = parent->_left;
  5. 			PNode subLR = subL->_right;
  6. 			PNode pparent = parent->_parent;
  7.  
  8. 			if (_Root == parent)
  9. 			{
  10. 				_Root = subL;
  11. 				subL->_parent = nullptr;
  12. 			}
  13. 			else
  14. 			{
  15. 				//更新parent的父节点指向
  16. 				if (pparent->_left == parent)
  17. 				{
  18. 					pparent->_left = subL;
  19. 				}
  20. 				else
  21. 				{
  22. 					pparent->_right = subL;
  23. 				}
  24. 				subL->_parent = pparent;
  25. 			}
  26. 			//parent的左指针指向subLR,subLR的父节点指向parent
  27. 			parent->_left = subLR;
  28. 			if(subLR)//subR的右节点可能不存在
  29. 				subLR->_parent = parent;
  30. 			//subL的右指针指向parent,parent的父节点指向subL
  31. 			subL->_right = parent;
  32. 			parent->_parent = subL;
  33.  
  34. 			//更新平衡因子
  35. 			parent->_bf = subL->_bf = 0;
  36. 		}
2.3.2.3新节点插入较高左子树的右侧：先左单旋再右单旋

有了上述的抽象图了解，这里就不在进行具象图分析，而是直接在抽象图上分析。 

当在右侧插入时，其也分为两种情况，为什么要区分这两种情况？

因为他们影响平衡因子的情况不同，所以要做区分。

 

 

 将上述情况转换为代码：

  1. 	    //左右单旋
  2. 		void RotateLR(PNode parent)
  3. 		{
  4. 			PNode subL = parent->_left;
  5. 			PNode subLR = subL->_right;
  6. 			int bf = subLR->_bf;//记录下来，为了后面更新平衡因子
  7.  
  8. 			RotateL(parent->_left);//左单旋
  9. 			RotateR(parent);//右单旋
  10.  
  11. 			因为左单旋和右单旋已经破坏了原本的平衡因子，所以需要手动更新
  12. 			//那么这里以原本subRL的平衡因子来做衡量
  13. 			if (bf == -1)
  14. 			{
  15. 				parent->_bf = 1;
  16. 				subL->_bf = 0;
  17. 				subLR->_bf = 0;
  18. 			}
  19. 			else if (bf == 1)
  20. 			{
  21. 				parent->_bf = 0;
  22. 				subL->_bf = -1;
  23. 				subLR->_bf = 0;
  24. 			}
  25. 			else if (bf == 0)//表示新插入节点
  26. 			{
  27. 				parent->_bf = subL->_bf = subLR->_bf = 0;
  28. 			}
  29. 		}
2.3.2.4新结点插入较高右子树的左侧：先右单旋再左单旋

 

 将上述情况转换为代码：

  1.         //右左单旋
  2. 		void RotateRL(PNode parent)
  3. 		{
  4. 			PNode subR = parent->_right;
  5. 			PNode subRL = subR->_left;
  6. 			int bf = subRL->_bf;//记录下来，为了后面更新平衡因子
  7. 			RotateR(parent->_right);//右单旋
  8. 			RotateL(parent);//左单旋
  9.  
  10. 			//因为右单旋和左单旋已经破坏了原本的平衡因子，所以需要手动更新
  11. 			//那么这里以原本subRL的平衡因子来做衡量
  12. 			if (bf == 1)
  13. 			{
  14. 				parent->_bf = -1;
  15. 				subR->_bf = 0;
  16. 				subRL->_bf = 0;
  17. 			}
  18. 			else if (bf == -1)
  19. 			{
  20. 				parent->_bf = 0;
  21. 				subR->_bf = 1;
  22. 				subRL->_bf = 0;
  23. 			}
  24. 			else if (bf == 0)//表示新插入节点
  25. 			{
  26. 				parent->_bf = subR->_bf = subRL->_bf = 0;
  27. 			}
  28. 		}
2.3.2.5调节平衡因子(完整版插入)

当插入新结点时，更新祖先结点的平衡因子，并一直往上判断，根据祖先结点的平衡因子判断是否需要进行旋转。

  1.         bool Insert(const T& data)
  2. 		{
  3. 			if (_Root == nullptr)
  4. 			{
  5. 				_Root = new Node(data);
  6. 				return true;
  7. 			}
  8. 			PNode cur = _Root;
  9. 			PNode parent = nullptr;
  10. 			//找插入点
  11. 			while (cur)
  12. 			{
  13. 				if (data < cur->_data)
  14. 				{
  15. 					parent = cur;
  16. 					cur = cur->_left;
  17. 					
  18. 				}
  19. 				else if (data > cur->_data)
  20. 				{
  21. 					parent = cur;
  22. 					cur = cur->_right;
  23. 	
  24. 				}
  25. 				else
  26. 					return false;
  27. 			}
  28. 			//插入
  29. 			PNode node = new Node(data);
  30. 			if (data < parent->_data)
  31. 			{
  32. 				parent->_left = node;
  33. 			}
  34. 			else
  35. 			{
  36. 				parent->_right = node;
  37. 			}
  38. 			node->_parent = parent;
  39. 			cur = node;
  40.  
  41.  
  42. 			while (cur)
  43. 			{
  44. 				if (parent == nullptr)
  45. 					break;
  46. 				//更新平衡因子
  47. 				if (cur == parent->_left)
  48. 					parent->_bf--;
  49. 				else
  50. 					parent->_bf++;
  51.  
  52. 				if (parent->_bf == 0)//不会影响爷爷，直接插入结束
  53. 				{
  54. 					break;
  55. 				}
  56. 				else if(parent->_bf == 1 || parent->_bf == -1)//继续往上
  57. 				{
  58. 					cur = parent;
  59. 					parent = parent->_parent;
  60. 				}
  61. 				else if(parent->_bf == 2 || parent->_bf == -2)
  62. 				{
  63. 					if (cur == parent->_right)
  64. 					{
  65. 						if (cur->_bf == 1)
  66. 						{
  67. 							//左单旋
  68. 							RotateL(parent);
  69. 						}
  70. 						else if (cur->_bf == -1)
  71. 						{
  72. 							//右左单旋
  73. 							RotateRL(parent);
  74. 						}
  75. 					}
  76. 					else
  77. 					{
  78. 						if (cur->_bf == 1)
  79. 						{
  80. 							//左右单旋
  81. 							RotateLR(parent);
  82. 						
  83. 						}
  84. 						else if (cur->_bf == -1)
  85. 						{
  86. 							//右单旋
  87. 							RotateR(parent);
  88. 						}
  89. 					}	
  90. 					break;
  91. 				}
  92. 				else
  93. 				{
  94. 					assert(false);//插入之前就有问题
  95. 				}
  96. 			}	
  97. 			return true;
  98.  
  99. 		}

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将结点删除，然后更新平衡因子，只不过，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

对于AVL树的删除，在这里就不在模拟实现了，因为有了插入的了解，就足够我们进行对AVL树的学习认识。

当然，如果想要进一步了解，可参考<<算法导论>>或<<数据结果-用面向南对象方法与C++描述>>殷人昆版。 

2.4AVL树的性能分析

 AVL树是一颗绝对平衡的二叉搜索树，弥补了普通版本的二叉搜索树的缺陷。其要求每个节点的左右子树高度差的绝对值不超过1，这样就可以保证查询时高效的时间复杂度，即log N。但是如果要

对AVL树做一些结构修改的操作，性能非常低下，

比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

因此 ：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会变),可以考虑AVL树，但一个结构经常修改，就不太适合。

三、AVL树的测试

 

  1. //AVLTree.h
  2. #include <iostream>
  3. #include <vector>
  4. #include <assert.h>
  5. using namespace std;
  6.  
  7. namespace bit
  8. {
  9. 	//节点
  10. 	template<class T>
  11. 	struct AVLTreeNode
  12. 	{
  13. 		AVLTreeNode(const T& data = T())
  14. 			:_left(nullptr)
  15. 			,_right(nullptr)
  16. 			,_parent(nullptr)
  17. 			,_bf(0)
  18. 			,_data(data)
  19. 		{}
  20. 		AVLTreeNode<T>* _left;
  21. 		AVLTreeNode<T>* _right;
  22. 		AVLTreeNode<T>* _parent;
  23. 		T _bf;//平衡因子
  24. 		T _data;
  25. 	};
  26.  
  27.  
  28. 	template<class T>
  29. 	class AVLTree
  30. 	{
  31. 		typedef AVLTreeNode<T> Node;
  32. 		typedef Node* PNode;
  33. 	public:
  34. 		AVLTree()
  35. 			:_Root(nullptr)
  36. 		{}
  37.  
  38. 		bool Insert(const T& data)
  39. 		{
  40. 			if (_Root == nullptr)
  41. 			{
  42. 				_Root = new Node(data);
  43. 				return true;
  44. 			}
  45. 			PNode cur = _Root;
  46. 			PNode parent = nullptr;
  47. 			//找插入点
  48. 			while (cur)
  49. 			{
  50. 				if (data < cur->_data)
  51. 				{
  52. 					parent = cur;
  53. 					cur = cur->_left;
  54. 					
  55. 				}
  56. 				else if (data > cur->_data)
  57. 				{
  58. 					parent = cur;
  59. 					cur = cur->_right;
  60. 	
  61. 				}
  62. 				else
  63. 					return false;
  64. 			}
  65. 			//插入
  66. 			PNode node = new Node(data);
  67. 			if (data < parent->_data)
  68. 			{
  69. 				parent->_left = node;
  70. 			}
  71. 			else
  72. 			{
  73. 				parent->_right = node;
  74. 			}
  75. 			node->_parent = parent;
  76. 			cur = node;
  77.  
  78.  
  79. 			while (cur)
  80. 			{
  81. 				if (parent == nullptr)
  82. 					break;
  83. 				//更新平衡因子
  84. 				if (cur == parent->_left)
  85. 					parent->_bf--;
  86. 				else
  87. 					parent->_bf++;
  88.  
  89. 				if (parent->_bf == 0)//不会影响爷爷，直接插入结束
  90. 				{
  91. 					break;
  92. 				}
  93. 				else if(parent->_bf == 1 || parent->_bf == -1)//继续往上
  94. 				{
  95. 					cur = parent;
  96. 					parent = parent->_parent;
  97. 				}
  98. 				else if(parent->_bf == 2 || parent->_bf == -2)
  99. 				{
  100. 					if (cur == parent->_right)
  101. 					{
  102. 						if (cur->_bf == 1)
  103. 						{
  104. 							//左单旋
  105. 							RotateL(parent);
  106. 						}
  107. 						else if (cur->_bf == -1)
  108. 						{
  109. 							//右左单旋
  110. 							RotateRL(parent);
  111. 						}
  112. 					}
  113. 					else
  114. 					{
  115. 						if (cur->_bf == 1)
  116. 						{
  117. 							//左右单旋
  118. 							RotateLR(parent);
  119. 						
  120. 						}
  121. 						else if (cur->_bf == -1)
  122. 						{
  123. 							//右单旋
  124. 							RotateR(parent);
  125. 						}
  126. 					}	
  127. 					break;
  128. 				}
  129. 				else
  130. 				{
  131. 					assert(false);//插入之前就有问题
  132. 				}
  133. 			}	
  134. 			return true;
  135.  
  136. 		}
  137.  
  138. 		//左单旋
  139. 		void RotateL(PNode parent)
  140. 		{
  141. 			PNode subR = parent->_right;
  142. 			PNode subRL = subR->_left;
  143. 			PNode pparent = parent->_parent;
  144.  
  145. 			if (parent == _Root)//更新根节点
  146. 			{
  147. 				_Root = subR;
  148. 				subR->_parent = nullptr;
  149. 			}
  150. 			else
  151. 			{
  152. 				//更新parent的父节点指向
  153. 				if (parent == pparent->_left)
  154. 				{
  155. 					pparent->_left = subR;
  156. 				}
  157. 				else
  158. 				{
  159. 					pparent->_right = subR;
  160. 				}
  161. 				subR->_parent = pparent;
  162.  
  163. 			}
  164.  
  165. 			//parent的右指针指向subRL,subRL的父节点指向parent
  166. 			parent->_right = subR->_left;
  167. 			if(subRL)//subR的左节点可能不存在
  168. 				subRL->_parent = parent;
  169.  
  170. 			//subR的左指针指向parent,parent的父节点指向subR
  171. 			subR->_left = parent;
  172. 			parent->_parent = subR;
  173.  
  174. 			//更新平衡因子
  175. 			parent->_bf = subR->_bf = 0;
  176. 		}
  177.  
  178. 		//右单旋
  179. 		void RotateR(PNode parent)
  180. 		{
  181. 			PNode subL = parent->_left;
  182. 			PNode subLR = subL->_right;
  183. 			PNode pparent = parent->_parent;
  184.  
  185. 			if (_Root == parent)
  186. 			{
  187. 				_Root = subL;
  188. 				subL->_parent = nullptr;
  189. 			}
  190. 			else
  191. 			{
  192. 				//更新parent的父节点指向
  193. 				if (pparent->_left == parent)
  194. 				{
  195. 					pparent->_left = subL;
  196. 				}
  197. 				else
  198. 				{
  199. 					pparent->_right = subL;
  200. 				}
  201. 				subL->_parent = pparent;
  202. 			}
  203. 			//parent的左指针指向subLR,subLR的父节点指向parent
  204. 			parent->_left = subLR;
  205. 			if(subLR)//subR的右节点可能不存在
  206. 				subLR->_parent = parent;
  207. 			//subL的右指针指向parent,parent的父节点指向subL
  208. 			subL->_right = parent;
  209. 			parent->_parent = subL;
  210.  
  211. 			//更新平衡因子
  212. 			parent->_bf = subL->_bf = 0;
  213. 		}
  214.  
  215. 		//左右单旋
  216. 		void RotateLR(PNode parent)
  217. 		{
  218. 			PNode subL = parent->_left;
  219. 			PNode subLR = subL->_right;
  220. 			int bf = subLR->_bf;//记录下来，为了后面更新平衡因子
  221.  
  222. 			RotateL(parent->_left);//左单旋
  223. 			RotateR(parent);//右单旋
  224.  
  225. 			因为左单旋和右单旋已经破坏了原本的平衡因子，所以需要手动更新
  226. 			//那么这里以原本subRL的平衡因子来做衡量
  227. 			if (bf == -1)
  228. 			{
  229. 				parent->_bf = 1;
  230. 				subL->_bf = 0;
  231. 				subLR->_bf = 0;
  232. 			}
  233. 			else if (bf == 1)
  234. 			{
  235. 				parent->_bf = 0;
  236. 				subL->_bf = -1;
  237. 				subLR->_bf = 0;
  238. 			}
  239. 			else if (bf == 0)//表示新插入节点
  240. 			{
  241. 				parent->_bf = subL->_bf = subLR->_bf = 0;
  242. 			}
  243. 		}
  244.  
  245. 		//右左单旋
  246. 		void RotateRL(PNode parent)
  247. 		{
  248. 			PNode subR = parent->_right;
  249. 			PNode subRL = subR->_left;
  250. 			int bf = subRL->_bf;//记录下来，为了后面更新平衡因子
  251. 			RotateR(parent->_right);//右单旋
  252. 			RotateL(parent);//左单旋
  253.  
  254. 			//因为右单旋和左单旋已经破坏了原本的平衡因子，所以需要手动更新
  255. 			//那么这里以原本subRL的平衡因子来做衡量
  256. 			if (bf == 1)
  257. 			{
  258. 				parent->_bf = -1;
  259. 				subR->_bf = 0;
  260. 				subRL->_bf = 0;
  261. 			}
  262. 			else if (bf == -1)
  263. 			{
  264. 				parent->_bf = 0;
  265. 				subR->_bf = 1;
  266. 				subRL->_bf = 0;
  267. 			}
  268. 			else if (bf == 0)//表示新插入节点
  269. 			{
  270. 				parent->_bf = subR->_bf = subRL->_bf = 0;
  271. 			}
  272. 		}
  273.  
  274. 		void InOrder()
  275. 		{
  276. 			_InOrder(_Root);
  277. 			cout << endl;
  278. 		}
  279. 		int Height()
  280. 		{
  281. 			return _Height(_Root);
  282. 		}
  283. 		int _Height(PNode Root)
  284. 		{
  285. 			if (Root == nullptr)
  286. 				return 0;
  287. 			int _LeftHeight = _Height(Root->_left)+ 1;
  288. 			int _RightHeight = _Height(Root->_right) + 1;
  289. 			return max(_LeftHeight, _RightHeight);
  290. 		}
  291. 		bool _IsBalance()
  292. 		{
  293. 			return _IsBalanceTree(_Root);
  294. 		}
  295. 		bool _IsBalanceTree(PNode Root)
  296. 		{
  297. 			if (Root == nullptr)
  298. 				return true;
  299. 			int _LeftHeight = _Height(Root->_left);
  300. 			int _RightHeight = _Height(Root->_right);
  301. 			int sub =_RightHeight - _LeftHeight ;
  302. 			if (sub != Root->_bf)
  303. 			{
  304. 				cout << Root->_data << ":" << "平衡因子异常" << endl;
  305. 				return false;
  306. 			}
  307.  
  308. 			if (sub == 1 || sub == -1 || sub == 0)
  309. 			{
  310. 				return _IsBalanceTree(Root->_left) && _IsBalanceTree(Root->_right);
  311. 			}
  312. 			else
  313. 				return false;
  314.  
  315. 		}
  316.  
  317. 		PNode Find(size_t data)
  318. 		{
  319. 			PNode cur = _Root;
  320. 			while (cur)
  321. 			{
  322. 				if (cur->_data < data)
  323. 				{
  324. 					cur = cur->_left;
  325. 				}
  326. 				else if (cur->_data > data)
  327. 				{
  328. 					cur = cur->_right;
  329. 				}
  330. 				else
  331. 				{
  332. 					return cur;
  333. 				}
  334. 			}
  335.  
  336. 			return NULL;
  337. 		}
  338.  
  339.  
  340. 		size_t Size()
  341. 		{
  342. 			return _Size(_Root);
  343. 		}
  344. 		size_t _Size(PNode cur)
  345. 		{
  346. 			if (cur == nullptr)
  347. 				return 0;
  348.  
  349. 			return _Size(cur->_left) + _Size(cur->_right) + 1;
  350. 		}
  351. 		
  352. 	private:
  353. 		void _InOrder(PNode Root)
  354. 		{
  355. 			if (Root == nullptr)
  356. 				return;
  357.  
  358. 			_InOrder(Root->_left);
  359. 			cout << Root->_data<< endl;
  360. 			_InOrder(Root->_right);
  361. 		}
  362. 		PNode _Root;
  363. 	};
  364. 	void AVLTreeTest()
  365. 	{
  366. 		//int arr[] = { 16,3,7,11,9,26,18,14,15};
  367. 		int arr[] = { 4,2,6,1,3,5,15,7,16,14 };
  368. 		AVLTree<int> avl;
  369.  
  370. 		for (auto e : arr)
  371. 		{
  372.  
  373. 			avl.Insert(e);
  374. 		}
  375. 		avl.InOrder();
  376. 		cout <<avl._IsBalance();
  377. 	}
  378. 	void TestAVLTree2()
  379. 	{
  380. 		const int N = 9;
  381. 		vector<int> v;
  382. 		v.reserve(N);
  383. 		srand(time(0));
  384.  
  385. 		for (size_t i = 0; i < N; i++)
  386. 		{
  387. 			v.push_back(rand() + i);
  388. 			//cout << v.back() << endl;
  389. 		}
  390.  
  391. 		size_t begin2 = clock();
  392. 		AVLTree<int> t;
  393. 		for (auto e : v)
  394. 		{
  395. 			t.Insert(e);
  396. 			cout << "Insert:" << e << "->" << t._IsBalance() << endl;
  397. 		}
  398. 		size_t end2 = clock();
  399.  
  400. 		cout << "Insert:" << end2 - begin2 << endl;
  401.  
  402. 		cout << t._IsBalance() << endl;
  403.  
  404. 		cout << "Height:" << t.Height() << endl;
  405. 		cout << "Size:" << t.Size() << endl;
  406.  
  407. 		size_t begin1 = clock();
  408. 		// 确定在的值
  409. 		for (auto e : v)
  410. 		{
  411. 			t.Find(e);
  412. 		}
  413.  
  414. 		// 随机值
  415. 		for (size_t i = 0; i < N; i++)
  416. 		{
  417. 			t.Find((rand() + i));
  418. 		}
  419.  
  420. 		size_t end1 = clock();
  421.  
  422. 		cout << "Find:" << end1 - begin1 << endl;
  423. 	}
  424. }
  1. //test.cpp
  2. #include "AVLTree.h"
  3.  
  4. int main()
  5. {
  6. 	bit::AVLTreeTest();
  7. 	//bit::TestAVLTree2();
  8.  
  9. 	return 0;
  10. }

输出结果：

  1. //test.cpp
  2. #include "AVLTree.h"
  3.  
  4. int main()
  5. {
  6. 	//bit::AVLTreeTest();
  7. 	bit::TestAVLTree2();
  8.  
  9. 	return 0;
  10. }

 输出结果：

end~ 

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

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

  

闽ICP备14008679号