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

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

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

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

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

暂时先不管太多。

先看左旋和右旋操作。

1. // return the subRoot
2. //        a                   b
3. //       /                  /   /
4. //      b        ->        c     a
5. //     /
6. //    c
7. AVLNode* LLRotate(AVLNode* a, AVLNode* b)
8. {
9. a->setLeft(b->getRight());
10. b->setRight(a);
11. 12. a->setAHeight(0);
12. b->setAHeight(0);
13. //a->setAHeight(getAVLHeight(a));
14. //b->setAHeight(getAVLHeight(b));
15. return b;
16. }
17. 19. // return the subRoot
18. //        a                      b
19. //          /                  /   /
20. //            b        ->     a     c
21. //              /
22. //                c
23. AVLNode* RRRotate(AVLNode* a, AVLNode* b)
24. {
25. a->setRight(b->getLeft());
26. b->setLeft(a);
27. 30. a->setAHeight(0);
28. b->setAHeight(0);
29. //a->setAHeight(getAVLHeight(a));
30. //b->setAHeight(getAVLHeight(b));
31. return b;
32. }
33. 37. 38. // return the subRoot
34. //        a                      c
35. //          /                  /   /
36. //            b        ->     a     b
37. //           /                 /
38. //          c                   d
39. //         /
40. //        d
41. AVLNode* RLRotate(AVLNode* a, AVLNode* b, AVLNode* c)
42. {
43. 49. b->setLeft(c->getRight());
44. c->setRight(b);
45. a->setRight(c->getLeft());
46. c->setLeft(a);
47. 54. 55. //a->setAHeight(getAVLHeight(a));
48. //c->setAHeight(getAVLHeight©);
49. //b->setAHeight(getAVLHeight(b));
50. 59. if (c->getAbsoluteAHeight() == 1)
51. {
52. if (b->getAHeight() == 0)
53. {
54. b->setAHeight(-1);
55. }
56. else
57. {
58. b->setAHeight(0);
59. }
60. a->setAHeight(1);
61. c->setAHeight(0);
62. 72. }
63. else
64. {
65. if (b->getAHeight() == 0)
66. {
67. b->setAHeight(-1);
68. }
69. else
70. {
71. b->setAHeight(0);
72. }
73. a->setAHeight(0);
74. c->setAHeight(0);
75. 86. }
76. 88. 89. return c;
77. }
78. 92. // return the subRoot
79. //        a                      c
80. //       /                     /   /
81. //      b              ->     b     a
82. //       /                         /
83. //        c                       d
84. //         /
85. //          d
86. AVLNode* LRRotate(AVLNode* a, AVLNode* b, AVLNode* c)
87. {
88. b->setRight(c->getLeft());
89. c->setLeft(b);
90. a->setLeft(c->getRight());
91. c->setRight(a);
92. 107. 108. //a->setAHeight(getAVLHeight(a));
93. //c->setAHeight(getAVLHeight©);
94. //b->setAHeight(getAVLHeight(b));
95. 112. if (c->getAbsoluteAHeight() == 1)
96. {
97. if (b->getAHeight() == 0)
98. {
99. b->setAHeight(1);
100. }
101. else
102. {
103. b->setAHeight(0);
104. }
105. 123. a->setAHeight(-1);
106. c->setAHeight(0);
107. 126. }
108. else
109. {
110. 130. if (b->getAHeight() == 0)
111. {
112. b->setAHeight(1);
113. }
114. else
115. {
116. b->setAHeight(0);
117. }
118. a->setAHeight(0);
119. c->setAHeight(0);
120. 141. }
121. 143. 144. 145. 146. return c;
122. }
123. 这里旋转后调整平衡因子是关键部分。这是我自己总结的方法，经少量测试暂时没有出现问题。这个调整方法好像与大多数书本和网络程序的方法不一致。不清楚到底哪个是正确的。但是如果不使用这种直接赋值的方法，可以使用递归查找树高的方法保障万无一失的解决这个问题。这里使用的 右树高减左树高得平衡因子 的方法。

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

