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