【C++】C++模板实现的AVL树

0x55AA

1 AVL树的定义
AVL树是一种自平衡二叉排序树，它的特点是任何一个节点的左子树高度和右子树的高度差在-1,0,1三者之间。AVL树的任何一个子树都是AVL树。
2 AVL树的实现
AVL树本质是一种二叉排序树，所以二叉排序树的任何性质AVL树都具有，但是AVL树稍微复杂的地方就是AVL树必须满足平衡条件，具体跟BST不同的地方主要体现在插入，删除操作。
插入操作：当插入之后可能会出现不平衡，所以这时候要通过旋转树来实现平衡。旋转有四种类型，左左，左右，右左，右右。其中左左旋转和右右旋转是镜像的，左右旋转和右左旋转是镜像的，所以实质上就是两种类型的旋转。针对左左旋转，只需要旋转一次即可，针对左右旋转，需要执行两次旋转。见下图：

这里采用递归法实现插入和删除操作。使用递归方便的一点是如果函数的参数是引用类型的，当传入一个p->left的时候，我们在当前函数的下层递归的时候，对p进行的赋值操作其实就是对上层递归中的p->left进行的操作，所以这样就不需要传递父指针了。
3 实现代码
AVLTree.h

1. //AVLTree.h
   
2. #ifndef DDXX_AVLTREE_H
   
3. #define DDXX_AVLTREE_H
   
4. #include <iostream>
   
5. #include <queue>
   
6. using namespace std;
   
7. template<typename Type>
   
8. class AVLTree
   
9. {
   
10.         struct Node
    
11.         {
    
12.                 Type e;
    
13.                 Node* left;
    
14.                 Node* right;
    
15.                 int h;
    
16.                 Node(Type _e):e(_e),left(NULL),right(NULL),h(0){}
    
17.                 Node(Type _e,Node* _left,Node* _right,int _h):e(e),left(_left),right(_right),h(_h){}
    
18.         };
    
19. public:
    
20.         AVLTree();
    
21.         AVLTree(Type arr[],int nLength);
    
22.         /*AVLTree(const AVLTree& right);
    
23.         AVLTree& operator=(const AVLTree& right);*/
    
24.         ~AVLTree();
    
25. public:
    
26.         bool        insert(Type e,Node* &p);
    
27.         void        erase(Type e,Node* &p);
    
28.         Node*&        find(Type e)const;
    
29.         void        traverse(Node* p)const;
    
30.         void        traverseByLevel(Node* p)const;
    
31.         int                getLength(){return mLength;}
    
32.         Node*&        getParent(Node* p);
    
33.         Node*&        getRoot(){return mRoot;} //notice the return type
    
34.         bool        empty(){return mRoot==NULL;};
    
35.         void        clear();
    
36.         void        clears(Node* &p);
    
37. private:
    
38.         void        rotateLeft(Node* &k2);
    
39.         void        rotateRight(Node* &k2);
    
40.         void        rotateLeftDouble(Node* &p);
    
41.         void        rotateRightDouble(Node* &p);
    
42.         int                height(Node* p)const{ return p == NULL ? -1 : p->h ;}
    
43.         int                max(int x,int y){return x>y?x:y;}
    
44. private:
    
45.         Node* mRoot;
    
46.         int mLength;
    
47. 
    
48. };
    
49. template<typename Type> AVLTree<Type>::AVLTree():mRoot(NULL),mLength(0)
    
50. {
    
51. }
    
52. 
    
53. template<typename Type> AVLTree<Type>::AVLTree(Type arr[],int nLength):mRoot(NULL),mLength(0)
    
54. {
    
55.         for(int i=0;i<nLength;i++)
    
56.         {
    
57.                 insert(arr[i],mRoot);
    
58.         }
    
59. }
    
60. 
    
61. template<typename Type> AVLTree<Type>::~AVLTree()
    
62. {
    
63.         clears(mRoot);
    
64. }
    
65. template<typename Type> bool AVLTree<Type>::insert(Type e,Node* &p)
    
