【数据结构】AVL树的旋转和插入

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】AVL树的旋转和插入，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

AVL树

左单旋


代码实现

  1. void _RotateL(Node* parent)
  2. 	{
  3. 		Node* subR=parent->_right;
  4. 		Node* subRL=subR->_left;
  5. 		Node* ppNode=parent->_parent;
  6. 		subR->_left=parent;
  7. 		parent->_right=subRL;
  8. 		if(subRL)
  9. 			subRL->_parent=parent;
  10. 		if(ppNode==NULL)
  11. 		{
  12. 			_root=subR;
  13. 		    subR->_parent=NULL;
  14. 		}
  15. 		else if(ppNode->_left==parent)
  16. 		{
  17. 			ppNode->_left=subR;
  18. 			subR->_parent=ppNode;
  19. 		}
  20. 		else//(ppNode->_right==parent)
  21. 		{
  22. 			ppNode->_right=subR;
  23. 			subR->_parent=ppNode;
  24. 		}
  25. 	    subR->_bf=parent->_bf=0;
  26. 	}


右单旋


实现

  1. void _RotateR(Node* parent)
  2. 	{
  3. 		Node* subL=parent->_left;
  4. 		Node* subLR=subL->_right;
  5. 		Node* ppNode=parent->_parent;
  6. 		subL->_right=parent;
  7. 		parent->_left=subLR;
  8. 		if(subLR)
  9.          subLR->_parent=parent;
  10. 		if(ppNode==NULL)
  11. 		{
  12. 			_root=subL;
  13. 			subL->_parent==NULL;
  14. 		}
  15. 		else if(ppNode->_left==parent)
  16. 		{
  17. 			subL->_parent=ppNode;
  18. 			ppNode->_left=subL;
  19. 		}
  20. 		else if (ppNode->_right==parent)
  21. 		{
  22. 			subL->_parent=ppNode;
  23. 			ppNode->_right=subL;
  24. 		}
  25. 		subL->_bf=parent->_bf=0;
  26. 	}


左右旋


实现

  1. void _RotateLR(Node* parent)
  2. 	{
  3.  
  4. 		Node* subL=parent->_left;
  5. 		Node* subLR=subL->_right;
  6. 		int bf=subLR->_bf;
  7. 		_RotateL(parent->_left);
  8. 		_RotateR(parent);
  9. 		if (bf==0)
  10. 		{
  11. 			subL->_bf=subLR->_bf=parent->_bf=0;
  12. 		}
  13. 		else if (bf==-1)
  14. 		{
  15. 			parent->_bf=1;
  16. 			subLR->_bf=subL->_bf=0;
  17. 		}
  18. 		else
  19. 		{
  20. 			subL->_bf=-1;
  21. 			subLR->_bf=parent->_bf=0;
  22. 		}
  23. 		
  24. 	}


右左旋


实现

  1. void _RotateRL(Node* parent)
  2. 	{
  3. 		Node* subR=parent->_right;
  4. 		Node* subRL=subR->_left;
  5. 		int bf=subRL->_bf;
  6. 		_RotateR(parent->_right);
  7. 		_RotateRL(parent);
  8. 		if(bf==0)
  9. 		{
  10. 			subR->_bf=parent->_bf=0;
  11. 		}
  12. 		else if(bf==-1)
  13. 		{
  14. 			parent->_bf=subR->_bf=0;
  15. 			subRL->_bf=1;
  16. 		}
  17. 		else
  18. 		{
  19. 			parent->_bf=-1;
  20. 			subR->_bf=subRL->_bf=0;
  21. 		}
  22. 	}

两个特殊测试用例



