Basic implementation of an AVL tree storing ints. This is not particularly optimized, and effectively implements a set data type with the ability to delete the minimum value as in a heap.
1. Header file
1 /* implementation of an AVL tree with explicit heights */
2
3 typedef struct avlNode *AvlTree;
4
5 /* empty avl tree is just a null pointer */
6
7 #define AVL_EMPTY (0)
8
9 /* free a tree */
10 void avlDestroy(AvlTree t);
11
12 /* return the height of a tree */
13 int avlGetHeight(AvlTree t);
14
15 /* return nonzero if key is present in tree */
16 int avlSearch(AvlTree t, int key);
17
18 /* insert a new element into a tree */
19 /* note *t is actual tree */
20 void avlInsert(AvlTree *t, int key);
21
22 /* run sanity checks on tree (for debugging) */
23 /* assert will fail if heights are wrong */
24 void avlSanityCheck(AvlTree t);
25
26 /* print all keys of the tree in order */
27 void avlPrintKeys(AvlTree t);
28
29 /* delete and return minimum value in a tree */
30 int avlDeleteMin(AvlTree *t);
2. Implementation
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4
5 #include "avlTree.h"
6
7 /* implementation of an AVL tree with explicit heights */
8
9 struct avlNode {
10 struct avlNode *child[2]; /* left and right */
11 int key;
12 int height;
13 };
14
15 /* free a tree */
16 void
17 avlDestroy(AvlTree t)
18 {
19 if(t != AVL_EMPTY) {
20 avlDestroy(t->child[0]);
21 avlDestroy(t->child[1]);
22 free(t);
23 }
24 }
25
26 /* return height of an AVL tree */
27 int
28 avlGetHeight(AvlTree t)
29 {
30 if(t != AVL_EMPTY) {
31 return t->height;
32 } else {
33 return 0;
34 }
35 }
36
37 /* return nonzero if key is present in tree */
38 int
39 avlSearch(AvlTree t, int key)
40 {
41 if(t == AVL_EMPTY) {
42 return 0;
43 } else if(t->key == key) {
44 return 1;
45 } else {
46 return avlSearch(t->child[key > t->key], key);
47 }
48 }
49
50 #define Max(x,y) ((x)>(y) ? (x) : (y))
51
52 /* assert height fields are correct throughout tree */
53 void
54 avlSanityCheck(AvlTree root)
55 {
56 int i;
57
58 if(root != AVL_EMPTY) {
59 for(i = 0; i < 2; i++) {
60 avlSanityCheck(root->child[i]);
61 }
62
63 assert(root->height == 1 + Max(avlGetHeight(root->child[0]), avlGetHeight(root->child[1])));
64 }
65 }
66
67 /* recompute height of a node */
68 static void
69 avlFixHeight(AvlTree t)
70 {
71 assert(t != AVL_EMPTY);
72
73 t->height = 1 + Max(avlGetHeight(t->child[0]), avlGetHeight(t->child[1]));
74 }
75
76 /* rotate child[d] to root */
77 /* assumes child[d] exists */
78 /* Picture:
79 *
80 * y x
81 * / \ <==> / \
82 * x C A y
83 * / \ / \
84 * A B B C
85 *
86 */
87 static void
88 avlRotate(AvlTree *root, int d)
89 {
90 AvlTree oldRoot;
91 AvlTree newRoot;
92 AvlTree oldMiddle;
93
94 oldRoot = *root;
95 newRoot = oldRoot->child[d];
96 oldMiddle = newRoot->child[!d];
97
98 oldRoot->child[d] = oldMiddle;
99 newRoot->child[!d] = oldRoot;
100 *root = newRoot;
101
102 /* update heights */
103 avlFixHeight((*root)->child[!d]); /* old root */
104 avlFixHeight(*root); /* new root */
105 }
106
107
108 /* rebalance at node if necessary */
109 /* also fixes height */
110 static void
111 avlRebalance(AvlTree *t)
112 {
113 int d;
114
115 if(*t != AVL_EMPTY) {
116 for(d = 0; d < 2; d++) {
117 /* maybe child[d] is now too tall */
118 if(avlGetHeight((*t)->child[d]) > avlGetHeight((*t)->child[!d]) + 1) {
119 /* imbalanced! */
120 /* how to fix it? */
121 /* need to look for taller grandchild of child[d] */
122 if(avlGetHeight((*t)->child[d]->child[d]) > avlGetHeight((*t)->child[d]->child[!d])) {
123 /* same direction grandchild wins, do single rotation */
124 avlRotate(t, d);
125 } else {
126 /* opposite direction grandchild moves up, do double rotation */
127 avlRotate(&(*t)->child[d], !d);
128 avlRotate(t, d);
129 }
130
131 return; /* avlRotate called avlFixHeight */
132 }
133 }
134
135 /* update height */
136 avlFixHeight(*t);
137 }
138 }
139
140 /* insert into tree */
141 /* this may replace root, which is why we pass
142 * in a AvlTree * */
143 void
144 avlInsert(AvlTree *t, int key)
145 {
146 /* insertion procedure */
147 if(*t == AVL_EMPTY) {
148 /* new t */
149 *t = malloc(sizeof(struct avlNode));
150 assert(*t);
151
152 (*t)->child[0] = AVL_EMPTY;
153 (*t)->child[1] = AVL_EMPTY;
154
155 (*t)->key = key;
156
157 (*t)->height = 1;
158
159 /* done */
160 return;
161 } else if(key == (*t)->key) {
162 /* nothing to do */
163 return;
164 } else {
165 /* do the insert in subtree */
166 avlInsert(&(*t)->child[key > (*t)->key], key);
167
168 avlRebalance(t);
169
170 return;
171 }
172 }
173
174
175 /* print all elements of the tree in order */
176 void
177 avlPrintKeys(AvlTree t)
178 {
179 if(t != AVL_EMPTY) {
180 avlPrintKeys(t->child[0]);
181 printf("%d\n", t->key);
182 avlPrintKeys(t->child[1]);
183 }
184 }
185
186
187 /* delete and return minimum value in a tree */
188 int
189 avlDeleteMin(AvlTree *t)
190 {
191 AvlTree oldroot;
192 int minValue;
193
194 assert(t != AVL_EMPTY);
195
196 if((*t)->child[0] == AVL_EMPTY) {
197 /* root is min value */
198 oldroot = *t;
199 minValue = oldroot->key;
200 *t = oldroot->child[1];
201 free(oldroot);
202 } else {
203 /* min value is in left subtree */
204 minValue = avlDeleteMin(&(*t)->child[0]);
205 }
206
207 avlRebalance(t);
208 return minValue;
209 }
210
211 /* delete the given value */
212 void
213 avlDelete(AvlTree *t, int key)
214 {
215 AvlTree oldroot;
216
217 if(*t != AVL_EMPTY) {
218 return;
219 } else if((*t)->key == key) {
220 /* do we have a right child? */
221 if((*t)->child[1] != AVL_EMPTY) {
222 /* give root min value in right subtree */
223 (*t)->key = avlDeleteMin(&(*t)->child[1]);
224 } else {
225 /* splice out root */
226 oldroot = (*t);
227 *t = (*t)->child[0];
228 free(oldroot);
229 }
230 } else {
231 avlDelete(&(*t)->child[key > (*t)->key], key);
232 }
233
234 /* rebalance */
235 avlRebalance(t);
236 }
3. Test code and Makefile
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4
5 #include "avlTree.h"
6
7 #define N (1024)
8 #define MULTIPLIER (97)
9
10 int
11 main(int argc, char **argv)
12 {
13 AvlTree t = AVL_EMPTY;
14 int i;
15
16 if(argc != 1) {
17 fprintf(stderr, "Usage: %s\n", argv[0]);
18 return 1;
19 }
20
21 for(i = 0; i < N; i++) {
22 avlInsert(&t, (i*MULTIPLIER) % N);
23 }
24
25 printf("height %d\n", avlGetHeight(t));
26
27 assert(avlSearch(t, N-1) == 1);
28 assert(avlSearch(t, N) == 0);
29
30 avlSanityCheck(t);
31
32 for(i = 0; i < N-1; i++) {
33 avlDeleteMin(&t);
34 }
35
36 avlSanityCheck(t);
37
38 avlPrintKeys(t);
39
40 avlDestroy(t);
41
42 return 0;
43 }