1 #pragma once
2
3 #include<stack>
4
5 template<
class Type>
6 class AVLTree;
7
8 template<
class Type>
9 class AVLNode
10 {
11 friend
class AVLTree<Type>
;
12 public:
13 AVLNode() : data(Type()),leftChild(NULL),rightChild(NULL),bf(
0)
14 {}
15 AVLNode(Type d, AVLNode<Type>*left=NULL,AVLNode<Type>*right=
NULL)
16 : data(d),leftChild(left),rightChild(right),bf(
0)
17 {}
18 ~
AVLNode()
19 {}
20 public:
21 void SetData(Type d);
22 Type& GetData()
const;
23 private:
24 Type data;
25 AVLNode *
leftChild;
26 AVLNode *
rightChild;
27 int bf;
28 };
29
30 template<
class Type>
31 class AVLTree
32 {
33 public:
34 AVLTree() : root(NULL)
35 {}
36 public:
37 void Insert(
const Type &
x)
38 {
39 Insert(root, x);
40 }
41 bool Remove(
const Type &
key)
42 {
43 return Remove(root, key);
44 }
45 private:
46 bool Remove(AVLNode<Type> *&t,
const Type &
key)
47 {
48 //1
49 if(t ==
NULL)
50 return false;
51 AVLNode<Type> *p =
t;
52 AVLNode<Type> *
q;
53 AVLNode<Type> *pr =
NULL;
54 stack<AVLNode<Type> *>
st;
55 while(p !=
NULL)
56 {
57 if(p->data ==
key)
58 break;
59
60 pr =
p;
61 st.push(pr);
62
63 if(key < p->
data)
64 p = p->
leftChild;
65 else
66 p = p->
rightChild;
67 }
68
69 if(p ==
NULL)
70 return false;
71 //
72 if(p->leftChild!=NULL && p->rightChild!=
NULL)
73 {
74 pr =
p;
75 st.push(pr);
76
77 q = p->
leftChild;
78 while(q->rightChild !=
NULL)
79 {
80 pr =
q;
81 q = q->
rightChild;
82 }
83 p->data = q->
data;
84 p =
q;
85 }
86
87 //
88 if(p->leftChild !=
NULL)
89 q = p->
leftChild;
90 else
91 q = p->
rightChild;
92
93 if(pr ==
NULL)
94 t =
q;
95 else
96 {
97 if(pr->leftChild ==
p)
98 pr->leftChild =
q;
99 else
100 pr->rightChild =
q;
101
102 ///
103 while(!
st.empty())
104 {
105 pr =
st.top();
106 st.pop();
107
108 if(pr->leftChild ==
q)
109 pr->bf++
;
110 else
111 pr->bf--
;
112
113 if(pr->bf==
1 || pr->bf==-
1)
114 break;
115 else if(pr->bf ==
0)
116 q =
pr;
117 else
118 {
119 if(pr->bf >
0)
120 q = pr->
rightChild;
121 else
122 q = pr->
leftChild;
123
124 if(q->bf ==
0)
// 单旋转
125 {
126 if(pr->bf >
0)
127 {
128 //RotateL(pr);
129 //bf ????
130 }
131 else
132 {
133 RotateR(pr);
134 //pr->bf = ???
135 //pr->rightChild->bf = ?????
136 }
137 }
138 else if(q->bf >
0)
139 {
140 if(pr->bf >
0)
// \
141 {
142 RotateL(pr);
143 }
144 else // <
145 {
146 RotateLR(pr);
147 //cout<<"RotateLR"<<endl;
148 }
149 }
150 else
151 {
152 if(pr->bf <
0)
// /
153 {
154 RotateR(pr);
155 }
156 else // >
157 {
158 RotateRL(pr);
159 }
160 }
161
162 break;
163 }
164 }
165
166 //
167 AVLNode<Type> *ppr =
st.top();
168 if(ppr->data > pr->
data )
169 ppr->leftChild =
pr;
170 else
171 ppr->rightChild =
pr;
172
173 }
174 delete p;
175 return true;
176 }
177 void Insert(AVLNode<Type> *&rt,
const Type &
x)
178 {
179 AVLNode<Type> *pr =
NULL;
180 AVLNode<Type>*t =
rt;
181 stack<AVLNode<Type> *>
St;
182 while(t !=
NULL)
183 {
184 if(x == t->
data)
185 return;
186
187 pr =
t;
188 St.push(pr);
189
190 if(x < t->
data)
191 t = t->
leftChild;
192 else if(x > t->
data)
193 t = t->
rightChild;
194 }
195 t =
new AVLNode<Type>
(x);
196 if(rt ==
NULL)
197 {
198 rt =
t;
199 return;
200 }
201
202 if(x < pr->
data)
203 pr->leftChild =
t;
204 else
205 pr->rightChild =
t;
206
207 while(!
St.empty())
208 {
209 pr =
St.top();
210 St.pop();
211
212 if(pr->leftChild ==
t)
213 pr->bf--
;
214 else
215 pr->bf++
;
216
217 if(pr->bf ==
0)
218 break;
219 else if(pr->bf==
1 || pr->bf==-
1)
220 t =
pr;
221 else
222 {
223 //调整
224 if(pr->bf <
0)
225 {
226 if(t->bf <
0)
// /
227 {
228 RotateR(pr);
229 }
230 else // <
231 {
232 RotateLR(pr);
233 }
234 }
235 else
236 {
237 if(t->bf >
0)
// \
238 {
239 RotateL(pr);
240 }
241 else // >
242 {
243 RotateRL(pr);
244 }
245 }
246 break;
247 }
248 }
249 if(St.empty())
250 rt =
pr;
251 else
252 {
253 AVLNode<Type> *s =
St.top();
254 if(pr->data < s->
data)
255 s->leftChild =
pr;
256 else
257 s->rightChild =
pr;
258 }
259 }
260 protected:
261 AVLNode<Type>* RotateL(AVLNode<Type> *&
ptr)
262 {
263 AVLNode<Type> *subL =
ptr;
264 ptr = subL->
rightChild;
265 subL->rightChild = ptr->
leftChild;
266 ptr->leftChild =
subL;
267 ptr->bf = subL->bf =
0;
268 return ptr;
269 }
270 AVLNode<Type>* RotateR(AVLNode<Type> *&
ptr)
271 {
272 AVLNode<Type> *subR =
ptr;
273 ptr = subR->
leftChild;
274 subR->leftChild = ptr->
rightChild;
275 ptr->rightChild =
subR;
276 ptr->bf = subR->bf =
0;
277 return ptr;
278 }
279 AVLNode<Type>* RotateLR(AVLNode<Type> *&
ptr)
280 {
281 AVLNode<Type> *subR =
ptr;
282 AVLNode<Type> *subL = ptr->
leftChild;
283 ptr = subL->
rightChild;
284
285 subL->rightChild = ptr->
leftChild;
286 ptr->leftChild =
subL;
287 //bf
288 if(ptr->bf <=
0)
289 subL->bf =
0;
290 else
291 subL->bf = -
1;
292
293 subR->leftChild = ptr->
rightChild;
294 ptr->rightChild =
subR;
295 //bf
296 if(ptr->bf >=
0)
297 subR->bf =
0;
298 else
299 subR->bf =
1;
300
301 ptr->bf =
0;
302 return ptr;
303 }
304 AVLNode<Type>* RotateRL(AVLNode<Type> *&
ptr)
305 {
306 AVLNode<Type> *subL =
ptr;
307 AVLNode<Type> *subR = ptr->
rightChild;
308 ptr = subR->
leftChild;
309 subR->leftChild = ptr->
rightChild;
310 ptr->rightChild =
subR;
311 //bf
312 if(ptr->bf >=
0)
313 subR->bf =
0;
314 else
315 subR->bf =
1;
316
317 subL->rightChild = ptr->
leftChild;
318 ptr->leftChild =
subL;
319 //bf
320 if(ptr->bf <=
0)
321 subL->bf =
0;
322 else
323 subL->bf = -
1;
324
325 ptr->bf =
0;
326 return ptr;
327 }
328 private:
329 AVLNode<Type> *
root;
330 };
转载于:https://www.cnblogs.com/fmonlyg/p/7152688.html
相关资源：JAVA上百实例源码以及开源项目
