AVL树C++实现

  1 inline int max(int x, int y){ return x>y?x:y; }
  2 
  3 template<typename Element>
  4 class AVLTree
  5 {
  6     public:
  7         AVLTree():root(NULL) {}
  8         AVLTree(const AVLTree &avl):root(NULL) { operator=(avl); }
  9         virtual ~AVLTree() { clear(root); }
 10 
 11         void clear() { clear(root); }
 12         bool isEmpty() const
 13         { return root==NULL; }
 14         void insert(const Element& e)
 15         { insert(root, e); }
 16         void remove(const Element& e)
 17         { remove(root, e); }
 18         bool contains(const Element& e) const
 19         { return contains(root, e); }
 20         const Element& findMin() const
 21         { return findMin(root); }
 22         const Element& findMax() const
 23         { return findMax(root); }
 24 
 25         const AVLTree& operator=(const AVLTree &avl)
 26         {
 27             if(this!=&avl)
 28             {
 29                 clear();
 30                 root = clone(avl.root);
 31             }
 32             return *this;
 33         }
 34 
 35     private:
 36         struct AVLNode
 37         {
 38             Element element;
 39             int height;
 40             AVLNode *left;
 41             AVLNode *right;
 42             AVLNode(const Element &e, AVLNode *lt, AVLNode *rt, int h=0):
 43                 element(e), left(lt), right(rt), height(h) {}
 44         };
 45         AVLNode *root;
 46 
 47         AVLNode* clone(AVLNode *t)
 48         {
 49             if(t!=NULL)
 50             {
 51                 return new AVLNode(t->element, clone(t->left), clone(t->right), t->height);
 52             }
 53             return NULL;
 54         }
 55         void clear(AVLNode * &t)
 56         {
 57             if(t!=NULL)
 58             {
 59                 clear(t->left);
 60                 clear(t->right);
 61                 delete t;
 62             }
 63             t = NULL;
 64         }
 65         int height(AVLNode *t) const
 66         { return t==NULL?-1:t->height; }
 67         void insert(AVLNode* &t, const Element& e)
 68         {
 69             if(t==NULL)
 70             {
 71                 t = new AVLNode(e, NULL, NULL);
 72             }
 73             else if(e<t->element)
 74             {
 75                 insert(t->left, e);
 76                 if(height(t->left)-height(t->right)==2)
 77                 {
 78                     if(e<t->left->element)
 79                     {
 80                         rotateLchildLtree(t);
 81                     }
 82                     else
 83                     {
 84                         doubleRotateLchildRtree(t);
 85                     }
 86                 }
 87             }
 88             else if(e>t->element)
 89             {
 90                 insert(t->right, e);
 91                 if(height(t->right)-height(t->left)==2)
 92                 {
 93                     if(e>t->right->element)
 94                     {
 95                         rotateRchildRtree(t);
 96                     }
 97                     else
 98                     {
 99                         doubleRotateRchildLtree(t);
100                     }
101                 }
102             }
103             else
104             {
105             }
106             t->height = max(height(t->left), height(t->right))+1;
107         }
108         void remove(AVLNode* &t, const Element& e)
109         {
110             if(t!=NULL)
111             {
112                 if(e<t->element)
113                 {
114                     remove(t->left, e);
115                 }
116                 else if(e>t->element)
117                 {
118                     remove(t->right, e);
119                 }
120                 else if(t->left!=NULL&&t->right!=NULL)
121                 {
122                     t->element = findMin(t->right);
123                     remove(t->right, t->element);
124                 }
125                 else
126                 {
127                     AVLNode *tmp = t;
128                     t = t->left!=NULL?t->left:t->right;
129                     delete tmp;
130                 }
131                 if(t!=NULL)
132                 {
133                     t->height = max(height(t->left), height(t->right))+1;
134                     if(height(t->left)-height(t->right)==2)
135                     {
136                         if(height(t->left->left)>height(t->left->right))
137                         {
138                             rotateLchildLtree(t);
139                         }
140                         else
141                         {
142                             doubleRotateLchildRtree(t);
143                         }
144                     }
145                     else if(height(t->right)-height(t->left)==2)
146                     {
147                         if(height(t->right->right)>height(t->right->left))
148                         {
149                             rotateRchildRtree(t);
150                         }
151                         else
152                         {
153                             doubleRotateRchildLtree(t);
154                         }
155                     }
156                     else
157                     {
158                     }
159                 }
160             }
161         }
162         void rotateLchildLtree(AVLNode * &k2)
163         {
164             AVLNode *k1 = k2->left;
165             k2->left = k1->right;
166             k1->right = k2;
167             k2 = k1;
168         }
169         void rotateRchildRtree(AVLNode * &k2)
170         {
171             AVLNode *k1 = k2->right;
172             k2->right = k1->left;
173             k1->left = k2;
174             k2 = k1;
175         }
176         void doubleRotateLchildRtree(AVLNode * &k3)
177         {
178             rotateRchildRtree(k3->left);
179             rotateLchildLtree(k3);
180         }
181         void doubleRotateRchildLtree(AVLNode * &k3)
182         {
183             rotateLchildLtree(k3->right);
184             rotateRchildRtree(k3);
185         }
186         bool contains(AVLNode *t, const Element& e) const
187         {
188             if(t!=NULL)
189             {
190                 if(e<t->element)
191                 {
192                     return contains(t->left, e);
193                 }
194                 else if(e>t->element)
195                 {
196                     return contains(t->right, e);
197                 }
198                 else
199                 {
200                     return true;
201                 }
202             }
203             else
204             {
205                 return false;
206             }
207         }
208         const Element& findMin(AVLNode *t) const
209         {
210             return t->left!=NULL?findMin(t->left):t->element;
211         }
212         const Element& findMax(AVLNode *t) const
213         {
214             return t->right!=NULL?findMax(t->right):t->element;
215         }
216 };