AVL树

  1 #include<iostream>
  2 #include<stack>
  3 using namespace std;
  4 
  5 template<class T>
  6 class avlTree
  7 {
  8     struct avlNode
  9     {
 10         T data;
 11         avlNode *left;
 12         avlNode *right;
 13         int height;
 14 
 15         avlNode(const T &element,avlNode *lt,avlNode *rt,int h=0)
 16         :data(element),left(lt),right(rt),height(h)
 17         {}
 18     };
 19 
 20     avlNode *root;
 21 
 22 private:
 23     void insert(const T &x,avlNode *&t);
 24     bool remove(const T &x,avlNode *&t);
 25     int heightNode(avlNode *&t)
 26     {
 27         //return t==NULL? -1:t->height;
 28         if(t==NULL)
 29             return 0;
 30         else
 31         {
 32             int lh=heightNode(t->left);
 33             int rh=heightNode(t->right);
 34             return 1+(lh>rh ? lh:rh);
 35         }
 36     }
 37     void LL(avlNode *&t);
 38     void LR(avlNode *&t);
 39     void RL(avlNode *&t);
 40     void RR(avlNode *&t);
 41     void makeEmpty(avlNode *&t);
 42     void preOrder(avlNode *&t);
 43     void midOrder(avlNode *&t);
 44     int max(int a,int b)
 45     {
 46         return a>b ? a:b;
 47     }
 48 public:
 49     avlTree(avlNode *t=NULL)
 50     {
 51         root=t;
 52     }
 53     ~avlTree()
 54     {
 55         makeEmpty(root);
 56     }
 57     void insert(const T &x)
 58     {
 59         insert(x,root);
 60     }
 61     void remove(const T &x)
 62     {
 63         remove(x,root);
 64     }
 65     void preOrder()
 66     {
 67         preOrder(root);
 68     }
 69     void midOrder()
 70     {
 71         midOrder(root);
 72     }
 73 };
 74 
 75 //单旋转：左子树比右子树高，插入发生在左儿子左子树
 76 template<class T>
 77 void avlTree<T>::LL(avlNode*&t)
 78 {
 79     avlNode *p=t->left;
 80 
 81     t->left=p->right;
 82     p->right=t;
 83 
 84     t->height=max(heightNode(t->left),heightNode(t->right))+1;
 85     p->height=max(heightNode(p->left),t->height)+1;
 86 
 87     t=p;
 88 }
 89 
 90 template<class T>
 91 void avlTree<T>::RR(avlNode *&t)
 92 {
 93     avlNode *p=t->right;
 94 
 95     t->right=p->left;
 96     p->left=t;
 97 
 98     t->height=max(heightNode(t->left),heightNode(t->right))+1;
 99     p->height=max(heightNode(p->right),t->height)+1;
100 
101     t=p;
102 }
103 
104 //双旋转：左子树比右子树高，插入发生在左儿子右子树
105 template<class T>
106 void avlTree<T>::LR(avlNode *&t)
107 {
108     RR(t->left);
109     LL(t);
110 }
111 
112 template<class T>
113 void avlTree<T>::RL(avlNode *&t)
114 {
115     LL(t->right);
116     RR(t);
117 }
118 
119 template<class T>
120 void avlTree<T>::insert(const T &x,avlNode *&t)
121 {
122     if(t==NULL)
123         t=new avlNode(x,NULL,NULL);
124     //不同插入方式对应不同旋转形式
125     else if(x<t->data)
126     {
127         insert(x,t->left);
128         if(heightNode(t->left)-heightNode(t->right)==2)
129         {
130             if(x<t->left->data)
131                 LL(t);
132             else
133                 LR(t);
134         }
135     }
136     else if(x>t->data)
137     {
138         insert(x,t->right);
139         if(heightNode(t->right)-heightNode(t->left)==2)
140         {
141             if(x>t->right->data)
142                 RR(t);
143             else
144                 RL(t);
145         }
146     }
147 
148     t->height=max(heightNode(t->left),heightNode(t->right))+1;
149 }
150 
151 template<class T>
152 bool avlTree<T>::remove(const T &x,avlNode *&t)
153 {
154     //是否需要停止调整
155     bool stop=false;
156     //1：删除在左子树上  2：删除在右子树上
157     int subTree;
158 
159     if(t==NULL)
160         return true;
161     if(x<t->data)
162     {
163         stop=remove(x,t->left);
164         subTree=1;
165     }
166     else if(x>t->data)
167     {
168         stop=remove(x,t->right);
169         subTree=2;
170     }
171     else if(t->left!=NULL&&t->right!=NULL)
172     {
173         //右子树最小节点为替代结点
174         avlNode *tmp=t->right;
175         while(tmp->left!=NULL)
176             tmp=tmp->left;
177         t->data=tmp->data;
178         stop=remove(t->data,t->right);
179         subTree=2;
180     }
181     else
182     {
183         avlNode *oldNode=t;
184         t=(t->left==NULL) ? t->right:t->left;
185         delete oldNode;
186         return false;
187     }
188 
189     if(stop)
190         return true;
191 
192     //删除前t平衡因子
193     int bf;
194 
195     switch(subTree)
196     {
197         case 1:
198         {
199             bf=heightNode(t->left)-heightNode(t->right)+1;
200             //删除前结点平衡因子为0，不影响父节点平衡因子，不需调整
201             if(bf==0)
202                 return true;
203             //从较高子树删除一个结点，影响父节点平衡因子，需要调整
204             else if(bf==1)
205                 return false;
206             //从较矮子树删除一个结点，需调整
207             //根据较高子树根节点平衡因子分情况
208             else if(bf==-1)
209             {
210                 int bfr=heightNode(t->right->left)-heightNode(t->right->right);
211                 switch(bfr)
212                 {
213                     case 0:
214                     {
215                         RR(t);
216                         return true;
217                     }
218                     case -1:
219                     {
220                         RR(t);
221                         return false;
222                     }
223                     default:
224                     {
225                         RL(t);
226                         return false;
227                     }
228                 }
229             }
230             break;
231         }
232         case 2:
233         {
234             bf=heightNode(t->left)-heightNode(t->right)-1;
235             if(bf==0)
236                 return true;
237             else if(bf==-1)
238                 return false;
239             else if(bf==1)
240             {
241                 int bfl=heightNode(t->left->left)-heightNode(t->left->right);
242                 switch(bfl)
243                 {
244                     case 0:
245                     {
246                         LL(t);
247                         return true;
248                     }
249                     case 1:
250                     {
251                         LL(t);
252                         return false;
253                     }
254                     case -1:
255                     {
256                         LR(t);
257                         return false;
258                     }
259                 }
260             }
261         }
262     }
263 }
264 
265 template<class T>
266 void avlTree<T>::makeEmpty(avlNode *&t)
267 {
268     if(t->left!=NULL)
269         makeEmpty(t->left);
270     if(t->right!=NULL)
271         makeEmpty(t->right);
272     delete t;
273 }
274 
275 template<class T>
276 void avlTree<T>::preOrder(avlNode *&t)
277 {
278     stack<avlNode *>s;
279 
280     avlNode *current;
281     s.push(t);
282 
283     while(!s.empty())
284     {
285         current=s.top();
286         cout<<current->data<<‘:‘<<heightNode(current->left)-heightNode(current->right)<<ends;
287         s.pop();
288         if(current->right!=NULL)
289             s.push(current->right);
290         if(current->left!=NULL)
291             s.push(current->left);
292     }
293 }
294 
295 template<class T>
296 void avlTree<T>::midOrder(avlNode *&t)
297 {
298     if(t)
299     {
300         midOrder(t->left);
301         cout<<t->data<<‘:‘<<heightNode(t->left)-heightNode(t->right)<<ends;
302         midOrder(t->right);
303     }
304 }
305 
306 int main()
307 {
308     avlTree<int>tree;
309 
310     int a[]={10,8,6,21,7,56,43,22,98,2};
311     //int a[3]={2,1,3};
312     for(int i=0;i<9;++i)
313         tree.insert(a[i]);
314 
315     cout<<"the preOrder traversal of the tree(with balance factor):"<<endl;
316     tree.preOrder();
317     cout<<endl;
318     cout<<"the midOrder traversal of the tree(with balance factor):"<<endl;
319     tree.midOrder();
320     cout<<endl;
321 
322     tree.remove(8);
323     cout<<endl;
324 
325     cout<<"the preOrder traversal of the tree(with balance factor) after remove 8:"<<endl;
326     tree.preOrder();
327     cout<<endl;
328     cout<<"the midOrder traversal of the tree(with balance factor) after remove 8:"<<endl;
329     tree.midOrder();
330 
331     return 0;
332 }