编程练习——平衡树（AVLTree）

AVLTree本身就是二叉查找树。为了保证查找效率在O(nlogn),所以有时要对树高进行必要的调整。

AVLTree拥有自己的法则使得插入、删除、查找都在O(nlogn)时间内完成。

下面写了一个AVLTreeNode类，好像和TreeNode类一样。

下面写AVLTree类，这个类重要的地方在与插入和删除操作。查找操作和BinarySearchTree一致。但是至今还没有找到一个有效的方法来使用BinarySearchTree中的Search。除非将Search方法抽象为一个接口。

暂时先不管太多。

先看左旋和右旋操作。

1. //returnthesubRoot
2. //ab
3. /////
4. //b->ca
5. ///
6. //c
7. AVLNode<T>*LLRotate(AVLNode<T>*a,AVLNode<T>*b)
8. {
9. a->setLeft(b->getRight());
10. b->setRight(a);
12. a->setAHeight(0);
13. b->setAHeight(0);
14. //a->setAHeight(getAVLHeight(a));
15. //b->setAHeight(getAVLHeight(b));
16. returnb;
17. }
19. //returnthesubRoot
20. //ab
21. /////
22. //b->ac
23. ///
24. //c
25. AVLNode<T>*RRRotate(AVLNode<T>*a,AVLNode<T>*b)
26. {
27. a->setRight(b->getLeft());
28. b->setLeft(a);
30. a->setAHeight(0);
31. b->setAHeight(0);
32. //a->setAHeight(getAVLHeight(a));
33. //b->setAHeight(getAVLHeight(b));
34. returnb;
35. }
38. //returnthesubRoot
39. //ac
40. /////
41. //b->ab
42. ////
43. //cd
44. ///
45. //d
46. AVLNode<T>*RLRotate(AVLNode<T>*a,AVLNode<T>*b,AVLNode<T>*c)
47. {
49. b->setLeft(c->getRight());
50. c->setRight(b);
51. a->setRight(c->getLeft());
52. c->setLeft(a);
55. //a->setAHeight(getAVLHeight(a));
56. //c->setAHeight(getAVLHeight(c));
57. //b->setAHeight(getAVLHeight(b));
59. if(c->getAbsoluteAHeight()==1)
60. {
61. if(b->getAHeight()==0)
62. {
63. b->setAHeight(-1);
64. }
65. else
66. {
67. b->setAHeight(0);
68. }
69. a->setAHeight(1);
70. c->setAHeight(0);
72. }
73. else
74. {
75. if(b->getAHeight()==0)
76. {
77. b->setAHeight(-1);
78. }
79. else
80. {
81. b->setAHeight(0);
82. }
83. a->setAHeight(0);
84. c->setAHeight(0);
86. }
89. returnc;
90. }
92. //returnthesubRoot
93. //ac
94. /////
95. //b->ba
96. ////
97. //cd
98. ///
99. //d
100. AVLNode<T>*LRRotate(AVLNode<T>*a,AVLNode<T>*b,AVLNode<T>*c)
101. {
102. b->setRight(c->getLeft());
103. c->setLeft(b);
104. a->setLeft(c->getRight());
105. c->setRight(a);
108. //a->setAHeight(getAVLHeight(a));
109. //c->setAHeight(getAVLHeight(c));
110. //b->setAHeight(getAVLHeight(b));
112. if(c->getAbsoluteAHeight()==1)
113. {
114. if(b->getAHeight()==0)
115. {
116. b->setAHeight(1);
117. }
118. else
119. {
120. b->setAHeight(0);
121. }
123. a->setAHeight(-1);
124. c->setAHeight(0);
126. }
127. else
128. {
130. if(b->getAHeight()==0)
131. {
132. b->setAHeight(1);
133. }
134. else
135. {
136. b->setAHeight(0);
137. }
138. a->setAHeight(0);
139. c->setAHeight(0);
141. }
146. returnc;
147. }

这里旋转后调整平衡因子是关键部分。这是我自己总结的方法，经少量测试暂时没有出现问题。这个调整方法好像与大多数书本和网络程序的方法不一致。不清楚到底哪个是正确的。但是如果不使用这种直接赋值的方法，可以使用递归查找树高的方法保障万无一失的解决这个问题。这里使用的右树高减左树高得平衡因子的方法。

下面给出这样的两个函数，其中getAVLHeight是核心方法。