1. int getHeight(AVLNode* node)
2. {
3. if (node == NULL)
4. {
5. return 0;
6. }
7. else
8. {
9. int leftHeight = getHeight(node->getLeft());
10. int rightHeight = getHeight(node->getRight());
11. if (leftHeight > rightHeight)
12. {
13. return leftHeight+1;
14. }
15. else
16. {
17. return rightHeight+1;
18. }
19. }
20. }
21. 22. int getAVLHeight(AVLNode* node)
22. {
23. if (node == NULL)
24. {
25. return 0;
26. }
27. else
28. {
29. int leftHeight = getHeight(node->getLeft());
30. int rightHeight = getHeight(node->getRight());
31. return rightHeight - leftHeight;
32. }
33. }
34. 删除、插入操作有点复杂。

插入操作：

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

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

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

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

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

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

1. void insertNode(AVLNode* node)
2. {
3. AVLNode* subRoot = this ->head;
4. if (subRoot == NULL)
5. {
6. subRoot = node;
7. return ;
8. }
9. AVLNode* ppoRoot = NULL;
10. AVLNode* poRoot = NULL;
11. AVLNode* pRoot = NULL;
12. 13. 14. 15. poRoot = subRoot;
13. 17. while (subRoot != NULL)
14. {
15. pRoot = subRoot;
16. if (subRoot->getData() > node->getData())
17. {
18. 23. if (isPossibleNode(subRoot->getLeft(),node))
19. {
20. poRoot = subRoot->getLeft();
21. ppoRoot = subRoot;
22. }
23. subRoot = subRoot->getLeft();
24. 30. }
25. else if (subRoot->getData() < node->getData())
26. {
27. 34. if (isPossibleNode(subRoot->getRight(),node))
28. {
29. poRoot = subRoot->getRight();
30. ppoRoot = subRoot;
31. }
32. subRoot = subRoot->getRight();
33. }
34. else
35. {
36. throw “the same key” ;
37. }
38. }
39. 47. bool isChangeHeight = false ;
40. if (pRoot->getData() > node->getData())
41. {
42. 51. pRoot->setLeft(node);
43. if (pRoot->getRight() == NULL)
44. {
45. isChangeHeight = true ;
46. }
47. else
48. {
49. pRoot->setAHeight(pRoot->getAHeight()-1);
50. }
51. }
52. else if (pRoot->getData() < node->getData())
53. {
54. 64. pRoot->setRight(node);
55. if (pRoot->getLeft() == NULL)
56. {
57. isChangeHeight = true ;
58. }
59. else
60. {
61. pRoot->setAHeight(pRoot->getAHeight()+1);
62. }
63. }
64. 75. 76. if (poRoot != NULL && isChangeHeight)
65. {
66. // s->a update Height
67. subRoot = poRoot;
68. while (subRoot != node)
69. {
70. if (subRoot->getData() > node->getData())
71. {
72. subRoot->setAHeight(subRoot->getAHeight()-1);
73. 86. subRoot = subRoot->getLeft();
74. 88. }
75. else if (subRoot->getData() < node->getData())
76. {
77. subRoot->setAHeight(subRoot->getAHeight()+1);
78. 93. subRoot = subRoot->getRight();
79. 95. }
80. 97. }
81. 99. subRoot = poRoot;
82. AVLNode* a = poRoot;
83. AVLNode* b = NULL;
84. AVLNode* c = NULL;
85. AVLNode* tempRoot = NULL;
86. if (a->getAbsoluteAHeight() > 1)
87. {
88. if (subRoot->getData() > node->getData())
89. {
90. b = subRoot->getLeft();
91. if (a->getAHeight()* b->getAHeight() > 0)
92. {
93. //LLRotate
94. tempRoot = LLRotate(a,b);
95. 114. }
96. else
97. {
98. //LRRotate
99. c = b->getRight();
100. tempRoot =LRRotate(a,b,c);
101. }
102. 122. }
103. else if (subRoot->getData() < node->getData())
104. {
105. b = subRoot->getRight();
106. if (a->getAHeight()* b->getAHeight() > 0)
107. {
108. //RRRotate
109. tempRoot = RRRotate(a,b);
110. }
111. else
112. {
113. //RLRotate
114. c = b->getLeft();
115. tempRoot =RLRotate(a,b,c);
116. }
117. }
118. if (ppoRoot!=NULL)
119. {
120. if (ppoRoot->getData() > tempRoot->getData())
121. {
122. ppoRoot->setLeft(tempRoot);
123. }
124. else
125. {
126. ppoRoot->setRight(tempRoot);
127. }
128. }
129. else
130. {
131. this ->head = tempRoot;
132. }
133. }
134. 155. 156. }
135. 158. }

