AVL树

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define MaxSize 1000
  5 #define MAX(a,b)    ( (a) > (b) ? (a) : (b) )
  6 
  7 //set empty Treenode's height is 0,according to WIKIPEDIA
  8 typedef int ElementType;
  9 
 10 struct AVLTreeNode
 11 {
 12     ElementType Element;
 13     int Height;
 14     struct AVLTreeNode *Left;
 15     struct AVLTreeNode *Right;
 16 };
 17 
 18 struct AVLTreeNode *AVLTreeInit()
 19 {
 20     struct AVLTreeNode *TreeRoot = NULL;
 21 
 22     return TreeRoot;
 23 }
 24 
 25 int GetAVLTreeNodeHeight(struct AVLTreeNode *TreeNode)
 26 {
 27     if(TreeNode==NULL)
 28         return 0;
 29     return TreeNode -> Height;
 30 }
 31 
 32 struct AVLTreeNode *LeftLeftRotation(struct AVLTreeNode *OriginalHeigher)
 33 {
 34     struct AVLTreeNode *OHLeft = OriginalHeigher->Left;
 35 
 36     OriginalHeigher -> Left = OHLeft -> Right;
 37     OHLeft -> Right = OriginalHeigher;
 38 
 39     OriginalHeigher->Height = MAX(GetAVLTreeNodeHeight(OriginalHeigher->Left),GetAVLTreeNodeHeight(OriginalHeigher->Right))+1;
 40     OHLeft->Height = MAX(GetAVLTreeNodeHeight(OHLeft->Left),GetAVLTreeNodeHeight(OHLeft->Right))+1;
 41 
 42     return OHLeft;
 43 }
 44 
 45 struct AVLTreeNode *RightRightRotation(struct AVLTreeNode *OriginalHeigher)
 46 {
 47     struct AVLTreeNode *OHRight = OriginalHeigher->Right;
 48 
 49     OriginalHeigher -> Right = OHRight -> Left;
 50     OHRight -> Left = OriginalHeigher;
 51 
 52     OriginalHeigher->Height = MAX(GetAVLTreeNodeHeight(OriginalHeigher->Left),GetAVLTreeNodeHeight(OriginalHeigher->Right))+1;
 53     OHRight->Height = MAX(GetAVLTreeNodeHeight(OHRight->Left),GetAVLTreeNodeHeight(OHRight->Right))+1;
 54 
 55     return OHRight;
 56 }
 57 
 58 struct AVLTreeNode *LeftRightRotation(struct AVLTreeNode *OriginalHeighest)
 59 {
 60     OriginalHeighest->Left = RightRightRotation(OriginalHeighest->Left);
 61 
 62     return LeftLeftRotation(OriginalHeighest);
 63 }
 64 
 65 struct AVLTreeNode *RightLeftRotation(struct AVLTreeNode *OriginalHeighest)
 66 {
 67     OriginalHeighest->Left = LeftLeftRotation(OriginalHeighest->Right);
 68 
 69     return RightRightRotation(OriginalHeighest);
 70 }
 71 
 72 //warning:decline the same value node
 73 struct AVLTreeNode *AVLTreeNodeInsert(ElementType ToBeInsert,struct AVLTreeNode *TreeRoot)
 74 {
 75     if(TreeRoot==NULL)
 76     {
 77         TreeRoot = malloc(sizeof(struct AVLTreeNode));
 78         TreeRoot -> Element = ToBeInsert;
 79         TreeRoot -> Height = 0;
 80         TreeRoot -> Left = TreeRoot -> Right = NULL;
 81     }
 82     else if(ToBeInsert < TreeRoot->Element)
 83     {
 84         TreeRoot->Left = AVLTreeNodeInsert(ToBeInsert,TreeRoot->Left);
 85         if(GetAVLTreeNodeHeight(TreeRoot->Left)-GetAVLTreeNodeHeight(TreeRoot->Right)==2)
 86         {
 87             if(ToBeInsert < TreeRoot->Left->Element)
 88             {
 89                 TreeRoot = LeftLeftRotation(TreeRoot);
 90             }
 91             else
 92             {
 93                 TreeRoot = LeftRightRotation(TreeRoot);
 94             }
 95         }
 96     }
 97     else if(ToBeInsert > TreeRoot->Element)
 98     {
 99         TreeRoot->Right = AVLTreeNodeInsert(ToBeInsert,TreeRoot->Right);
100         if(GetAVLTreeNodeHeight(TreeRoot->Right)-GetAVLTreeNodeHeight(TreeRoot->Left)==2)
101         {
102             if(ToBeInsert > TreeRoot->Right->Element)
103             {
104                 TreeRoot = RightRightRotation(TreeRoot);
105             }
106             else
107             {
108                 TreeRoot = RightLeftRotation(TreeRoot);
109             }
110         }
111     }
112     else //if ToBeInsert == TreeRoot->Element
113     {
114         printf("ERROR
");
115     }
116 
117     TreeRoot->Height = MAX(GetAVLTreeNodeHeight(TreeRoot->Left),GetAVLTreeNodeHeight(TreeRoot->Right))+1;
118     return TreeRoot;
119 }
120 
121 struct AVLTreeNode *BinarySearchTreeNodeFindMax(struct AVLTreeNode *TreeRoot)
122 {
123     if(TreeRoot==NULL)
124     {
125         return NULL;
126     }
127     else if(TreeRoot->Right==NULL)
128     {
129         return TreeRoot;
130     }
131     else
132     {
133         return BinarySearchTreeNodeFindMax(TreeRoot->Right);
134     }
135 }
136 
137 struct AVLTreeNode *BinarySearchTreeNodeFindMin(struct AVLTreeNode *TreeRoot)
138 {
139     if(TreeRoot==NULL)
140     {
141         return NULL;
142     }
143     else if(TreeRoot->Left==NULL)
144     {
145         return TreeRoot;
146     }
147     else
148     {
149         return BinarySearchTreeNodeFindMin(TreeRoot->Left);
150     }
151 }
152 
153 //if doesn't find,return NULL
154 struct AVLTreeNode *AVLTreeNodeDelete(ElementType ToBeDelete,struct AVLTreeNode *TreeRoot)
155 {
156     if(TreeRoot == NULL)
157         return NULL;
158 
159     struct AVLTreeNode *TmpCell;
160     if(ToBeDelete < TreeRoot -> Element)
161     {
162         TreeRoot->Left = AVLTreeNodeDelete(ToBeDelete,TreeRoot->Left);
163         if(GetAVLTreeNodeHeight(TreeRoot->Right)-GetAVLTreeNodeHeight(TreeRoot->Left)==2)
164         {
165             TmpCell = TreeRoot->Right;
166             if(GetAVLTreeNodeHeight(TmpCell->Right)>GetAVLTreeNodeHeight(TmpCell->Left))
167             {
168                 TreeRoot = RightLeftRotation(TreeRoot);
169             }
170             else
171             {
172                 TreeRoot = RightRightRotation(TreeRoot);
173             }
174         }
175     }
176     else if(ToBeDelete > TreeRoot -> Element)
177     {
178         TreeRoot->Right = AVLTreeNodeDelete(ToBeDelete,TreeRoot->Right);
179         if(GetAVLTreeNodeHeight(TreeRoot->Left)-GetAVLTreeNodeHeight(TreeRoot->Right)==2)
180         {
181             struct AVLTreeNode *TmpCell = TreeRoot->Left;
182             if(GetAVLTreeNodeHeight(TmpCell->Left)>GetAVLTreeNodeHeight(TmpCell->Right))
183             {
184                 TreeRoot = LeftRightRotation(TreeRoot);
185             }
186             else
187             {
188                 TreeRoot = LeftLeftRotation(TreeRoot);
189             }
190         }
191     }
192     else //if(ToBeDelete == TreeRoot -> Element)
193     {
194         if(TreeRoot->Left && TreeRoot->Right)
195         {
196             if(GetAVLTreeNodeHeight(TreeRoot->Left)>GetAVLTreeNodeHeight(TreeRoot->Right))
197             {
198                 TmpCell = BinarySearchTreeNodeFindMax(TreeRoot -> Left);
199                 TreeRoot -> Element = TmpCell -> Element;
200                 TreeRoot -> Left = AVLTreeNodeDelete(TreeRoot->Element,TreeRoot->Left);
201             }
202             else
203             {
204                 TmpCell = BinarySearchTreeNodeFindMin(TreeRoot -> Right);
205                 TreeRoot -> Element = TmpCell -> Element;
206                 TreeRoot -> Right = AVLTreeNodeDelete(TreeRoot->Element,TreeRoot->Right);
207             }
208         }
209         else
210         {
211             TmpCell = TreeRoot;
212             if(TreeRoot->Left==NULL)
213             {
214                 TreeRoot = TreeRoot -> Right;
215             }
216             else if(TreeRoot->Right==NULL)
217             {
218                 TreeRoot = TreeRoot -> Left;
219             }
220             free(TmpCell);
221         }
222     }
223     return TreeRoot;
224 }
225 
226 int BinarySearchTreePreOrder(struct AVLTreeNode *TreeRoot)
227 {
228     if(TreeRoot!=NULL)
229     {
230         printf("%d
",TreeRoot -> Element);
231         BinarySearchTreePreOrder(TreeRoot->Left);
232         BinarySearchTreePreOrder(TreeRoot->Right);
233     }
234     return 0;
235 }
236 
237 int main()
238 {
239     struct AVLTreeNode *TreeRoot = AVLTreeInit();
240     TreeRoot = AVLTreeNodeInsert(1,TreeRoot);
241     TreeRoot = AVLTreeNodeInsert(2,TreeRoot);
242     TreeRoot = AVLTreeNodeInsert(3,TreeRoot);
243     TreeRoot = AVLTreeNodeInsert(4,TreeRoot);
244     TreeRoot = AVLTreeNodeInsert(5,TreeRoot);
245     TreeRoot = AVLTreeNodeInsert(6,TreeRoot);
246     TreeRoot = AVLTreeNodeInsert(7,TreeRoot);
247     TreeRoot = AVLTreeNodeDelete(2,TreeRoot);
248     printf("%d
",TreeRoot->Left->Element);
249     return 0;
250 }