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

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

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

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. }
1. int getAVLHeight(AVLNode* node)
21. {
22. if (node == NULL)
23. {
24. return 0;
25. }
26. else
27. {
28. int leftHeight = getHeight(node->getLeft());
29. int rightHeight = getHeight(node->getRight());
30. return rightHeight - leftHeight;
31. }
32. }
33. 删除、插入操作有点复杂。

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

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

3.插入后查看是否增长子树树高，如果增长树高，再查看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;
1. poRoot = subRoot;
1. while (subRoot != NULL)
12. {
13. pRoot = subRoot;
14. if (subRoot->getData() > node->getData())
15. {
1. if (isPossibleNode(subRoot->getLeft(),node))
16. {
17. poRoot = subRoot->getLeft();
18. ppoRoot = subRoot;
19. }
20. subRoot = subRoot->getLeft();
1. }
21. else if (subRoot->getData() < node->getData())
22. {
1. if (isPossibleNode(subRoot->getRight(),node))
23. {
24. poRoot = subRoot->getRight();
25. ppoRoot = subRoot;
26. }
27. subRoot = subRoot->getRight();
28. }
29. else
30. {
31. throw “the same key” ;
32. }
33. }
1. bool isChangeHeight = false ;
34. if (pRoot->getData() > node->getData())
35. {
1. pRoot->setLeft(node);
36. if (pRoot->getRight() == NULL)
37. {
38. isChangeHeight = true ;
39. }
40. else
41. {
42. pRoot->setAHeight(pRoot->getAHeight()-1);
43. }
44. }
45. else if (pRoot->getData() < node->getData())
46. {
1. pRoot->setRight(node);
47. if (pRoot->getLeft() == NULL)
48. {
49. isChangeHeight = true ;
50. }
51. else
52. {
53. pRoot->setAHeight(pRoot->getAHeight()+1);
54. }
55. }
1. if (poRoot != NULL && isChangeHeight)
56. {
57. // s->a update Height
58. subRoot = poRoot;
59. while (subRoot != node)
60. {
61. if (subRoot->getData() > node->getData())
62. {
63. subRoot->setAHeight(subRoot->getAHeight()-1);
1. subRoot = subRoot->getLeft();
1. }
64. else if (subRoot->getData() < node->getData())
65. {
66. subRoot->setAHeight(subRoot->getAHeight()+1);
1. subRoot = subRoot->getRight();
1. }
1. }
1. subRoot = poRoot;
67. AVLNode* a = poRoot;
68. AVLNode* b = NULL;
69. AVLNode* c = NULL;
70. AVLNode* tempRoot = NULL;
71. if (a->getAbsoluteAHeight() > 1)
72. {
73. if (subRoot->getData() > node->getData())
74. {
75. b = subRoot->getLeft();
76. if (a->getAHeight()* b->getAHeight() > 0)
77. {
78. //LLRotate
79. tempRoot = LLRotate(a,b);
1. }
80. else
81. {
82. //LRRotate
83. c = b->getRight();
84. tempRoot =LRRotate(a,b,c);
85. }
1. }
86. else if (subRoot->getData() < node->getData())
87. {
88. b = subRoot->getRight();
89. if (a->getAHeight()* b->getAHeight() > 0)
90. {
91. //RRRotate
92. tempRoot = RRRotate(a,b);
93. }
94. else
95. {
96. //RLRotate
97. c = b->getLeft();
98. tempRoot =RLRotate(a,b,c);
99. }
100. }
101. if (ppoRoot!=NULL)
102. {
103. if (ppoRoot->getData() > tempRoot->getData())
104. {
105. ppoRoot->setLeft(tempRoot);
106. }
107. else
108. {
109. ppoRoot->setRight(tempRoot);
110. }
111. }
112. else
113. {
115. }
116. }
1. }
1. }

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

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只有一个孩子或者没有孩子，那么删除时树高一定会改变。另外做一个简单的删除操作即可。该左孩子代替此节点还是右孩子代替它，如何代替其实

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

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