aboutsummaryrefslogtreecommitdiff
path: root/avl.c
diff options
context:
space:
mode:
Diffstat (limited to 'avl.c')
-rw-r--r--avl.c453
1 files changed, 453 insertions, 0 deletions
diff --git a/avl.c b/avl.c
new file mode 100644
index 0000000..201dc5b
--- /dev/null
+++ b/avl.c
@@ -0,0 +1,453 @@
1// AVL Tree
2#include <stdio.h>
3#include <stdlib.h>
4#include <stdbool.h>
5#include <time.h>
6
7/* utils */
8#include "util.h"
9
10// TODO: [x] Review: http://www.inr.ac.ru/~info21/ADen/
11// [x] Tests: https://stackoverflow.com/q/3955680
12
13typedef int T;
14
15struct tree_node {
16 struct tree_node *left, *right;
17 int bal;
18 T key;
19 int count; /* collision counter */
20 /* ggf. weitere Felder... */
21};
22
23static struct tree_node *
24insert_r(T x, struct tree_node *p, bool *h)
25{
26 struct tree_node *p1, *p2;
27
28 if ( p == NULL ) {
29 *h = true;
30
31 p = malloc(sizeof *p);
32 if ( p != NULL ) {
33 p->left = NULL;
34 p->right = NULL;
35 p->bal = 0;
36
37 p->key = x;
38 p->count = 1; /* hit counter */
39 }
40 else
41 ERROR("out of memory");
42 }
43 else if ( x < p->key ) {
44 p->left = insert_r(x, p->left, h);
45
46 if ( *h ) {
47 if ( p->bal == +1 ) {
48 p->bal = 0;
49 *h = false;
50 }
51 else if ( p->bal == 0 ) {
52 p->bal = -1;
53 }
54 else /* if ( p->bal == -1 ) */ {
55 p1 = p->left;
56 if ( p1->bal == -1 ) { /* single LL rotation */
57 p->left = p1->right; p1->right = p;
58 p->bal = 0; p = p1;
59 }
60 else { /* double LR rotation */
61 p2 = p1->right;
62 p1->right = p2->left; p2->left = p1;
63 p->left = p2->right; p2->right = p;
64 p->bal = ( p2->bal == -1 ) ? +1 : 0;
65 p1->bal = ( p2->bal == +1 ) ? -1 : 0;
66 p = p2;
67 }
68 p->bal = 0;
69 *h = false;
70 }
71 }
72 }
73 else if ( x > p->key ) {
74 p->right = insert_r(x, p->right, h);
75
76 if ( *h ) {
77 if ( p->bal == -1 ) {
78 p->bal = 0;
79 *h = false;
80 }
81 else if ( p->bal == 0 ) {
82 p->bal = +1;
83 }
84 else /* if ( p->bal == +1 ) */ {
85 p1 = p->right;
86 if ( p1->bal == +1 ) { /* single RR rotation */
87 p->right = p1->left; p1->left = p;
88 p->bal = 0; p = p1;
89 }
90 else { /* double RL rotation */
91 p2 = p1->left;
92 p1->left = p2->right; p2->right = p1;
93 p->right = p2->left; p2->left = p;
94 p->bal = ( p2->bal == +1 ) ? -1 : 0;
95 p1->bal = ( p2->bal == -1 ) ? +1 : 0;
96 p = p2;
97 }
98 p->bal = 0;
99 *h = false;
100 }
101 }
102 }
103 else {
104 /* handle collision! */
105 p->count++; /* hit counter */
106 *h = false;
107 }
108 if ( p == NULL )
109 ERROR("das hier sollte niemals passieren");
110 return p;
111}
112
113struct tree_node *
114insert(struct tree_node *tree, T data)
115{
116 bool h = false;
117 return insert_r(data, tree, &h);
118}
119
120static struct tree_node *
121balanceL(struct tree_node *p, bool *h)
122{
123 if ( p->bal == -1 ) {
124 p->bal = 0;
125 }
126 else if ( p->bal == 0 ) {
127 p->bal = +1;
128 *h = false;
129 }
130 else /* if ( p->bal == +1 ) */ { /* rebalance */
131 struct tree_node *p1 = p->right;
132 if ( p1->bal >= 0 ) { /* singla RR rotation */
133 p->right = p1->left;
134 p1->left = p;
135 if ( p1->bal == 0 ) {
136 p->bal = +1;
137 p1->bal = -1;
138 *h = false;
139 }
140 else {
141 p->bal = 0;
142 p1->bal = 0;
143 }
144 p = p1;
145 }
146 else { /* double RL rotation */
147 struct tree_node *p2 = p1->left;
148 p1->left = p2->right;
149 p2->right = p1;
150 p->right = p2->left;
151 p2->left = p;
152 p->bal = ( p2->bal == +1 ) ? -1 : 0;
153 p1->bal = ( p2->bal == -1 ) ? +1 : 0;
154 p = p2;
155 p2->bal = 0;
156 }
157 }
158 return p;
159}
160
161static struct tree_node *
162balanceR(struct tree_node *p, bool *h)
163{
164 if ( p->bal == +1 ) {
165 p->bal = 0;
166 }
167 else if ( p->bal == 0 ) {
168 p->bal = -1;
169 *h = false;
170 }
171 else /* p->bal == -1 */ { /* rebalance */
172 struct tree_node *p1 = p->left;
173 if ( p1->bal <= 0 ) { /* single LL rotation */
174 p->left = p1->right;
175 p1->right = p;
176 if ( p1->bal == 0 ) {
177 p->bal = -1;
178 p1->bal = +1;
179 *h = false;
180 }
181 else {
182 p->bal = 0;
183 p1->bal = 0;
184 }
185 p = p1;
186 }
187 else { /* double LR rotation */
188 struct tree_node *p2 = p1->right;
189 p1->right = p2->left;
190 p2->left = p1;
191 p->left = p2->right;
192 p2->right = p;
193 p->bal = ( p2->bal == -1 ) ? +1 : 0;
194 p1->bal = ( p2->bal == +1 ) ? -1 : 0;
195 p = p2;
196 p2->bal = 0;
197 }
198 }
199 return p;
200}
201
202static void
203del(struct tree_node **q, struct tree_node **r, bool *h)
204{
205 if ( (*r)->right != NULL ) {
206 del(q, &(*r)->right, h);
207 if ( *h )
208 *r = balanceR(*r, h);
209 }
210 else {
211 /* copy data */
212 (*q)->key = (*r)->key;
213 (*q)->count = (*r)->count;
214
215 *q = *r;
216 *r = (*r)->left;
217 *h = true;
218 }
219}
220
221static struct tree_node *
222delete_r(T x, struct tree_node *p, bool *h)
223{
224 if ( p == NULL ) {
225 ERROR("key not found");
226 }
227 else if ( x < p->key ) {
228 p->left = delete_r(x, p->left, h);
229 if ( *h )
230 p = balanceL(p, h);
231 }
232 else if ( x > p->key ) {
233 p->right = delete_r(x, p->right, h);
234 if ( *h )
235 p = balanceR(p, h);
236 }
237 else /* if ( x == p->key ) */ {
238 struct tree_node *q = p;
239 if ( q->right == NULL ) {
240 p = q->left;
241 *h = true;
242 }
243 else if ( q->left == NULL ) {
244 p = q->right;
245 *h = true;
246 }
247 else {
248 del(&q, &q->left, h);
249 if ( *h )
250 p = balanceL(p, h);
251 }
252 free(q);
253 }
254 return p;
255}
256
257struct tree_node *
258delete(struct tree_node *tree, T data)
259{
260 bool h = false;
261 return delete_r(data, tree, &h);
262}
263
264
265// aux display and verification routines, helpful but not essential
266struct trunk {
267 struct trunk *prev;
268 char * str;
269};
270
271void show_trunks(struct trunk *p)
272{
273 if (!p) return;
274 show_trunks(p->prev);
275 printf("%s", p->str);
276}
277
278// this is very haphazzard
279void show_tree(struct tree_node *root, struct trunk *prev, int is_left)
280{
281 if (root == NULL) return;
282
283 struct trunk this_disp = { prev, " " };
284 char *prev_str = this_disp.str;
285 show_tree(root->right, &this_disp, 1);
286
287 if (!prev)
288 this_disp.str = "---";
289 else if (is_left) {
290 this_disp.str = ".--";
291 prev_str = " |";
292 } else {
293 this_disp.str = "`--";
294 prev->str = prev_str;
295 }
296
297 show_trunks(&this_disp);
298 if ( root->key >= 'A' && root->key <= 'Z' )
299 printf("%c\n", root->key);
300 else
301 printf("%d\n", root->key);
302
303 if (prev) prev->str = prev_str;
304 this_disp.str = " |";
305
306 show_tree(root->left, &this_disp, 0);
307 if (!prev) puts("");
308}
309
310void
311print(struct tree_node *tree)
312{
313 if ( tree ) {
314 print(tree->left);
315 printf("%d (%d)\n", tree->key, tree->bal);
316 print(tree->right);
317 }
318}
319
320int
321main()
322{
323
324
325#if 0 /* 1a/b */
326 tree = insert(tree, 20);
327 tree = insert(tree, 4);
328 show_tree(tree, 0, 0);
329
330 //tree = insert(tree, 15);
331 tree = insert(tree, 8);
332 show_tree(tree, 0, 0);
333#endif
334
335#if 0 /* 2a/b */
336 tree = insert(tree, 20);
337 tree = insert(tree, 4);
338 tree = insert(tree, 26);
339 tree = insert(tree, 3);
340 tree = insert(tree, 9);
341 show_tree(tree, 0, 0);
342
343 //tree = insert(tree, 15);
344 tree = insert(tree, 8);
345 show_tree(tree, 0, 0);
346#endif
347
348#if 0 /* 3a/b */
349 tree = insert(tree, 20);
350 tree = insert(tree, 4);
351 tree = insert(tree, 26);
352 tree = insert(tree, 3);
353 tree = insert(tree, 9);
354 tree = insert(tree, 21);
355 tree = insert(tree, 30);
356 tree = insert(tree, 2);
357 tree = insert(tree, 7);
358 tree = insert(tree, 11);
359 show_tree(tree, 0, 0);
360
361 //tree = insert(tree, 15);
362 tree = insert(tree, 8);
363 show_tree(tree, 0, 0);
364#endif
365
366#if 0
367 tree = insert(tree, 2);
368 tree = insert(tree, 1);
369 tree = insert(tree, 4);
370 tree = insert(tree, 3);
371 tree = insert(tree, 5);
372 show_tree(tree, 0, 0);
373
374 tree = delete(tree, 1);
375 show_tree(tree, 0, 0);
376#endif
377
378#if 0
379 tree = insert(tree, 6);
380 tree = insert(tree, 2);
381 tree = insert(tree, 9);
382 tree = insert(tree, 1);
383 tree = insert(tree, 4);
384 tree = insert(tree, 8);
385 tree = insert(tree, 'B');
386 tree = insert(tree, 3);
387 tree = insert(tree, 5);
388 tree = insert(tree, 7);
389 tree = insert(tree, 'A');
390 tree = insert(tree, 'C');
391 tree = insert(tree, 'D');
392 show_tree(tree, 0, 0);
393
394 tree = delete(tree, 1);
395 show_tree(tree, 0, 0);
396#endif
397
398
399#if 0
400 tree = insert(tree, 5);
401 tree = insert(tree, 2);
402 tree = insert(tree, 8);
403 tree = insert(tree, 1);
404 tree = insert(tree, 3);
405 tree = insert(tree, 7);
406 tree = insert(tree, 'A');
407 tree = insert(tree, 4);
408 tree = insert(tree, 6);
409 tree = insert(tree, 9);
410 tree = insert(tree, 'B');
411 tree = insert(tree, 'C');
412 show_tree(tree, 0, 0);
413
414 tree = delete(tree, 1);
415 show_tree(tree, 0, 0);
416#endif
417
418
419#if 0
420 tree = insert(tree, 5);
421 tree = insert(tree, 3);
422 tree = insert(tree, 8);
423 tree = insert(tree, 2);
424 tree = insert(tree, 4);
425 tree = insert(tree, 7);
426 tree = insert(tree, 10);
427 tree = insert(tree, 1);
428 tree = insert(tree, 6);
429 tree = insert(tree, 9);
430 tree = insert(tree, 11);
431
432 tree = delete(tree, 4);
433 tree = delete(tree, 8);
434 tree = delete(tree, 6);
435 tree = delete(tree, 5);
436 tree = delete(tree, 2);
437 tree = delete(tree, 1);
438 tree = delete(tree, 7);
439
440 show_tree(tree, 0, 0);
441#endif
442
443 struct tree_node *tree = NULL;
444
445 srand(time(NULL));
446 for ( int i = 0; i != 300000; ++i )
447 tree = insert(tree, rand());
448
449 //show_tree(tree, 0, 0);
450
451 return EXIT_SUCCESS;
452}
453