1. intgetHeight(AVLNode<T>*node)
2. {
3. if(node==NULL)
4. {
5. return0;
6. }
7. else
8. {
9. intleftHeight=getHeight(node->getLeft());
10. intrightHeight=getHeight(node->getRight());
11. if(leftHeight>rightHeight)
12. {
13. returnleftHeight+1;
14. }
15. else
16. {
17. returnrightHeight+1;
18. }
19. }
20. }
22. intgetAVLHeight(AVLNode<T>*node)
23. {
24. if(node==NULL)
25. {
26. return0;
27. }
28. else
29. {
30. intleftHeight=getHeight(node->getLeft());
31. intrightHeight=getHeight(node->getRight());
32. returnrightHeight-leftHeight;
33. }
34. }

删除、插入操作有点复杂。

插入操作：

1.先找到可能要调整的那个节点A，这里的可能要调整的节点即为插入路径中平衡因子为+1或者为-1的点。（这里一定要记得不要自作聪明的认为如果向左插入，+1节点就不会是可能节点）

2.插入应该插入的节点，调整从A至目标节点的平衡因子。并且记录是否增长了子树树高（是否插入节点没有兄弟节点）。

3.插入后查看是否增长子树树高，如果增长树高，再查看A是否已经不平衡。如果不平衡，调整，否则，插入完成。

（这里要注意A节点为树根的情况，或者无A节点的情况）

因为下面的程序首先将树根设定为可能要调整的节点A，所以没有出现无A节点的情况。

以上三点，我看过很多教科书，发现讲解有些含糊，或者本身就是略写。这里并没有采用递归操作。

1. voidinsertNode(AVLNode<T>*node)
2. {
3. AVLNode<T>*subRoot=this->head;
4. if(subRoot==NULL)
5. {
6. subRoot=node;
7. return;
8. }
9. AVLNode<T>*ppoRoot=NULL;
10. AVLNode<T>*poRoot=NULL;
11. AVLNode<T>*pRoot=NULL;
15. poRoot=subRoot;
17. while(subRoot!=NULL)
18. {
19. pRoot=subRoot;
20. if(subRoot->getData()>node->getData())
21. {
23. if(isPossibleNode(subRoot->getLeft(),node))
24. {
25. poRoot=subRoot->getLeft();
26. ppoRoot=subRoot;
27. }
28. subRoot=subRoot->getLeft();
30. }
31. elseif(subRoot->getData()<node->getData())
32. {
34. if(isPossibleNode(subRoot->getRight(),node))
35. {
36. poRoot=subRoot->getRight();
37. ppoRoot=subRoot;
38. }
39. subRoot=subRoot->getRight();
40. }
41. else
42. {
43. throw"thesamekey";
44. }
45. }
47. boolisChangeHeight=false;
48. if(pRoot->getData()>node->getData())
49. {
51. pRoot->setLeft(node);
52. if(pRoot->getRight()==NULL)
53. {
54. isChangeHeight=true;
55. }
56. else
57. {
58. pRoot->setAHeight(pRoot->getAHeight()-1);
59. }
60. }
61. elseif(pRoot->getData()<node->getData())
62. {
64. pRoot->setRight(node);
65. if(pRoot->getLeft()==NULL)
66. {
67. isChangeHeight=true;
68. }
69. else
70. {
71. pRoot->setAHeight(pRoot->getAHeight()+1);
72. }
73. }
76. if(poRoot!=NULL&&isChangeHeight)
77. {
78. //s->aupdateHeight
79. subRoot=poRoot;
80. while(subRoot!=node)
81. {
82. if(subRoot->getData()>node->getData())
83. {
84. subRoot->setAHeight(subRoot->getAHeight()-1);
86. subRoot=subRoot->getLeft();
88. }
89. elseif(subRoot->getData()<node->getData())
90. {
91. subRoot->setAHeight(subRoot->getAHeight()+1);
93. subRoot=subRoot->getRight();
95. }
97. }
99. subRoot=poRoot;
100. AVLNode<T>*a=poRoot;
101. AVLNode<T>*b=NULL;
102. AVLNode<T>*c=NULL;
103. AVLNode<T>*tempRoot=NULL;
104. if(a->getAbsoluteAHeight()>1)
105. {
106. if(subRoot->getData()>node->getData())
107. {
108. b=subRoot->getLeft();
109. if(a->getAHeight()*b->getAHeight()>0)
110. {
111. //LLRotate
112. tempRoot=LLRotate(a,b);
114. }
115. else
116. {
117. //LRRotate
118. c=b->getRight();
119. tempRoot=LRRotate(a,b,c);
120. }
122. }
123. elseif(subRoot->getData()<node->getData())
124. {
125. b=subRoot->getRight();
126. if(a->getAHeight()*b->getAHeight()>0)
127. {
128. //RRRotate
129. tempRoot=RRRotate(a,b);
130. }
131. else
132. {
133. //RLRotate
134. c=b->getLeft();
135. tempRoot=RLRotate(a,b,c);
136. }
137. }
138. if(ppoRoot!=NULL)
139. {
140. if(ppoRoot->getData()>tempRoot->getData())
141. {
142. ppoRoot->setLeft(tempRoot);
143. }
144. else
145. {
146. ppoRoot->setRight(tempRoot);
147. }
148. }
149. else
150. {
151. this->head=tempRoot;
152. }
153. }
156. }
158. }

