1 #include <iostream>
2 #include <list>
3 #include <utility>
4 #include <
string>
5 using namespace std;
6 7 static const string PRINT_SPACES =
" ";
8 9 template <typename Object>
10 class AVLTree
11 {
12 public:
13 AVLTree(){root=NULL;}
14 15 void insert(
const Object &x)
16 {insert(x,root);}
17 void remove(
const Object &x)
18 {remove(x,root);}
19 20 void print();
21 22 private:
23 struct AVLnode
24 {
25 Object data;
26 AVLnode *left;
27 AVLnode *right;
28 int height;
29 30 AVLnode(Object ob,AVLnode *l,AVLnode *r,
int h=
0):data(ob),left(l),right(r),height(h){}
31 };
32 33 AVLnode *root;
34 35 void insert(
const Object &x,AVLnode * &t);
36 37 void remove(
const Object &x,AVLnode *&t);
38 39 void leftSingleRotation(AVLnode * &t);
40 void rightSingleRotation(AVLnode * &t);
41 42 void leftDoubleRotation(AVLnode * &t);
43 void rightDoubleRotation(AVLnode * &t);
44 45 int height(AVLnode * &t)
46 {
47 //结点的高度,空结点的高度为-1
48 return t==NULL?-
1:t->height;
49 }
50 51 int max(
int a,
int b)
52 {
53 return a<b?b:a;
54 }
55 56 int powerOf2(
int x)
//求2的x次方(x大于等于0)
57 {
58 if(x==
0)
return 1;
59 int m=
1;
60 while(--x>=
0)
61 m*=
2;
62 return m;
63 }
64 65 AVLnode * max_node(AVLnode * t)
//max和min使用递归的话不能使用引用形参,不能返回引用
66 {
67 if(!t)
68 return NULL;
69 if(t->right)
70 return max_node(t->right);
71 else 72 return t;
73 }
74 75 AVLnode * min_node(AVLnode * t)
76 {
77 if(t)
//考虑一下t为空的情况,使其更全面,毕竟这个函数是可以加一个public版本的重载供用户使用
78 while(t->left)
79 t=t->left;
80 return t;
81 }
82 };
83 84 template <typename Object>
85 void AVLTree<Object>::insert(
const Object &x,AVLnode * &t)
86 {
87 if(!t)
88 t=
new AVLnode(x,NULL,NULL);
89 else if(x<t->data)
90 {
91 insert(x,t->left);
92 if(height(t->left)-height(t->right)==
2)
//在左子树插入结点后,不可能右子树比左子树高2
93 if(x<t->left->data)
94 leftSingleRotation(t);
//左单旋转
95 else 96 leftDoubleRotation(t);
//左双旋转
97 else//不需要调整就满足平衡条件的话,只需要重新计算其高度就好
98 t->height=max(height(t->left),height(t->right))+
1;
99 }
100 else if(x>t->data)
101 {
102 insert(x,t->right);
103 if(height(t->right)-height(t->left)==
2)
104 if(x>t->right->data)
105 rightSingleRotation(t);
//右单旋转
106 else107 rightDoubleRotation(t);
//右双旋转
108 else109 t->height=max(height(t->left),height(t->right))+
1;
110 }
111 else;
//不考虑重复的值
112 }
113 114 template <typename Object>
115 void AVLTree<Object>::leftSingleRotation(AVLnode * &t)
//左单旋转
116 {
117 AVLnode *s=t->left;
118 t->left=s->right;
119 s->right=t;
120 t->height=max(height(t->left),height(t->right))+
1;
//重新计算s和t的高度
121 s->height=max(height(s->left),t->height)+
1;
122 t=s;
123 }
124 125 template <typename Object>
126 void AVLTree<Object>::rightSingleRotation(AVLnode * &t)
127 {
128 AVLnode *s=t->right;
129 t->right=s->left;
130 s->left=t;
131 t->height=max(height(t->left),height(t->right))+
1;
132 s->height=max(t->height,height(s->right))+
1;
133 t=s;
134 }
135 136 template <typename Object>
137 void AVLTree<Object>::leftDoubleRotation(AVLnode * &t)
//左双旋转
138 {
139 AVLnode *p=t->left;
140 AVLnode *q=p->right;
141 t->left=q->right;
142 p->right=q->left;
143 q->left=p;
144 q->right=t;
145 t->height=max(height(t->left),height(t->right))+
1;
//重新计算3个结点的高度
146 p->height=max(height(p->left),height(p->right))+
1;
147 q->height=max(p->height,t->height)+
1;
148 t=q;
149 }
150 151 template <typename Object>
152 void AVLTree<Object>::rightDoubleRotation(AVLnode * &t)
153 {
154 AVLnode *p=t->right;
155 AVLnode *q=p->left;
156 t->right=q->left;
157 p->left=q->right;
158 q->right=p;
159 q->left=t;
160 t->height=max(height(t->left),height(t->right))+
1;
161 p->height=max(height(p->left),height(p->right))+
1;
162 q->height=max(t->height,p->height)+
1;
163 t=q;
164 }
165 166 template <typename Object>
167 void AVLTree<Object>::remove(
const Object &x,AVLnode *&t)
168 {
169 if(!t)
return;
//没有找到要删除的值,do nothing
170 if(x<t->data)
171 {
172 remove(x,t->left);
173 if(height(t->right)-height(t->left)==
2)
174 {
175 //右子树比左子树高2,那么在删除操作之前右子树比左子树高1,
176 //也就是说t的右子树必然不为空,甚至必然有非空子树(高度至少为1).
177 AVLnode *s=t->right;
178 if(height(s->left)>height(s->right))
179 rightDoubleRotation(t);
//右双旋转
180 else181 rightSingleRotation(t);
//右单旋转
182 }
183 else184 //不需要调整就满足平衡条件的话,只需要重新计算其高度就好
185 t->height=max(height(t->left),height(t->right))+
1;
186 }
187 else if(x>t->data)
188 {
189 remove(x,t->right);
190 if(height(t->left)-height(t->right)==
2)
191 {
192 AVLnode *s=t->left;
193 if(height(s->right)>height(s->left))
194 leftDoubleRotation(t);
//左双旋转
195 else196 leftSingleRotation(t);
//左单旋转
197 }
198 else199 t->height=max(height(t->left),height(t->right))+
1;
200 }
201 else202 {
203 if(t->left&&t->right)
204 //t的左右子树都非空,把remove操作转移到只有一个非空子树的结点或者叶子结点上去
205 {
206 if(height(t->left)>height(t->right))
207 //把remove操作往更高的那颗子树上转移
208 {
209 //左子树中的最大值
210 t->data=max_node(t->left)->data;
211 remove(t->data,t->left);
212 }
213 else214 {
215 //右子树中的最小值
216 t->data=min_node(t->right)->data;
217 remove(t->data,t->right);
218 }
219 }
220 else221 {
222 AVLnode *oldnode=t;
223 t=t->left?t->left:t->right;
224 delete oldnode;
225 }
226 }
227 }
228 229 //使用队列层次遍历打印树
230 template <typename Object>
231 void AVLTree<Object>::print()
232 {
233 if(!root)
return;
234 list<pair<AVLnode *,
int> > lis;
//int是标志位,0表示正常值,-1表示此处没有值,应打印空格
235 lis.push_back(make_pair(root,
0));
236 AVLnode *em=
new AVLnode(
0,NULL,NULL);
//一个空的点
237 int count=
1,j=
0;
//count表示当前行的最大结点数,j表示当前行已打印的结点数(空结点也计数)
238 int hg=root->height;
//当前行的高度,计算空格时使用
239 240 while(hg>=
0)
//当hg<0时说明最后一行(树叶)已经打印完毕
241 {
242 while(j++!=count)
243 {
244 for(
int i=
1;i<powerOf2(hg);i++)
245 cout<<PRINT_SPACES;
//打印前一部分空格
246 if(lis.front().second==
0)
247 cout<<lis.front().first->data;
248 else249 cout<<PRINT_SPACES;
//int位为-1,则打印空格以对齐
250 if(lis.front().first->left)
//左子树入队
251 lis.push_back(make_pair(lis.front().first->left,
0));
252 else253 lis.push_back(make_pair(em,-
1));
254 if(lis.front().first->right)
//右子树入队
255 lis.push_back(make_pair(lis.front().first->right,
0));
256 else257 lis.push_back(make_pair(em,-
1));
258 for(
int i=
0;i<powerOf2(hg);i++)
259 cout<<PRINT_SPACES;
//打印后一部分空格
260 lis.pop_front();
261 }
262 j=
0;
263 count*=
2;
//下一行的最大节点数是上一行的两倍
264 --hg;
//高度减1
265 cout<<endl;
//换行
266 }
267 delete em;
268 lis.clear();
269 }