66. {
    
67.         if( p== NULL)
    
68.         {
    
69.                 p = new Node(e);
    
70.                 mLength++;
    
71.         }
    
72.         else if(e < p->e)
    
73.         {
    
74.                 insert(e,p->left);
    
75.                 if( height(p->left) - height(p->right) == 2)
    
76.                 {
    
77.                         if (e < p->left->e)
    
78.                                 rotateLeft(p);
    
79.                         else
    
80.                                 rotateLeftDouble(p);
    
81.                 }
    
82.         }
    
83.         else if(e > p->e)
    
84.         {
    
85.                 insert(e,p->right);
    
86.                 if( height(p->left) - height(p->right) == -2)
    
87.                 {
    
88.                         if (e > p->right->e)
    
89.                                 rotateRight(p);
    
90.                         else
    
91.                                 rotateRightDouble(p);
    
92.                 }
    
93.         }
    
94.         else // e ia already exist
    
95.         {       
    
96.                 //return false;
    
97.         }
    
98.         p->h = max( height(p->left),height(p->right) )+1;
    
99.         return true;
    
100. }
     
101. 
     
102. template<typename Type> void AVLTree<Type>::rotateLeft(Node*& k2)
     
103. {
     
104.         Node* k1 = k2->left;
     
105.         k2->left = k1->right;
     
106.         k1->right = k2;
     
107. 
     
108.         k1->h = max( height(k1->left),height(k1->right) ) + 1;
     
109.         k2->h = max( height(k2->left),height(k2->right) ) + 1;
     
110.         k2 = k1;// join the original node
     
111. }
     
112. 
     
113. template<typename Type> void AVLTree<Type>::rotateRight(Node* &k2)
     
114. {
     
115.         Node* k1 = k2->right;
     
116.         k2->right = k1->left;
     
117.         k1->left = k2;
     
118. 
     
119.         k1->h = max( height(k1->left),height(k1->right) ) + 1;
     
120.         k2->h = max( height(k2->left),height(k2->right) ) + 1;
     
121.         //k1=k2，因为在insert函数中传入的是p->left或者p->right的引用，所以这里能把根结点赋给其父结点的子节点
     
122.         k2 = k1;
     
123. }
     
124. 
     
125. template<typename Type> void AVLTree<Type>::rotateLeftDouble(Node*& k3)
     
126. {
     
127.         rotateRight(k3->left);
     
128.         rotateLeft(k3);
     
129. }
     
130. template<typename Type> void AVLTree<Type>::rotateRightDouble(Node*& k3)
     
131. {
     
132.         rotateLeft(k3->right);
     
133.         rotateRight(k3);
     
134. }
     
135. 
     
136. template<typename Type> void AVLTree<Type>::traverse(Node* p)const
     
137. {
     
138.         if( p == NULL)
     
139.                 return;
     
140.         else
     
141.         {
     
142.                 traverse(p->left);
     
143.                 cout<<"element:"<<p->e<<endl; //traverse by mid
     
144.                 traverse(p->right);       
     
145.         }
     
146. }
     
147. 
     
148. template<typename Type> void AVLTree<Type>::traverseByLevel(Node* root)const
     
149. {
     
150.         if(root == NULL)
     
151.         {
     
152.                 cout<<"The tree is empty"<<endl;
     
153.                 return;
     
154.         }
     
155.         queue<Node*> que;
     
156.         que.push(root);
     
157.         while( !que.empty() )
     
158.         {
     
159.                 Node* ptr = que.front();
     
160.                 que.pop();
     
161.                 cout<<"element:"<<ptr->e<<"        th:"<<height(ptr->left) - height(ptr->right)<<endl;
     
162.                 if(ptr->left != NULL)
     
163.                         que.push(ptr->left);
     
164.                 if(ptr->right != NULL)
     
165.                         que.push(ptr->right);
     
166.         }
     
167. }
     
168. 
     
169. template<typename Type> typename AVLTree<Type>::Node* & AVLTree<Type>::getParent(Node* p)
     