再看删除操作。

采用的是http://www.cs.uga.edu/~eileen/2720/Notes/AVLTrees-II.ppt这个ppt介绍的删除操作。

因为删除操作要反遍历到树根，所以这里无奈采用是递归操作。

bool deleteNode(AVLNode<T>* subRoot, AVLNode<T>* prev, T& node);

这个操作返回值：如果子树树高变化，那么返回true,否则返回false。

1.如果子树为Null，函数返回false

2.比较subRoot里的data值和node中的data值。

A.如果subRoot->data< node.data,需要递归下右子树，如果这个递归返回true,将subRoot的平衡因子调整为-1，如果为false就return false。

B.subRoot->data> node.data需要递归下左子树，如果这个递归返回true,将subRoot的平衡因子调整为+1，如果为false就return false。

C.subRoot->data== node.data.

1）如果此时subRoot只有一个孩子或者没有孩子，那么删除时树高一定会改变。另外做一个简单的删除操作即可。该左孩子代替此节点还是右孩子代替它，如何代替其实和BinarySearchTree一样。再return true

2）如果有两个孩子，去左子树中找到替代品，然后将这个subRoot的数据域完全变为此替代品后，去左子树中用再用deleteNode方法将替代品删除。如果deleteNode操作返回true，那么显然subRoot的平衡因子要加1.

3.如果subRoot的平衡因子已经为2或者-2，那么以subRoot为根开始调整。

A.如果调整后subRoot平衡因子为0，return true

B.不为0，return false。

下面是实际代码

