【数据结构】AVL树

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

AVL树,是一棵平衡搜索二叉树,既满足搜索树的性质(见二叉搜索树的文章链接二叉搜索树),又满足平衡树

性质(左右子树的高度差不大于2)。

在二叉搜索树中,我们知道要插入一个元素,必须将他插到合适的位置,但是在AVL树中,不仅要插入到合适的位

置,还要保证插入该元素之后这棵树是平衡搜索二叉树。

关于如何调整一棵二叉树为平衡二叉树,这里就涉及到四种旋转:

左单旋,右单旋,左右双旋,右左双旋。

下边就每一种旋转都给出图示:

左单旋:


右单旋:与左单旋同理。

左双旋:



右双旋:情形类似于右左双旋。

说到平衡树,那么如何判断一棵二叉树是不是平衡二叉树???

思路一:如果我们可以计算出左子树的高度和右子树的高度,两者做差看是否符合平衡树的条件。这样一来,我们会

遍历这棵树两次,导致效率就能低下一些。

思路二:如果我们每一次遍历,都会带回树的高度,这样就会少遍历一次,时间复杂度是0(N)。下边给出完整代

码:

  1. #pragma once
  2. #include<iostream>
  3. using namespace std;
  4. #include<stack>
  5.  
  6. template<typename K,typename V>
  7. struct AVLTreeNode
  8. {
  9. K _key;
  10. V _value;
  11.  
  12. AVLTreeNode<K,V>* _left;
  13. AVLTreeNode<K,V>* _right;
  14. AVLTreeNode<K,V>* _parent;
  15.  
  16. int _bf;
  17. AVLTreeNode(const K& key,const V& value = 0)
  18. :_key(key),_value(value),_left(NULL),_right(NULL),_parent(NULL),_bf(0)
  19. {}
  20. };
  21. template<typename K,typename V>
  22. class AVLTree
  23. {
  24. typedef AVLTreeNode<K,V> Node;
  25. public:
  26. AVLTree()
  27. :_root(NULL)
  28. {}
  29. ~AVLTree()
  30. {
  31. _Destroy(_root);
  32. }
  33. bool InsertNonR(const K& key)
  34. {
  35. if (_root == NULL)
  36. {
  37. _root = new Node(key);
  38. _root->_parent = NULL;
  39. return true;
  40. }
  41. Node* cur = _root;
  42. Node* parent = _root;
  43. while (cur)
  44. {
  45. //找插入位置
  46. if (cur->_key < key)
  47. {
  48. parent = cur;
  49. cur = cur->_right;
  50. }
  51. else if (cur->_key > key)
  52. {
  53. parent = cur;
  54. cur = cur->_left;
  55. }
  56. //无法插入
  57. else
  58. return false;
  59. }
  60. cur = new Node(key);
  61. cur->_parent = parent;
  62. if (parent->_key < key)
  63. {
  64. parent->_right = cur;
  65. }
  66. else
  67. {
  68. parent->_left = cur;
  69. }
  70.  
  71. while (parent)//调整到根节点之后就不再调整
  72. {
  73. //if (parent->_parent && parent->_parent->_left == parent)
  74. if(cur == parent->_left)
  75. --parent->_bf;
  76. else if (cur == parent->_right) //if (parent->_parent->_right == parent)
  77. ++parent->_bf;
  78.  
  79. if (parent->_bf == 0)//说明parent的高度并没有改变,此时调整结束
  80. return true;
  81. else if (parent->_bf == 1 || parent->_bf == -1)
  82. {
  83. cur = parent;
  84. parent = parent->_parent;
  85. }
  86. else
  87. {
  88. if (parent->_bf == 2)//树已经不平衡,需要调整
  89. {
  90. if (cur->_bf == 1)
  91. _RotateL(parent);
  92. else //if (cur->_bf == -1)
  93. _RotateRL(parent);
  94. }
  95. // if (parent->_bf == -2)
  96. else
  97. {
  98. if (cur->_bf == -1)
  99. _RotateR(parent);
  100. else //if (cur->_bf == 1)
  101. _RotateLR(parent);
  102. }
  103. }
  104. }
  105. return true;
  106. }
  107. void InOrderNonR()
  108. {
  109. if (_root == NULL)
  110. return;
  111. stack<Node*> s;
  112. Node* cur = _root;
  113. while (cur || !s.empty())
  114. {
  115. while (cur)
  116. {
  117. s.push(cur);
  118. cur = cur->_left;
  119. }
  120. Node* top = s.top();
  121. s.pop();
  122. cout << top->_key << " ";
  123. cur = top->_right;
  124. }
  125. cout << endl;
  126. }
  127. bool IsBalance()
  128. {
  129. return _IsBalance(_root);
  130. }
  131. bool IsBalanceOP()
  132. {
  133. int height = 0;
  134. return _IsBalanceOP(_root,height);
  135. }
  136. size_t Height()
  137. {
  138. return _Height(_root);
  139. }
  140. bool Remove(const K& key)
  141. {
  142. if (_root == NULL)
  143. return false;
  144. Node* cur = _root;
  145. Node* parent = NULL;
  146. Node* del = NULL;
  147. while (cur)
  148. {
  149. if (cur->_key < key)
  150. {
  151. parent = cur;
  152. cur = cur->_right;
  153. }
  154. else if (cur->_key > key)
  155. {
  156. parent = cur;
  157. cur = cur->_left;
  158. }
  159. else//找到所要删除的元素
  160. {
  161. if (cur->_left == NULL && cur->_right == NULL)//叶子结点
  162. {
  163. if (parent && parent->_left == cur)
  164. {
  165. parent->_left = NULL;
  166. parent->_bf++;
  167. del = cur;
  168. }
  169. else if (parent && parent->_right == cur)
  170. {
  171. parent->_right = NULL;
  172. parent->_bf--;
  173. del = cur;
  174. }
  175. else
  176. {
  177. del = _root;
  178. _root->_parent = NULL;
  179. }
  180. }
  181. else if (cur->_left == NULL || cur->_right == NULL)
  182. {
  183. if (cur->_right != NULL)
  184. {
  185. if (parent == NULL)
  186. {
  187. _root = cur->_right;
  188. _root->_parent = NULL;
  189. }
  190. if (parent->_right == cur)//只有右孩子
  191. {
  192. parent->_right = cur->_right;
  193. parent->_bf--;
  194. }
  195. else if (parent->_left == cur)
  196. {
  197. parent->_left = cur->_right;
  198. ++parent->_bf;
  199. }
  200. }
  201. else//只有左孩子
  202. {
  203. if (parent == NULL)
  204. {
  205. _root = cur->_left;
  206. _root->_parent = NULL;
  207. }
  208. else if (parent->_left == cur)
  209. {
  210. parent->_left = cur->_left;
  211. parent->_bf++;
  212. }
  213. else
  214. {
  215. parent->_right = cur->_left;
  216. parent->_bf--;
  217. }
  218. }
  219. del = cur;
  220. }
  221. else//有左右孩子
  222. {
  223. Node* minRight = cur->_right;
  224. //找右子树的最左结点
  225. while (minRight->_left)
  226. {
  227. parent = minRight;
  228. minRight = minRight->_left;
  229. }
  230. cur->_key = minRight->_key;
  231. if (parent->_left == minRight)
  232. {
  233. parent->_left = minRight->_right;
  234. parent->_bf++;
  235. }
  236. else if (parent->_right == minRight)
  237. {
  238. parent->_right = minRight->_right;
  239. parent->_bf--;
  240. }
  241. del = minRight;
  242. }
  243. while (parent)
  244. {
  245. cur = del;
  246. if (cur == parent->_left)
  247. ++parent->_bf;
  248. else if (cur == parent->_right)
  249. --parent->_bf;
  250.  
  251. if (parent->_bf == 0)
  252. {
  253. cur = parent;
  254. parent = parent->_parent;
  255. }
  256. else if (parent->_bf == 1 || parent->_bf == -1)
  257. {
  258. //高度没有改变,直接跳出
  259. break;
  260. }
  261. else
  262. {
  263. if (parent->_bf == 2)//树已经不平衡,需要调整
  264. {
  265. if (cur->_bf == 1)
  266. _RotateL(parent);
  267. else //if (cur->_bf == -1)
  268. _RotateRL(parent);
  269. }
  270. // if (parent->_bf == -2)
  271. else
  272. {
  273. if (cur->_bf == -1)
  274. _RotateR(parent);
  275. else //if (cur->_bf == 1)
  276. _RotateLR(parent);
  277. }
  278. }
  279. }
  280. delete del;
  281. del = NULL;
  282. return true;
  283. }
  284. }
  285. return false;
  286. }
  287. protected:
  288. //优化版本
  289. bool _IsBalanceOP(Node* root,int& height)
  290. {
  291. if (root == NULL)
  292. {
  293. height = 0;
  294. return true;
  295. }
  296. int leftHeight = 0;
  297. if (!_IsBalanceOP(root->_left,leftHeight))
  298. return false;
  299. int rightHeight = 0;
  300. if (!_IsBalanceOP(root->_right,rightHeight))
  301. return false;
  302. height = 1 + rightHeight > leftHeight ? rightHeight : leftHeight;
  303. return true;
  304. }
  305. size_t _Height(Node* root)
  306. {
  307. if (root == NULL)
  308. return 0;
  309. int leftHeight = _Height(root->_left);
  310. int rightHeight = _Height(root->_right);
  311. return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  312. }
  313. //大多数结点会计算两次,时间复杂度0(N*N)
  314. bool _IsBalance(Node* root)
  315. {
  316. if (root == NULL)
  317. return true;
  318. int leftHeight = _Height(root->_left);
  319. int rightHeight = _Height(root->_right);
  320.  
  321. if (rightHeight - leftHeight != root->_bf)
  322. {
  323. cout << "平衡因子异常" << root->_key << " ";
  324. }
  325.  
  326. return abs(rightHeight - leftHeight) < 2
  327. && _IsBalance(root->_left)
  328. && _IsBalance(root->_right);
  329. }
  330. void _RotateR(Node* parent)
  331. {
  332. Node* subL = parent->_left;
  333. Node* ppNode = parent->_parent;//记住parent的父节点
  334. Node* subLR = subL->_right;
  335.  
  336. //parent与subLR连接
  337. parent->_left = subLR;
  338. if (subLR != NULL)
  339. subLR->_parent = parent;
  340.  
  341. //parent与subL连接
  342. subL->_right = parent;
  343. parent->_parent = subL;
  344.  
  345. //ppNode与subL进行连接
  346. if (ppNode == NULL)
  347. {
  348. _root = subL;
  349. subL->_parent = NULL;
  350. }
  351. else
  352. {
  353. if (ppNode->_left == parent)
  354. ppNode->_left = subL;
  355. else
  356. ppNode->_right = subL;
  357. subL->_parent = ppNode;
  358.  
  359. }
  360. subL->_bf = parent->_bf = 0;
  361. }
  362. void _RotateL(Node* parent)
  363. {
  364. Node* subR = parent->_right;
  365. Node* ppNode = parent->_parent;//记住parent的父节点
  366. Node* subRL = subR->_left;
  367.  
  368. //subRL与parent相连
  369. parent->_right = subRL;
  370. if (subRL != NULL)
  371. subRL->_parent = parent;
  372.  
  373. //subR与parent相连接
  374. subR->_left = parent;
  375. parent->_parent = subR;
  376.  
  377. //ppNode与subR连接
  378. if (ppNode == NULL)
  379. {
  380. _root = subR;
  381. subR->_parent = NULL;
  382. }
  383. else
  384. {
  385. if (ppNode->_left == parent)
  386. ppNode->_left = subR;
  387. else
  388. ppNode->_right = subR;
  389. subR->_parent = ppNode;
  390. }
  391. parent->_bf = subR->_bf = 0;
  392. }
  393. void _RotateLR(Node* parent)
  394. {
  395. Node* subL = parent->_left;
  396. Node* subLR = subL->_right;
  397. int bf = subLR->_bf;
  398. _RotateL(parent->_left);
  399. _RotateR(parent);
  400. if (bf == 0)
  401. {
  402. parent->_bf = 0;
  403. subL->_bf = 0;
  404. subLR->_bf = 0;
  405. }
  406. else if (bf == 1)
  407. {
  408. parent->_bf = 0;
  409. subL->_bf = -1;
  410. subLR->_bf = 1;
  411. }
  412. else // bf == -1
  413. {
  414. parent->_bf = 1;
  415. subL->_bf = 0;
  416. subLR->_bf = -1;
  417. }
  418. }
  419. void _RotateRL(Node* parent)
  420. {
  421. Node* subR = parent->_right;
  422. Node* subRL = subR->_left;
  423. int bf = subRL->_bf;
  424. _RotateR(parent->_right);
  425. _RotateL(parent);
  426. if (bf == 0)
  427. {
  428. parent->_bf = 0;
  429. subR->_bf = 0;
  430. }
  431. else if (bf == 1)
  432. {
  433. parent->_bf = -1;
  434. subR->_bf = 0;
  435. subRL->_bf = 1;
  436. }
  437. else
  438. {
  439. parent->_bf = 0;
  440. subR->_bf = 1;
  441. subRL->_bf = -1;
  442. }
  443.  
  444. }
  445. void _Destroy(Node* root)
  446. {
  447. if (root == NULL)
  448. return;
  449. _Destroy(root->_left);
  450. _Destroy(root->_right);
  451. delete root;
  452. }
  453. private:
  454. Node* _root;
  455. };
  456. void TestAVL()
  457. {
  458. AVLTree<int,int> tree1;
  459. int array1[] = { 16,3,7,11,9,26,18,14,15 };
  460. for (int i = 0; i < sizeof(array1) / sizeof(array1[0]); ++i)
  461. {
  462. tree1.InsertNonR(array1[i]);
  463. }
  464. tree1.InOrderNonR();
  465. cout <<"IsBalance?"<< tree1.IsBalance() << endl;
  466. cout << "IsBalance?" << tree1.IsBalanceOP() << endl;
  467. tree1.Remove(16);
  468. tree1.Remove(3);
  469. tree1.Remove(7);
  470. tree1.Remove(11);
  471. tree1.InOrderNonR();//9 26 18 14 15
  472. tree1.Remove(9);
  473. tree1.Remove(26);
  474. tree1.Remove(18);
  475. tree1.Remove(15);
  476. tree1.InOrderNonR();//9 26 18 14 15
  477. cout << "IsBalance?" << tree1.IsBalance() << endl;
  478.  
  479. int array2[] = { 4,2,6,1,5,15,16,14 };
  480.  
  481. AVLTree<int,int> tree2;
  482. for (size_t i = 0;i<sizeof(array2) / sizeof(array2[0]);++i)
  483. {
  484. tree2.InsertNonR(array2[i]);
  485. }
  486. tree2.InOrderNonR();
  487. cout << "IsBalance?" << tree2.IsBalance() << endl;
  488. cout << "IsBalance?" << tree2.IsBalanceOP() << endl;
  489. tree2.Remove(5);
  490. tree2.InOrderNonR();
  491. }


关于AVL树,就到这里~

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