再看删除操作。

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

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

bool deleteNode(AVLNode* subRoot, AVLNode* 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方法将替代品删除。如果de
leteNode操作返回true，那么显然subRoot的平衡因子要加1.

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

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

B.不为0，return false。

下面是实际代码

1. bool deleteNode(AVLNode* subRoot, AVLNode* prev, T& node)
2. {
3. if (subRoot == NULL)
4. {
5. return false ;
6. }
7. bool isChangeHeight = 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. }
15. 16. }
16. else if (subRoot->getData() < node)
17. {
18. isChangeHeight = deleteNode(subRoot->getRight(),subRoot,node);
19. if (isChangeHeight)
20. {
21. subRoot->setAHeight(subRoot->getAHeight()-1);
22. }
23. 25. }
24. else
25. {
26. AVLNode* assignNode = NULL;
27. if (subRoot->getLeft() == NULL && subRoot->getRight() == NULL)
28. {
29. // no child
30. 33. isChangeHeight = true ;
31. deleteNode(subRoot,prev,assignNode);
32. return isChangeHeight;
33. }
34. else if (subRoot->getLeft() == NULL && subRoot->getRight() != NULL)
35. {
36. // no left child
37. isChangeHeight = true ;
38. assignNode = subRoot->getRight();
39. deleteNode(subRoot,prev,assignNode);
40. return isChangeHeight;
41. 45. }
42. else if (subRoot->getRight() == NULL && subRoot->getLeft() != NULL)
43. {
44. // no right chlid
45. isChangeHeight = true ;
46. assignNode = subRoot->getLeft();
47. deleteNode(subRoot,prev,assignNode);
48. return isChangeHeight;
49. }
50. else
51. {
52. // have both children
53. assignNode = getMaxNode(subRoot->getLeft());
54. T data = assignNode->getData();
55. bool isChange = deleteNode(subRoot->getLeft(),subRoot,data);
56. cout << "use " << data<< " replace " << subRoot->getData()<<endl;
57. subRoot->setData(data); // copy all data to subRoot
58. 63. if (isChange)
59. {
60. subRoot->setAHeight(subRoot->getAHeight()+1);
61. }
62. }
63. 69. if (subRoot->getAbsoluteAHeight() == 2)
64. {
65. AVLNode* a = subRoot;
66. AVLNode* b = NULL;
67. AVLNode* c = NULL;
68. AVLNode* tempRoot = NULL;
69. if (subRoot->getAHeight() == 2)
70. {
71. // move to left
72. b = subRoot->getRight();
73. switch (b->getAHeight())
74. {
75. case 1:
76. tempRoot = RRRotate(a,b);
77. isChangeHeight = true ;
78. break ;
79. case -1:
80. c = b->getLeft();
81. tempRoot = RLRotate(a,b,c);
82. isChangeHeight = true ;
83. break ;
84. case 0:
85. tempRoot = RRRotate(a,b);
86. isChangeHeight = false ;
87. break ;
88. }
89. 96. }
90. else if (subRoot->getAHeight() == -2)
91. {
92. // move to right
93. b = subRoot->getLeft();
94. switch (b->getAHeight())
95. {
96. case 1:
97. c = b->getRight();
98. tempRoot = LRRotate(a,b,c);
99. isChangeHeight = true ;
100. 108. break ;
101. case -1:
102. tempRoot = LLRotate(a,b);
103. isChangeHeight = true ;
104. break ;
105. case 0:
106. tempRoot = LLRotate(a,b);
107. isChangeHeight = false ;
108. break ;
109. }
110. 119. }
111. 121. if (prev == NULL)
112. {
113. this ->head = tempRoot;
114. }
115. else
116. {
117. if (prev->getData() > tempRoot->getData())
118. {
119. prev->setLeft(tempRoot);
120. }
121. else
122. {
123. prev->setRight(tempRoot);
124. }
125. }
126. }
127. 138. 139. 140. }
128. 142. return isChangeHeight;
129. 144. }