1. booldeleteNode(AVLNode<T>*subRoot,AVLNode<T>*prev,T&node)
2. {
3. if(subRoot==NULL)
4. {
5. returnfalse;
6. }
7. boolisChangeHeight=false;
8. if(subRoot->getData()>node)
9. {
10. isChangeHeight=deleteNode(subRoot->getLeft(),subRoot,node);
11. if(isChangeHeight)
12. {
13. subRoot->setAHeight(subRoot->getAHeight()+1);
14. }
16. }
17. elseif(subRoot->getData()<node)
18. {
19. isChangeHeight=deleteNode(subRoot->getRight(),subRoot,node);
20. if(isChangeHeight)
21. {
22. subRoot->setAHeight(subRoot->getAHeight()-1);
23. }
25. }
26. else
27. {
28. AVLNode<T>*assignNode=NULL;
29. if(subRoot->getLeft()==NULL&&subRoot->getRight()==NULL)
30. {
31. //nochild
33. isChangeHeight=true;
34. deleteNode(subRoot,prev,assignNode);
35. returnisChangeHeight;
36. }
37. elseif(subRoot->getLeft()==NULL&&subRoot->getRight()!=NULL)
38. {
39. //noleftchild
40. isChangeHeight=true;
41. assignNode=subRoot->getRight();
42. deleteNode(subRoot,prev,assignNode);
43. returnisChangeHeight;
45. }
46. elseif(subRoot->getRight()==NULL&&subRoot->getLeft()!=NULL)
47. {
48. //norightchlid
49. isChangeHeight=true;
50. assignNode=subRoot->getLeft();
51. deleteNode(subRoot,prev,assignNode);
52. returnisChangeHeight;
53. }
54. else
55. {
56. //havebothchildren
57. assignNode=getMaxNode(subRoot->getLeft());
58. Tdata=assignNode->getData();
59. boolisChange=deleteNode(subRoot->getLeft(),subRoot,data);
60. cout<<"use"<<data<<"replace"<<subRoot->getData()<<endl;
61. subRoot->setData(data);//copyalldatatosubRoot
63. if(isChange)
64. {
65. subRoot->setAHeight(subRoot->getAHeight()+1);
66. }
67. }
69. if(subRoot->getAbsoluteAHeight()==2)
70. {
71. AVLNode<T>*a=subRoot;
72. AVLNode<T>*b=NULL;
73. AVLNode<T>*c=NULL;
74. AVLNode<T>*tempRoot=NULL;
75. if(subRoot->getAHeight()==2)
76. {
77. //movetoleft
78. b=subRoot->getRight();
79. switch(b->getAHeight())
80. {
81. case1:
82. tempRoot=RRRotate(a,b);
83. isChangeHeight=true;
84. break;
85. case-1:
86. c=b->getLeft();
87. tempRoot=RLRotate(a,b,c);
88. isChangeHeight=true;
89. break;
90. case0:
91. tempRoot=RRRotate(a,b);
92. isChangeHeight=false;
93. break;
94. }
96. }
97. elseif(subRoot->getAHeight()==-2)
98. {
99. //movetoright
100. b=subRoot->getLeft();
101. switch(b->getAHeight())
102. {
103. case1:
104. c=b->getRight();
105. tempRoot=LRRotate(a,b,c);
106. isChangeHeight=true;
108. break;
109. case-1:
110. tempRoot=LLRotate(a,b);
111. isChangeHeight=true;
112. break;
113. case0:
114. tempRoot=LLRotate(a,b);
115. isChangeHeight=false;
116. break;
117. }
119. }
121. if(prev==NULL)
122. {
123. this->head=tempRoot;
124. }
125. else
126. {
127. if(prev->getData()>tempRoot->getData())
128. {
129. prev->setLeft(tempRoot);
130. }
131. else
132. {
133. prev->setRight(tempRoot);
134. }
135. }
136. }
140. }
142. returnisChangeHeight;
144. }

最后贴上AVLTree的完整类代码