解决这两个特殊用例的部分代码（具体实现在插入函数）

  1.  else
  2. 		  {
  3. 			if(parent->_bf == 2)
  4. 			{
  5. 				if(cur->_bf == 1)
  6. 				{
  7. 					_RotateL(parent);
  8. 				}
  9. 				else if(cur->_bf==-2)
  10. 				{
  11. 					_RotateRL(parent);
  12. 				}
  13. 			}
  14. 			else if(parent->_bf==-2)
  15. 			{ 
  16. 				if(cur->_bf == -1)
  17. 				{
  18. 					_RotateR(parent);
  19. 				}
  20. 				else if(cur->_bf==2)
  21. 				{
  22. 					_RotateLR(parent);
  23. 				}
  24. 			}

插入函数 
  1. 	bool Insert(const K& key,const V& value)
  2. 	{
  3. 		Node* newNode=new Node(key,value);
  4. 		if(_root==NULL)
  5. 		{
  6. 			_root=newNode;
  7. 			return true;
  8. 		}
  9.       Node* parent=NULL;
  10. 	  Node* cur=_root;
  11.       
  12. 	  while(cur)
  13. 	  { 
  14. 		  
  15. 		  if(cur->_key>key)
  16. 		  {
  17. 			  parent=cur;
  18. 		  cur=cur->_left;
  19.  		  }
  20. 		  else if(cur->_key<key)
  21. 		  {
  22. 			  parent=cur;
  23. 		     cur=cur->_right;
  24. 		  }
  25. 		  else
  26. 			  return false;
  27. 	  }
  28. 	  cur=new Node(key,value);
  29. 	  cur->_parent=parent;
  30. 	  if(parent->_key>key)
  31. 		  parent->_left=cur;
  32. 	  else if(parent->_key<key)
  33. 		  parent->_right=cur;
  34. 	  while (parent)
  35. 	  {
  36. 		  if(parent->_left==cur)
  37. 		  {
  38. 			  --parent->_bf;
  39. 		  }
  40. 		  else if(parent->_right==cur)
  41. 		  {
  42. 			  ++parent->_bf;
  43. 		  }
  44. 		  if(parent->_bf==0)
  45. 		  {
  46. 			  return true;
  47. 		  }
  48. 		  if(abs(parent->_bf)==1)
  49. 		  {
  50. 			  cur=parent;
  51. 			  parent=parent->_parent;
  52. 		  }
  53.  
  54. 		 else
  55. 		  {
  56. 			if(parent->_bf == 2)
  57. 			{
  58. 				if(cur->_bf == 1)
  59. 				{
  60. 					_RotateL(parent);
  61. 				}
  62. 				else if(cur->_bf==-2)
  63. 				{
  64. 					_RotateRL(parent);
  65. 				}
  66. 			}
  67. 			else if(parent->_bf==-2)
  68. 			{ 
  69. 				if(cur->_bf == -1)
  70. 				{
  71. 					_RotateR(parent);
  72. 				}
  73. 				else if(cur->_bf==2)
  74. 				{
  75. 					_RotateLR(parent);
  76. 				}
  77. 			}
  78. 			else
  79. 			return true;
  80. 		}
  81. 	}
  82. 	return true;
  83. }

全部代码

AVLtree.h

  1. #include<iostream>
  2. using namespace std;
  3. template<class K,class V>
  4. struct AVLtreeNode
  5. {
  6. 	AVLtreeNode<K,V>* _left;
  7. 	AVLtreeNode<K,V>* _right;
  8. 	AVLtreeNode<K,V>* _parent;
  9. 	K _key;
  10. 	V _value;
  11. 	int _bf;
  12. 	AVLtreeNode(const K& key,const V& value)
  13. 		:_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value),_bf(0)
  14. 	{}
  15. };
  16. template<class K,class V>
  17. class AVLtree
  18. {
  19. 	typedef AVLtreeNode<K,V> Node;
  20. public:
  21. 	AVLtree()
  22. 		:_root(NULL)
  23. 	{}
  24. 	~AVLtree()
  25. 	{}
  26. 	bool Insert(const K& key,value);
  27. 	  cur->_parent=parent;
  28. 	  if(parent->_key>key)
  29. 		  parent->_left=cur;
  30. 	  else if(parent->_key<key)
  31. 		  parent->_right=cur;
  32. 	  while (parent)
  33. 	  {
  34. 		  if(parent->_left==cur)
  35. 		  {
  36. 			  --parent->_bf;
  37. 		  }
  38. 		  else if(parent->_right==cur)
  39. 		  {
  40. 			  ++parent->_bf;
  41. 		  }
  42. 		  if(parent->_bf==0)
  43. 		  {
  44. 			  return true;
  45. 		  }
  46. 		  if(abs(parent->_bf)==1)
  47. 		  {
  48. 			  cur=parent;
  49. 			  parent=parent->_parent;
  50. 		  }
  51.  
  52. 		 else
  53. 		  {
  54. 			if(parent->_bf == 2)
  55. 			{
  56. 				if(cur->_bf == 1)
  57. 				{
  58. 					_RotateL(parent);
  59. 				}
  60. 				else if(cur->_bf==-2)
  61. 				{
  62. 					_RotateRL(parent);
  63. 				}
  64. 			}
  65. 			else if(parent->_bf==-2)
  66. 			{ 
  67. 				if(cur->_bf == -1)
  68. 				{
  69. 					_RotateR(parent);
  70. 				}
  71. 				else if(cur->_bf==2)
  72. 				{
  73. 					_RotateLR(parent);
  74. 				}
  75. 			}
  76. 			else
  77. 			return true;
  78. 		}
  79. 	}
  80. 	return true;
  81. }
  82. 	void Inorder()
  83. 	{
  84. 		_Inorder(_root);
  85. 		cout<<endl;
  86. 	}
  87. 	int Height()
  88. 	{
  89. 	return	_Height(_root);
  90. 	}
  91. 	bool IsBalance()
  92. 	{
  93. 		return _IsBalance(_root);
  94. 	}
  95. 	bool IsBalanceOP()
  96. 	{
  97. 		int Height=0;
  98. 		
  99.          return _IsBalanceOP(_root,Height);
  100. 	}
  101.  
  102. protected:
  103. 	void _Inorder(Node* root)
  104. 	{
  105. 		if(root==NULL)
  106. 			return;
  107. 		_Inorder(root->_left);
  108. 		cout<<" KEY:  "<<root->_key<<" VALUE:  "<<root->_value<<" BF:  "<<root->_bf<<endl;
  109. 		_Inorder(root->_right);
  110. 	}
  111. 	int _Height(Node* root)
  112. 	{
  113. 		if(root==NULL)
  114. 			return 0;
  115. 	    int left=_Height(root->_left)+1;
  116. 		int right=_Height(root->_right)+1;
  117. 		return left>right ? left:right;
  118. 	}
  119. 	bool _IsBalance(Node* parent)
  120. 	{
  121. 		if(parent==NULL)
  122. 			return true;
  123. 		int bf=_Height(parent->_right)-_Height(parent->_left);
  124. 		if(parent->_bf!=bf)
  125. 		{
  126. 			cout<<"不是平衡树"<<parent->_key<<endl;
  127. 			return false;
  128. 		}
  129. 		return _IsBalance(parent->_left);
  130. 		return _IsBalance(parent->_right);
  131. 	}
  132. 	bool _IsBalanceOP(Node* root,int height)
  133. 	{
  134. 		if (root==NULL)
  135. 		{
  136. 			height=0;
  137. 			return true;
  138. 		}
  139. 		int leftHeight=0;
  140. 		if(_IsBalanceOP(root->_left,leftHeight)==false)
  141. 			return false;
  142. 		int rightHeigt=0;
  143. 		if(_IsBalanceOP(root->_right,rightHeigt)==false)
  144. 			return false;
  145. 		return true;
  146. 	}
  147. 	void _RotateL(Node* parent)
  148. 	{
  149. 		Node* subR=parent->_right;
  150. 		Node* subRL=subR->_left;
  151. 		Node* ppNode=parent->_parent;
  152. 		subR->_left=parent;
  153. 		parent->_right=subRL;
  154. 		if(subRL)
  155. 			subRL->_parent=parent;
  156. 		if(ppNode==NULL)
  157. 		{
  158. 			_root=subR;
  159. 		    subR->_parent=NULL;
  160. 		}
  161. 		else if(ppNode->_left==parent)
  162. 		{
  163. 			ppNode->_left=subR;
  164. 			subR->_parent=ppNode;
  165. 		}
  166. 		else//(ppNode->_right==parent)
  167. 		{
  168. 			ppNode->_right=subR;
  169. 			subR->_parent=ppNode;
  170. 		}
  171. 	    subR->_bf=parent->_bf=0;
  172. 	}
  173. 	void _RotateR(Node* parent)
  174. 	{
  175. 		Node* subL=parent->_left;
  176. 		Node* subLR=subL->_right;
  177. 		Node* ppNode=parent->_parent;
  178. 		subL->_right=parent;
  179. 		parent->_left=subLR;
  180. 		if(subLR)
  181.          subLR->_parent=parent;
  182. 		if(ppNode==NULL)
  183. 		{
  184. 			_root=subL;
  185. 			subL->_parent==NULL;
  186. 		}
  187. 		else if(ppNode->_left==parent)
  188. 		{
  189. 			subL->_parent=ppNode;
  190. 			ppNode->_left=subL;
  191. 		}
  192. 		else if (ppNode->_right==parent)
  193. 		{
  194. 			subL->_parent=ppNode;
  195. 			ppNode->_right=subL;
  196. 		}
  197. 		subL->_bf=parent->_bf=0;
  198. 	}
  199. 	void _RotateLR(Node* parent)
  200. 	{
  201.  
  202. 		Node* subL=parent->_left;
  203. 		Node* subLR=subL->_right;
  204. 		int bf=subLR->_bf;
  205. 		_RotateL(parent->_left);
  206. 		_RotateR(parent);
  207. 		if (bf==0)
  208. 		{
  209. 			subL->_bf=subLR->_bf=parent->_bf=0;
  210. 		}
  211. 		else if (bf==-1)
  212. 		{
  213. 			parent->_bf=1;
  214. 			subLR->_bf=subL->_bf=0;
  215. 		}
  216. 		else
  217. 		{
  218. 			subL->_bf=-1;
  219. 			subLR->_bf=parent->_bf=0;
  220. 		}
  221. 		
  222. 	}
  223. 	void _RotateRL(Node* parent)
  224. 	{
  225. 		Node* subR=parent->_right;
  226. 		Node* subRL=subR->_left;
  227. 		int bf=subRL->_bf;
  228. 		_RotateR(parent->_right);
  229. 		_RotateRL(parent);
  230. 		if(bf==0)
  231. 		{
  232. 			subR->_bf=parent->_bf=0;
  233. 		}
  234. 		else if(bf==-1)
  235. 		{
  236. 			parent->_bf=subR->_bf=0;
  237. 			subRL->_bf=1;
  238. 		}
  239. 		else
  240. 		{
  241. 			parent->_bf=-1;
  242. 			subR->_bf=subRL->_bf=0;
  243. 		}
  244. 	}
  245. private:
  246. 	Node* _root;
  247. };
  248. void TestAVLtree1()
  249. {
  250. 	AVLtree<int,int> At;
  251. 	At.Insert(0,1);
  252. 	At.Insert(1,1);
  253. 	At.Insert(2,1);
  254. 	At.Insert(3,1);
  255. 	At.Insert(4,1);
  256. 	At.Insert(5,1);
  257. 	At.Insert(6,1);
  258. 	At.Insert(7,1);
  259. 	At.Insert(8,1);
  260. 	At.Insert(9,1);
  261.     At.Insert(10,1);
  262. 	At.Insert(11,1);
  263. 	At.Inorder();
  264. 	cout<<At.IsBalance()<<endl;
  265.  
  266. }
  267. void TestAVLtree2()
  268. {
  269. 	
  270. 	AVLtree<int,int> At;
  271. 	At.Insert(4,1);
  272. 	At.Insert(15,1);
  273. 	At.Insert(16,1);
  274. 	At.Inorder();
  275. 	cout<<At.IsBalance()<<endl;
  276.  
  277. }
  278. void TestAVLtree3()
  279. {
  280.  
  281. 	AVLtree<int,int> At;
  282. 	At.Insert(16,1);
  283. 	At.Insert(26,1);
  284. 	At.Insert(18,1);
  285. 	At.Insert(14,1);
  286. 	At.Inorder();
  287. 	cout<<At.IsBalanceOP()<<endl;
  288.  
  289. }

main.cpp 
  1. #include "AVLtree.h"
  2. #include <cstdlib>
  3. int main()
  4. {
  5. 	TestAVLtree1();
  6. 	TestAVLtree2();
  7. 	TestAVLtree3();
  8. 	system("pause");
  9. 	return 0;
  10. }

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test