最后贴上AVLTree的完整类代码

1. #include “AVLNode.h”
2. 3. template< class T>
3. class AVLTree
4. {
5. private :
6. AVLNode* head;
7. 9. int getHeight(AVLNode* node)
8. {
9. if (node == NULL)
10. {
11. return 0;
12. }
13. else
14. {
15. int leftHeight = getHeight(node->getLeft());
16. int rightHeight = getHeight(node->getRight());
17. if (leftHeight > rightHeight)
18. {
19. return leftHeight+1;
20. }
21. else
22. {
23. return rightHeight+1;
24. }
25. }
26. }
27. 30. int getAVLHeight(AVLNode* node)
28. {
29. if (node == NULL)
30. {
31. return 0;
32. }
33. else
34. {
35. int leftHeight = getHeight(node->getLeft());
36. int rightHeight = getHeight(node->getRight());
37. return rightHeight - leftHeight;
38. }
39. }
40. 44. 45. void clearSubTree(AVLNode* node)
41. {
42. if (node != NULL)
43. {
44. clearSubTree(node->getLeft());
45. clearSubTree(node->getRight());
46. delete node;
47. }
48. }
49. 55. void printTree(AVLNode* subTree, int count)
50. {
51. if (subTree!=NULL)
52. {
53. 60. printTree(subTree->getRight(), count+1);
54. for ( int i = 0; i < count; i++)
55. {
56. cout << "   " ;
57. }
58. cout <getData()<<endl;
59. printTree(subTree->getLeft(),count+1);
60. }
61. }
62. 70. 71. void printInMidOrder(AVLNode* subTree)
63. {
64. if (subTree!=NULL)
65. {
66. printInMidOrder(subTree->getLeft());
67. 77. 78. cout <getData()<<endl;
68. printInMidOrder(subTree->getRight());
69. }
70. }
71. 83. bool isPossibleNode(AVLNode* node, AVLNode* comNode)
72. {
73. if (node != NULL && node->getAbsoluteAHeight() == 1)
74. {
75. return true ;
76. }
77. return false ;
78. }
79. 92. void insertNode(AVLNode* node)
80. {
81. AVLNode* subRoot = this ->head;
82. if (subRoot == NULL)
83. {
84. subRoot = node;
85. return ;
86. }
87. AVLNode* ppoRoot = NULL;
88. AVLNode* poRoot = NULL;
89. AVLNode* pRoot = NULL;
90. 104. 105. 106. poRoot = subRoot;
91. 108. while (subRoot != NULL)
92. {
93. pRoot = subRoot;
94. if (subRoot->getData() > node->getData())
95. {
96. 114. if (isPossibleNode(subRoot->getLeft(),node))
97. {
98. poRoot = subRoot->getLeft();
99. ppoRoot = subRoot;
100. }
101. subRoot = subRoot->getLeft();
102. 121. }
103. else if (subRoot->getData() < node->getData())
104. {
105. 125. if (isPossibleNode(subRoot->getRight(),node))
106. {
107. poRoot = subRoot->getRight();
108. ppoRoot = subRoot;
109. }
110. subRoot = subRoot->getRight();
111. }
112. else
113. {
114. throw “the same key” ;
115. }
116. }
117. 138. bool isChangeHeight = false ;
118. if (pRoot->getData() > node->getData())
119. {
120. 142. pRoot->setLeft(node);
121. if (pRoot->getRight() == NULL)
122. {
123. isChangeHeight = true ;
124. }
125. else
126. {
127. pRoot->setAHeight(pRoot->getAHeight()-1);
128. }
129. }
130. else if (pRoot->getData() < node->getData())
131. {
132. 155. pRoot->setRight(node);
133. if (pRoot->getLeft() == NULL)
134. {
135. isChangeHeight = true ;
136. }
137. else
138. {
139. pRoot->setAHeight(pRoot->getAHeight()+1);
140. }
141. }
142. 166. 167. if (poRoot != NULL && isChangeHeight)
143. {
144. // s->a update Height
145. subRoot = poRoot;
146. while (subRoot != node)
147. {
148. if (subRoot->getData() > node->getData())
149. {
150. subRoot->setAHeight(subRoot->getAHeight()-1);
151. 177. subRoot = subRoot->getLeft();
152. 179. }
153. else if (subRoot->getData() < node->getData())
154. {
155. subRoot->setAHeight(subRoot->getAHeight()+1);
156. 184. subRoot = subRoot->getRight();
157. 186. }
158. 188. }
159. 190. subRoot = poRoot;
160. AVLNode* a = poRoot;
161. AVLNode* b = NULL;
162. AVLNode* c = NULL;
163. AVLNode* tempRoot = NULL;
164. if (a->getAbsoluteAHeight() > 1)
165. {
166. if (subRoot->getData() > node->getData())
167. {
168. b = subRoot->getLeft();
169. if (a->getAHeight()* b->getAHeight() > 0)
170. {
171. //LLRotate
172. tempRoot = LLRotate(a,b);
173. 205. }
174. else
175. {
176. //LRRotate
177. c = b->getRight();
178. tempRoot =LRRotate(a,b,c);
179. }
180. 213. }
181. else if (subRoot->getData() < node->getData())
182. {
183. b = subRoot->getRight();
184. if (a->getAHeight()* b->getAHeight() > 0)
185. {
186. //RRRotate
187. tempRoot = RRRotate(a,b);
188. }
189. else
190. {
191. //RLRotate
192. c = b->getLeft();
193. tempRoot =RLRotate(a,b,c);
194. }
195. }
196. if (ppoRoot!=NULL)
197. {
198. if (ppoRoot->getData() > tempRoot->getData())
199. {
200. ppoRoot->setLeft(tempRoot);
201. }
202. else
203. {
204. ppoRoot->setRight(tempRoot);
205. }
206. }
207. else
208. {
209. this ->head = tempRoot;
210. }
211. }
212. 246. 247. }
213. 249. }
214. 251. 252. // return the subRoot
215. //        a                   b
216. //       /                  /   /
217. //      b        ->        c     a
218. //     /
219. //    c
220. AVLNode* LLRotate(AVLNode* a, AVLNode* b)
221. {
222. a->setLeft(b->getRight());
223. b->setRight(a);
224. 263. a->setAHeight(0);
225. b->setAHeight(0);
226. //a->setAHeight(getAVLHeight(a));
227. //b->setAHeight(getAVLHeight(b));
228. return b;
229. }
230. 270. // return the subRoot
231. //        a                      b
232. //          /                  /   /
233. //            b        ->     a     c
234. //              /
235. //                c
236. AVLNode* RRRotate(AVLNode* a, AVLNode* b)
237. {
238. a->setRight(b->getLeft());
239. b->setLeft(a);
240. 281. a->setAHeight(0);
241. b->setAHeight(0);
242. //a->setAHeight(getAVLHeight(a));
243. //b->setAHeight(getAVLHeight(b));
244. return b;
245. }
246. 288. 289. // return the subRoot
247. //        a                      c
248. //          /                  /   /
249. //            b        ->     a     b
250. //           /                 /
251. //          c                   d
252. //         /
253. //        d
254. AVLNode* RLRotate(AVLNode* a, AVLNode* b, AVLNode* c)
255. {
256. 300. b->setLeft(c->getRight());
257. c->setRight(b);
258. a->setRight(c->getLeft());
259. c->setLeft(a);
260. 305. 306. //a->setAHeight(getAVLHeight(a));
261. //c->setAHeight(getAVLHeight©);
262. //b->setAHeight(getAVLHeight(b));
263. 310. if (c->getAbsoluteAHeight() == 1)
264. {
265. if (b->getAHeight() == 0)
266. {
267. b->setAHeight(-1);
268. }
269. else
270. {
271. b->setAHeight(0);
272. }
273. a->setAHeight(1);
274. c->setAHeight(0);
275. 323. }
276. else
277. {
278. if (b->getAHeight() == 0)
279. {
280. b->setAHeight(-1);
281. }
282. else
283. {
284. b->setAHeight(0);
285. }
286. a->setAHeight(0);
287. c->setAHeight(0);
288. 337. }
289. 339. 340. return c;
290. }
291. 343. // return the subRoot
292. //        a                      c
293. //       /                     /   /
294. //      b              ->     b     a
295. //       /                         /
296. //        c                       d
297. //         /
298. //          d
299. AVLNode* LRRotate(AVLNode* a, AVLNode* b, AVLNode* c)
300. {
301. b->setRight(c->getLeft());
302. c->setLeft(b);
303. a->setLeft(c->getRight());
304. c->setRight(a);
305. 358. 359. //a->setAHeight(getAVLHeight(a));
306. //c->setAHeight(getAVLHeight©);
307. //b->setAHeight(getAVLHeight(b));
308. 363. if (c->getAbsoluteAHeight() == 1)
309. {
310. if (b->getAHeight() == 0)
311. {
312. b->setAHeight(1);
313. }
314. else
315. {
316. b->setAHeight(0);
317. }
318. 374. a->setAHeight(-1);
319. c->setAHeight(0);
320. 377. }
321. else
322. {
323. 381. if (b->getAHeight() == 0)
324. {
325. b->setAHeight(1);
326. }
327. else
328. {
329. b->setAHeight(0);
330. }
331. a->setAHeight(0);
332. c->setAHeight(0);
333. 392. }
334. 394. 395. 396. 397. return c;
335. }
336. 400. 401. AVLNode* getMaxNode(AVLNode* subRoot)
337. {
338. if (subRoot == NULL)
339. {
340. return NULL;
341. }
342. if (subRoot->getRight() == NULL)
343. {
344. return subRoot;
345. }
346. else
347. {
348. return getMaxNode(subRoot->getRight());
349. }
350. }
351. 417. void deleteNode(AVLNode* subRoot, AVLNode* prev,AVLNode* assignNode)
352. {
353. if (prev == NULL)
354. {
355. this ->head = assignNode;
356. 423. }
357. else
358. {
359. if (prev->getLeft() == subRoot)
360. {
361. prev->setLeft(assignNode);
362. 430. }
363. else if (prev->getRight() == subRoot)
364. {
365. prev->setRight(assignNode);
366. 435. }
367. }
368. 438. delete subRoot;
369. }
370. 441. bool deleteNode(AVLNode* subRoot, AVLNode* prev, T& node)
371. {
372. if (subRoot == NULL)
373. {
374. return false ;
375. }
376. bool isChangeHeight = false ;
377. if (subRoot->getData() > node)
378. {
379. isChangeHeight = deleteNode(subRoot->getLeft(),subRoot,node);
380. if (isChangeHeight)
381. {
382. subRoot->setAHeight(subRoot->getAHeight()+1);
383. }
384. 456. }
385. else if (subRoot->getData() < node)
386. {
387. isChangeHeight = deleteNode(subRoot->getRight(),subRoot,node);
388. if (isChangeHeight)
389. {
390. subRoot->setAHeight(subRoot->getAHeight()-1);
391. }
392. 465. }
393. else
394. {
395. AVLNode* assignNode = NULL;
396. if (subRoot->getLeft() == NULL && subRoot->getRight() == NULL)
397. {
398. // no child
399. 473. isChangeHeight = true ;
400. deleteNode(subRoot,prev,assignNode);
401. return isChangeHeight;
402. }
403. else if (subRoot->getLeft() == NULL && subRoot->getRight() != NULL)
404. {
405. // no left child
406. isChangeHeight = true ;
407. assignNode = subRoot->getRight();
408. deleteNode(subRoot,prev,assignNode);
409. return isChangeHeight;
410. 485. }
411. else if (subRoot->getRight() == NULL && subRoot->getLeft() != NULL)
412. {
413. // no right chlid
414. isChangeHeight = true ;
415. assignNode = subRoot->getLeft();
416. deleteNode(subRoot,prev,assignNode);
417. return isChangeHeight;
418. }
419. else
420. {
421. // have both children
422. assignNode = getMaxNode(subRoot->getLeft());
423. T data = assignNode->getData();
424. bool isChange = deleteNode(subRoot->getLeft(),subRoot,data);
425. cout << "use " << data<< " replace " << subRoot->getData()<<endl;
426. subRoot->setData(data); // copy all data to subRoot
427. 503. if (isChange)
428. {
429. subRoot->setAHeight(subRoot->getAHeight()+1);
430. }
431. }
432. 509. if (subRoot->getAbsoluteAHeight() == 2)
433. {
434. AVLNode* a = subRoot;
435. AVLNode* b = NULL;
436. AVLNode* c = NULL;
437. AVLNode* tempRoot = NULL;
438. if (subRoot->getAHeight() == 2)
439. {
440. // move to left
441. b = subRoot->getRight();
442. switch (b->getAHeight())
443. {
444. case 1:
445. tempRoot = RRRotate(a,b);
446. isChangeHeight = true ;
447. break ;
448. case -1:
449. c = b->getLeft();
450. tempRoot = RLRotate(a,b,c);
451. isChangeHeight = true ;
452. break ;
453. case 0:
454. tempRoot = RRRotate(a,b);
455. isChangeHeight = false ;
456. break ;
457. }
458. 536. }
459. else if (subRoot->getAHeight() == -2)
460. {
461. // move to right
462. b = subRoot->getLeft();
463. switch (b->getAHeight())
464. {
465. case 1:
466. c = b->getRight();
467. tempRoot = LRRotate(a,b,c);
468. isChangeHeight = true ;
469. 548. break ;
470. case -1:
471. tempRoot = LLRotate(a,b);
472. isChangeHeight = true ;
473. break ;
474. case 0:
475. tempRoot = LLRotate(a,b);
476. isChangeHeight = false ;
477. break ;
478. }
479. 559. }
480. 561. if (prev == NULL)
481. {
482. this ->head = tempRoot;
483. }
484. else
485. {
486. if (prev->getData() > tempRoot->getData())
487. {
488. prev->setLeft(tempRoot);
489. }
490. else
491. {
492. prev->setRight(tempRoot);
493. }
494. }
495. }
496. 578. 579. 580. }
497. 582. return isChangeHeight;
498. 584. }
499. 586. 587. 588. public :
500. AVLTree(T& data)
501. {
502. head = new AVLNode(data);
503. }
504. 594. AVLTree(AVLNode* head)
505. {
506. clearSubTree( this ->head);
507. this ->head = head;
508. }
509. 600. ~AVLTree()
510. {
511. clearSubTree(head);
512. }
513. 605. void printTree()
514. {
515. printTree( this ->head,0);
516. }
517. 610. void printInMidOrder()
518. {
519. printInMidOrder( this ->head);
520. }
521. 615. 616. void insertNode(T& data)
522. {
523. insertNode( new AVLNode(data));
524. 620. }
525. 622. void deleteNode(T& data)
526. {
527. deleteNode( this ->head,NULL,data);
528. }
529. /bool isUnbalancePoint(AVLNode node, AVLNode* compareNode)
530. {
531. 629. if(node->getAbsoluteAHeight() == 1)
532. {
533. 632. if(node->getAHeight == 1 && node->getData() < compareNode->getData() )
534. {
535. return true;
536. }
537. else if(node->getAHeight == -1 && node->getData() > compareNode->getData())
538. {
539. return true;
540. }
541. }
542. return false;
543. }*/
544. 644. 645. };