1. #include"AVLNode.h"
3. template<classT>
4. classAVLTree
5. {
6. private:
7. AVLNode<T>*head;
9. intgetHeight(AVLNode<T>*node)
10. {
11. if(node==NULL)
12. {
13. return0;
14. }
15. else
16. {
17. intleftHeight=getHeight(node->getLeft());
18. intrightHeight=getHeight(node->getRight());
19. if(leftHeight>rightHeight)
20. {
21. returnleftHeight+1;
22. }
23. else
24. {
25. returnrightHeight+1;
26. }
27. }
28. }
30. intgetAVLHeight(AVLNode<T>*node)
31. {
32. if(node==NULL)
33. {
34. return0;
35. }
36. else
37. {
38. intleftHeight=getHeight(node->getLeft());
39. intrightHeight=getHeight(node->getRight());
40. returnrightHeight-leftHeight;
41. }
42. }
45. voidclearSubTree(AVLNode<T>*node)
46. {
47. if(node!=NULL)
48. {
49. clearSubTree(node->getLeft());
50. clearSubTree(node->getRight());
51. deletenode;
52. }
53. }
55. voidprintTree(AVLNode<T>*subTree,intcount)
56. {
57. if(subTree!=NULL)
58. {
60. printTree(subTree->getRight(),count+1);
61. for(inti=0;i<count;i++)
62. {
63. cout<<"";
64. }
65. cout<<subTree->getData()<<endl;
66. printTree(subTree->getLeft(),count+1);
67. }
68. }
71. voidprintInMidOrder(AVLNode<T>*subTree)
72. {
73. if(subTree!=NULL)
74. {
75. printInMidOrder(subTree->getLeft());
78. cout<<subTree->getData()<<endl;
79. printInMidOrder(subTree->getRight());
80. }
81. }
83. boolisPossibleNode(AVLNode<T>*node,AVLNode<T>*comNode)
84. {
85. if(node!=NULL&&node->getAbsoluteAHeight()==1)
86. {
87. returntrue;
88. }
89. returnfalse;
90. }
92. voidinsertNode(AVLNode<T>*node)
93. {
94. AVLNode<T>*subRoot=this->head;
95. if(subRoot==NULL)
96. {
97. subRoot=node;
98. return;
99. }
100. AVLNode<T>*ppoRoot=NULL;
101. AVLNode<T>*poRoot=NULL;
102. AVLNode<T>*pRoot=NULL;
106. poRoot=subRoot;
108. while(subRoot!=NULL)
109. {
110. pRoot=subRoot;
111. if(subRoot->getData()>node->getData())
112. {
114. if(isPossibleNode(subRoot->getLeft(),node))
115. {
116. poRoot=subRoot->getLeft();
117. ppoRoot=subRoot;
118. }
119. subRoot=subRoot->getLeft();
121. }
122. elseif(subRoot->getData()<node->getData())
123. {
125. if(isPossibleNode(subRoot->getRight(),node))
126. {
127. poRoot=subRoot->getRight();
128. ppoRoot=subRoot;
129. }
130. subRoot=subRoot->getRight();
131. }
132. else
133. {
134. throw"thesamekey";
135. }
136. }
138. boolisChangeHeight=false;
139. if(pRoot->getData()>node->getData())
140. {
142. pRoot->setLeft(node);
143. if(pRoot->getRight()==NULL)
144. {
145. isChangeHeight=true;
146. }
147. else
148. {
149. pRoot->setAHeight(pRoot->getAHeight()-1);
150. }
151. }
152. elseif(pRoot->getData()<node->getData())
153. {
155. pRoot->setRight(node);
156. if(pRoot->getLeft()==NULL)
157. {
158. isChangeHeight=true;
159. }
160. else
161. {
162. pRoot->setAHeight(pRoot->getAHeight()+1);
163. }
164. }
167. if(poRoot!=NULL&&isChangeHeight)
168. {
169. //s->aupdateHeight
170. subRoot=poRoot;
171. while(subRoot!=node)
172. {
173. if(subRoot->getData()>node->getData())
174. {
175. subRoot->setAHeight(subRoot->getAHeight()-1);
177. subRoot=subRoot->getLeft();
179. }
180. elseif(subRoot->getData()<node->getData())
181. {
182. subRoot->setAHeight(subRoot->getAHeight()+1);
184. subRoot=subRoot->getRight();
186. }
188. }
190. subRoot=poRoot;
191. AVLNode<T>*a=poRoot;
192. AVLNode<T>*b=NULL;
193. AVLNode<T>*c=NULL;
194. AVLNode<T>*tempRoot=NULL;
195. if(a->getAbsoluteAHeight()>1)
196. {
197. if(subRoot->getData()>node->getData())
198. {
199. b=subRoot->getLeft();
200. if(a->getAHeight()*b->getAHeight()>0)
201. {
202. //LLRotate
203. tempRoot=LLRotate(a,b);
205. }
206. else
207. {
208. //LRRotate
209. c=b->getRight();
210. tempRoot=LRRotate(a,b,c);
211. }
213. }
214. elseif(subRoot->getData()<node->getData())
215. {
216. b=subRoot->getRight();
217. if(a->getAHeight()*b->getAHeight()>0)
218. {
219. //RRRotate
220. tempRoot=RRRotate(a,b);
221. }
222. else
223. {
224. //RLRotate
225. c=b->getLeft();
226. tempRoot=RLRotate(a,b,c);
227. }
228. }
229. if(ppoRoot!=NULL)
230. {
231. if(ppoRoot->getData()>tempRoot->getData())
232. {
233. ppoRoot->setLeft(tempRoot);
234. }
235. else
236. {
237. ppoRoot->setRight(tempRoot);
238. }
239. }
240. else
241. {
242. this->head=tempRoot;
243. }
244. }
247. }
249. }
252. //returnthesubRoot
253. //ab
254. /////
255. //b->ca
256. ///
257. //c
258. AVLNode<T>*LLRotate(AVLNode<T>*a,AVLNode<T>*b)
259. {
260. a->setLeft(b->getRight());
261. b->setRight(a);
263. a->setAHeight(0);
264. b->setAHeight(0);
265. //a->setAHeight(getAVLHeight(a));
266. //b->setAHeight(getAVLHeight(b));
267. returnb;
268. }
270. //returnthesubRoot
271. //ab
272. /////
273. //b->ac
274. ///
275. //c
276. AVLNode<T>*RRRotate(AVLNode<T>*a,AVLNode<T>*b)
277. {
278. a->setRight(b->getLeft());
279. b->setLeft(a);
281. a->setAHeight(0);
282. b->setAHeight(0);
283. //a->setAHeight(getAVLHeight(a));
284. //b->setAHeight(getAVLHeight(b));
285. returnb;
286. }
289. //returnthesubRoot
290. //ac
291. /////
292. //b->ab
293. ////
294. //cd
295. ///
296. //d
297. AVLNode<T>*RLRotate(AVLNode<T>*a,AVLNode<T>*b,AVLNode<T>*c)
298. {
300. b->setLeft(c->getRight());
301. c->setRight(b);
302. a->setRight(c->getLeft());
303. c->setLeft(a);
306. //a->setAHeight(getAVLHeight(a));
307. //c->setAHeight(getAVLHeight(c));
308. //b->setAHeight(getAVLHeight(b));
310. if(c->getAbsoluteAHeight()==1)
311. {
312. if(b->getAHeight()==0)
313. {
314. b->setAHeight(-1);
315. }
316. else
317. {
318. b->setAHeight(0);
319. }
320. a->setAHeight(1);
321. c->setAHeight(0);
323. }
324. else
325. {
326. if(b->getAHeight()==0)
327. {
328. b->setAHeight(-1);
329. }
330. else
331. {
332. b->setAHeight(0);
333. }
334. a->setAHeight(0);
335. c->setAHeight(0);
337. }
340. returnc;
341. }
343. //returnthesubRoot
344. //ac
345. /////
346. //b->ba
347. ////
348. //cd
349. ///
350. //d
351. AVLNode<T>*LRRotate(AVLNode<T>*a,AVLNode<T>*b,AVLNode<T>*c)
352. {
353. b->setRight(c->getLeft());
354. c->setLeft(b);
355. a->setLeft(c->getRight());
356. c->setRight(a);
359. //a->setAHeight(getAVLHeight(a));
360. //c->setAHeight(getAVLHeight(c));
361. //b->setAHeight(getAVLHeight(b));
363. if(c->getAbsoluteAHeight()==1)
364. {
365. if(b->getAHeight()==0)
366. {
367. b->setAHeight(1);
368. }
369. else
370. {
371. b->setAHeight(0);
372. }
374. a->setAHeight(-1);
375. c->setAHeight(0);
377. }
378. else
379. {
381. if(b->getAHeight()==0)
382. {
383. b->setAHeight(1);
384. }
385. else
386. {
387. b->setAHeight(0);
388. }
389. a->setAHeight(0);
390. c->setAHeight(0);
392. }
397. returnc;
398. }
401. AVLNode<T>*getMaxNode(AVLNode<T>*subRoot)
402. {
403. if(subRoot==NULL)
404. {
405. returnNULL;
406. }
407. if(subRoot->getRight()==NULL)
408. {
409. returnsubRoot;
410. }
411. else
412. {
413. returngetMaxNode(subRoot->getRight());
414. }
415. }
417. voiddeleteNode(AVLNode<T>*subRoot,AVLNode<T>*prev,AVLNode<T>*assignNode)
418. {
419. if(prev==NULL)
420. {
421. this->head=assignNode;
423. }
424. else
425. {
426. if(prev->getLeft()==subRoot)
427. {
428. prev->setLeft(assignNode);
430. }
431. elseif(prev->getRight()==subRoot)
432. {
433. prev->setRight(assignNode);
435. }
436. }
438. deletesubRoot;
439. }
441. booldeleteNode(AVLNode<T>*subRoot,AVLNode<T>*prev,T&node)
442. {
443. if(subRoot==NULL)
444. {
445. returnfalse;
446. }
447. boolisChangeHeight=false;
448. if(subRoot->getData()>node)
449. {
450. isChangeHeight=deleteNode(subRoot->getLeft(),subRoot,node);
451. if(isChangeHeight)
452. {
453. subRoot->setAHeight(subRoot->getAHeight()+1);
454. }
456. }
457. elseif(subRoot->getData()<node)
458. {
459. isChangeHeight=deleteNode(subRoot->getRight(),subRoot,node);
460. if(isChangeHeight)
461. {
462. subRoot->setAHeight(subRoot->getAHeight()-1);
463. }
465. }
466. else
467. {
468. AVLNode<T>*assignNode=NULL;
469. if(subRoot->getLeft()==NULL&&subRoot->getRight()==NULL)
470. {
471. //nochild
473. isChangeHeight=true;
474. deleteNode(subRoot,prev,assignNode);
475. returnisChangeHeight;
476. }
477. elseif(subRoot->getLeft()==NULL&&subRoot->getRight()!=NULL)
478. {
479. //noleftchild
480. isChangeHeight=true;
481. assignNode=subRoot->getRight();
482. deleteNode(subRoot,prev,assignNode);
483. returnisChangeHeight;
485. }
486. elseif(subRoot->getRight()==NULL&&subRoot->getLeft()!=NULL)
487. {
488. //norightchlid
489. isChangeHeight=true;
490. assignNode=subRoot->getLeft();
491. deleteNode(subRoot,prev,assignNode);
492. returnisChangeHeight;
493. }
494. else
495. {
496. //havebothchildren
497. assignNode=getMaxNode(subRoot->getLeft());
498. Tdata=assignNode->getData();
499. boolisChange=deleteNode(subRoot->getLeft(),subRoot,data);
500. cout<<"use"<<data<<"replace"<<subRoot->getData()<<endl;
501. subRoot->setData(data);//copyalldatatosubRoot
503. if(isChange)
504. {
505. subRoot->setAHeight(subRoot->getAHeight()+1);
506. }
507. }
509. if(subRoot->getAbsoluteAHeight()==2)
510. {
511. AVLNode<T>*a=subRoot;
512. AVLNode<T>*b=NULL;
513. AVLNode<T>*c=NULL;
514. AVLNode<T>*tempRoot=NULL;
515. if(subRoot->getAHeight()==2)
516. {
517. //movetoleft
518. b=subRoot->getRight();
519. switch(b->getAHeight())
520. {
521. case1:
522. tempRoot=RRRotate(a,b);
523. isChangeHeight=true;
524. break;
525. case-1:
526. c=b->getLeft();
527. tempRoot=RLRotate(a,b,c);
528. isChangeHeight=true;
529. break;
530. case0:
531. tempRoot=RRRotate(a,b);
532. isChangeHeight=false;
533. break;
534. }
536. }
537. elseif(subRoot->getAHeight()==-2)
538. {
539. //movetoright
540. b=subRoot->getLeft();
541. switch(b->getAHeight())
542. {
543. case1:
544. c=b->getRight();
545. tempRoot=LRRotate(a,b,c);
546. isChangeHeight=true;
548. break;
549. case-1:
550. tempRoot=LLRotate(a,b);
551. isChangeHeight=true;
552. break;
553. case0:
554. tempRoot=LLRotate(a,b);
555. isChangeHeight=false;
556. break;
557. }
559. }
561. if(prev==NULL)
562. {
563. this->head=tempRoot;
564. }
565. else
566. {
567. if(prev->getData()>tempRoot->getData())
568. {
569. prev->setLeft(tempRoot);
570. }
571. else
572. {
573. prev->setRight(tempRoot);
574. }
575. }
576. }
580. }
582. returnisChangeHeight;
584. }
588. public:
589. AVLTree(T&data)
590. {
591. head=newAVLNode<T>(data);
592. }
594. AVLTree(AVLNode<T>*head)
595. {
596. clearSubTree(this->head);
597. this->head=head;
598. }
600. ~AVLTree()
601. {
602. clearSubTree(head);
603. }
605. voidprintTree()
606. {
607. printTree(this->head,0);
608. }
610. voidprintInMidOrder()
611. {
612. printInMidOrder(this->head);
613. }
616. voidinsertNode(T&data)
617. {
618. insertNode(newAVLNode<T>(data));
620. }
622. voiddeleteNode(T&data)
623. {
624. deleteNode(this->head,NULL,data);
625. }
626. /*boolisUnbalancePoint(AVLNode<T>*node,AVLNode<T>*compareNode)
627. {
629. if(node->getAbsoluteAHeight()==1)
630. {
632. if(node->getAHeight==1&&node->getData()<compareNode->getData())
633. {
634. returntrue;
635. }
636. elseif(node->getAHeight==-1&&node->getData()>compareNode->getData())
637. {
638. returntrue;
639. }
640. }
641. returnfalse;
642. }*/
645. };