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