170. {  
     
171.     if( p == m_root)  
     
172.         return NULL;  
     
173.     Node* ptr = m_root;  
     
174.     Node* ptf = ptr;  
     
175.     while( ptr != NULL )  
     
176.     {  
     
177.         if ( ptr->e == p->e )  
     
178.             return ptf;  
     
179.         if ( ptr->e > p->e )  
     
180.         {  
     
181.             ptf = ptr;  
     
182.             ptr = ptr->leftChild;  
     
183.         }  
     
184.         else  
     
185.         {  
     
186.             ptf = ptr;  
     
187.             ptr = ptr->rightChild;
     
188.         }  
     
189.     }   
     
190. }
     
191. 
     
192. template<typename Type> typename AVLTree<Type>::Node*& AVLTree<Type>::find(Type e)const
     
193. {  
     
194.     Node* ptr = m_root;  
     
195.   
     
196.     while(ptr != NULL)  
     
197.     {  
     
198.         if ( ptr->e == e )  
     
199.             return ptr;  
     
200.         if ( ptr->e > e )  
     
201.             ptr = ptr->leftChild;  
     
202.         else  
     
203.             ptr = ptr->rightChild;  
     
204.     }  
     
205.     //if ( ptr == NULL )  
     
206.     return NULL;  
     
207. }
     
208. 
     
209. template<typename Type> void AVLTree<Type>::clears(Node*& p)
     
210. {
     
211.         if( p == NULL )
     
212.                 return;
     
213.         else
     
214.         {
     
215.                 clears(p->left);
     
216.                 clears(p->right);
     
217.                 delete p;
     
218.                 p = NULL;
     
219.                 mLength--;
     
220.         }
     
221. }
     
222. 
     
223. template<typename Type> void AVLTree<Type>::clear()
     
224. {
     
225.         clears(mRoot);
     
226. }
     
227. 
     
228. template<typename Type> void AVLTree<Type>::erase(Type e,Node* &p)
     
229. {
     
230.         if( p == NULL)
     
231.                 return;
     
232.         if( e > p->e)
     
233.         {
     
234.                 erase(e,p->right);
     
235.                 if( height(p->left) - height(p->right) == 2)
     
236.                 {
     
237.                         if( height(p->left->left) > height(p->left->right) )
     
238.                                 rotateLeft(p);
     
239.                         else
     
240.                                 rotateLeftDouble(p);
     
241.                 }
     
242.         }
     
243.         else if( e < p->e)
     
244.         {
     
245.                 erase(e,p->left);
     
246.                 if( height(p->left) - height(p->right) == -2)
     
247.                 {
     
248.                         if( height(p->right->right) > height(p->right->left) )
     
249.                                 rotateRight(p);
     
250.                         else
     
251.                                 rotateRightDouble(p);
     
252.                 }
     
253.         }
     
254.         else if ( e == p->e && p->left!= NULL && p->right!= NULL)
     
255.         {
     
256.                 Node* pmax = p->left;
     
257.                 while( pmax->right != NULL)
     
258.                 {
     
259.                         pmax = pmax->right;
     
260.                 }
     
261.                 p->e = pmax->e;
     
262.                 erase(p->e,p->left);
     
263.         }
     
264.         else //最终的删除会在这里执行
     
265.         {
     
266.                 Node* pNew = p->left==NULL ? p->right : p->left;
     
267.                 delete p;
     
268.                 p = pNew;
     
269.                 mLength--;
     
270.         }
     
271.         if ( p!=NULL)
     
272.                 p->h = max( height(p->left),height(p->right)) + 1;
     
273. }
     
274. #endif

复制代码

main.cpp

1. //main.cpp
   
2. #include <iostream>
   
3. #include "AVLTree.h"
   
4. using namespace std;
   
5. 
   
6. void main()
   
7. {
   
8.         int Arr[9] = {6,2,8,4,10,0,12,16,14};
   
9.         AVLTree<int> Tr(Arr,9);
   
10.         Tr.traverse(Tr.getRoot());
    
11.         Tr.traverseByLevel(Tr.getRoot());
    
12. 
    
13.         Tr.erase(14,Tr.getRoot());
    
14.         Tr.traverse(Tr.getRoot());
    
15.         Tr.traverseByLevel(Tr.getRoot());
    
16.         cout<<"Tree's length is:"<<Tr.getLength()<<endl;
    
17.         Tr.clear();
    
18.         cout<<"Tree's length is:"<<Tr.getLength()<<endl;
    
19. }

复制代码