From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sat, 9 Apr 2022 09:43:53 +0200
Subject: neue Verzeichnisstruktur

---
 avl.c | 470 ------------------------------------------------------------------
 1 file changed, 470 deletions(-)
 delete mode 100644 avl.c

(limited to 'avl.c')

diff --git a/avl.c b/avl.c
deleted file mode 100644
index 5bb4415..0000000
--- a/avl.c
+++ /dev/null
@@ -1,470 +0,0 @@
-// AVL Tree
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-
-/* utils */
-#include "util.h"
-
-// clang-format off
-
-// Review: http://www.inr.ac.ru/~info21/ADen/
-// Tests:  https://stackoverflow.com/q/3955680
-
-/* --8<-- avl_type */
-typedef int T;
-
-struct tree_node {
-	struct tree_node *left, *right;
-	int bal;
-	T key;
-	int count;	/* collision counter */
-	/* ggf. weitere Felder... */
-};
-/* -->8-- */
-
-/* --8<-- avl_insert_r */
-static struct tree_node *
-insert_r(T x, struct tree_node *p, bool *h)
-{
-	struct tree_node *p1, *p2;
-
-	if ( p == NULL ) {
-		*h = true;
-
-		p = malloc(sizeof *p);
-		if ( p ) {
-			p->left = NULL;
-			p->right = NULL;
-			p->bal = 0;
-
-			p->key = x;
-			p->count = 1;	/* hit counter */
-		}
-		else
-			ERROR("out of memory");
-	}
-	else if ( x < p->key ) {
-		p->left = insert_r(x, p->left, h);
-
-		if ( *h ) {
-			if ( p->bal == +1 ) {
-				p->bal = 0;
-				*h = false;
-			}
-			else if ( p->bal == 0 ) {
-				p->bal = -1;
-			}
-			else /* if ( p->bal == -1 ) */ {
-				p1 = p->left;
-				if ( p1->bal == -1 ) {	/* single LL rotation */
-					p->left = p1->right; p1->right = p;
-					p->bal = 0; p = p1;
-				}
-				else {					/* double LR rotation */
-					p2 = p1->right;
-					p1->right = p2->left; p2->left = p1;
-					p->left = p2->right; p2->right = p;
-					p->bal  = ( p2->bal == -1 ) ? +1 : 0;
-					p1->bal = ( p2->bal == +1 ) ? -1 : 0;
-					p = p2;
-				}
-				p->bal = 0;
-				*h = false;
-			}
-		}
-	}
-	else if ( x > p->key ) {
-		p->right = insert_r(x, p->right, h);
-
-		if ( *h ) {
-			if ( p->bal == -1 ) {
-				p->bal = 0;
-				*h = false;
-			}
-			else if ( p->bal == 0 ) {
-				p->bal = +1;
-			}
-			else /* if ( p->bal == +1 ) */ {
-				p1 = p->right;
-				if ( p1->bal == +1 ) {	/* single RR rotation */
-					p->right = p1->left; p1->left = p;
-					p->bal = 0; p = p1;
-				}
-				else {					/* double RL rotation */
-					p2 = p1->left;
-					p1->left = p2->right; p2->right = p1;
-					p->right = p2->left; p2->left = p;
-					p->bal  = ( p2->bal == +1 ) ? -1 : 0;
-					p1->bal = ( p2->bal == -1 ) ? +1 : 0;
-					p = p2;
-				}
-				p->bal = 0;
-				*h = false;
-			}
-		}
-	}
-	else {
-		/* handle collision! */
-		p->count++;	/* hit counter */
-		*h = false;
-	}
-	assert(p != NULL);
-
-	return p;
-}
-/* -->8-- */
-
-/* --8<-- avl_insert */
-struct tree_node *
-insert(struct tree_node *tree, T data)
-{
-	bool h = false;
-	return insert_r(data, tree, &h);
-}
-/* -->8-- */
-
-/* --8<-- avl_balanceL */
-static struct tree_node *
-balanceL(struct tree_node *p, bool *h)
-{
-	if ( p->bal == -1 ) {
-		p->bal = 0;
-	}
-	else if ( p->bal == 0 ) {
-		p->bal = +1;
-		*h = false;
-	}
-	else /* if ( p->bal == +1 ) */ {		/* rebalance */
-		struct tree_node *p1 = p->right;
-		if ( p1->bal >= 0 ) {				/* singla RR rotation */
-			p->right = p1->left; 
-			p1->left = p;
-			if ( p1->bal == 0 ) {
-				p->bal = +1;
-				p1->bal = -1;
-				*h = false;
-			}
-			else {
-				p->bal = 0;
-				p1->bal = 0;
-			}
-			p = p1;
-		}
-		else {								/* double RL rotation */
-			struct tree_node *p2 = p1->left;
-			p1->left = p2->right;
-			p2->right = p1;
-			p->right = p2->left;
-			p2->left = p;
-			p->bal  = ( p2->bal == +1 ) ? -1 : 0;
-			p1->bal = ( p2->bal == -1 ) ? +1 : 0;
-			p = p2;
-			p2->bal = 0;
-		}
-	}
-	return p;
-}
-/* -->8-- */
-
-/* --8<-- avl_balanceR */
-static struct tree_node *
-balanceR(struct tree_node *p, bool *h)
-{
-	if ( p->bal == +1 ) {
-		p->bal = 0;
-	}
-	else if ( p->bal == 0 ) {
-		p->bal = -1;
-		*h = false;
-	}
-	else /* p->bal == -1 */ {		/* rebalance */
-		struct tree_node *p1 = p->left;
-		if ( p1->bal <= 0 ) {		/* single LL rotation */
-			p->left = p1->right; 
-			p1->right = p;
-			if ( p1->bal == 0 ) {
-				p->bal = -1;
-				p1->bal = +1;
-				*h = false;
-			}
-			else {
-				p->bal = 0;
-				p1->bal = 0;
-			}
-			p = p1;
-		}
-		else {						/* double LR rotation */
-			struct tree_node *p2 = p1->right;
-			p1->right = p2->left;
-			p2->left = p1;
-			p->left = p2->right;
-			p2->right = p;
-			p->bal  = ( p2->bal == -1 ) ? +1 : 0;
-			p1->bal = ( p2->bal == +1 ) ? -1 : 0;
-			p = p2;
-			p2->bal = 0;
-		}
-	}
-	return p;
-}
-/* -->8-- */
-
-/* --8<-- avl_del */
-static void
-del(struct tree_node **q, struct tree_node **r, bool *h)
-{
-	if ( (*r)->right ) {
-		del(q, &(*r)->right, h);
-		if ( *h ) 
-			*r = balanceR(*r, h);
-	}
-	else {
-		/* copy data */
-		(*q)->key = (*r)->key;
-		(*q)->count = (*r)->count;
-
-		*q = *r;
-		*r = (*r)->left;
-		*h = true;
-	}
-}
-/* -->8-- */
-
-/* --8<-- avl_delete_r */
-static struct tree_node *
-delete_r(T x, struct tree_node *p, bool *h)
-{
-	if ( p == NULL ) {
-		ERROR("key not found");
-	}
-	else if ( x < p->key ) {
-		p->left = delete_r(x, p->left, h);
-		if ( *h )
-			p = balanceL(p, h);
-	}
-	else if ( x > p->key ) {
-		p->right = delete_r(x, p->right, h);
-		if ( *h )
-			p = balanceR(p, h);
-	}
-	else /* if ( x == p->key ) */ {
-		struct tree_node *q = p;
-		if ( q->right == NULL ) {
-			p = q->left;
-			*h = true;
-		}
-		else if ( q->left == NULL ) {
-			p = q->right;
-			*h = true;
-		}
-		else {
-			del(&q, &q->left, h);
-			if ( *h )
-				p = balanceL(p, h);
-		}
-		free(q);
-	}
-	return p;
-}
-/* -->8-- */
-
-/* --8<-- avl_delete */
-struct tree_node *
-delete(struct tree_node *tree, T data)
-{
-	bool h = false;
-	return delete_r(data, tree, &h);
-}
-/* -->8-- */
-
-// aux display and verification routines, helpful but not essential
-struct trunk {
-	struct trunk *prev;
-	char * str;
-};
- 
-void show_trunks(struct trunk *p)
-{
-	if (!p) return;
-	show_trunks(p->prev);
-	printf("%s", p->str);
-}
- 
-// this is very haphazzard
-void show_tree(struct tree_node *root, struct trunk *prev, int is_left)
-{
-	if (root == NULL) return;
-
-	struct trunk this_disp = { prev, "    " };
-	char *prev_str = this_disp.str;
-	show_tree(root->right, &this_disp, 1);
-
-	if (!prev)
-		this_disp.str = "---";
-	else if (is_left) {
-		this_disp.str = ".--";
-		prev_str = "   |";
-	} else {
-		this_disp.str = "`--";
-		prev->str = prev_str;
-	}
-
-	show_trunks(&this_disp);
-	if ( root->key >= 'A' && root->key <= 'Z' )
-		printf("%c\n", root->key);
-	else
-		printf("%d\n", root->key);
-
-	if (prev) prev->str = prev_str;
-	this_disp.str = "   |";
-
-	show_tree(root->left, &this_disp, 0);
-	if (!prev) puts("");
-}
-
-void
-print(struct tree_node *tree)
-{
-	if ( tree ) {
-		print(tree->left);
-		printf("%d (%d)\n", tree->key, tree->bal);
-		print(tree->right);
-	}
-}
-
-int
-main()
-{
-
-
-#if 0	/* 1a/b */
-	tree = insert(tree, 20);
-	tree = insert(tree,  4);
-	show_tree(tree, 0, 0);
-
-	//tree = insert(tree, 15);
-	tree = insert(tree,  8);
-	show_tree(tree, 0, 0);
-#endif
-
-#if 0	/* 2a/b */
-	tree = insert(tree, 20);
-	tree = insert(tree,  4);
-	tree = insert(tree, 26);
-	tree = insert(tree,  3);
-	tree = insert(tree,  9);
-	show_tree(tree, 0, 0);
-
-	//tree = insert(tree, 15);
-	tree = insert(tree,  8);
-	show_tree(tree, 0, 0);
-#endif
-
-#if 0	/* 3a/b */
-	tree = insert(tree, 20);
-	tree = insert(tree,  4);
-	tree = insert(tree, 26);
-	tree = insert(tree,  3);
-	tree = insert(tree,  9);
-	tree = insert(tree, 21);
-	tree = insert(tree, 30);
-	tree = insert(tree,  2);
-	tree = insert(tree,  7);
-	tree = insert(tree, 11);
-	show_tree(tree, 0, 0);
-
-	//tree = insert(tree, 15);
-	tree = insert(tree,  8);
-	show_tree(tree, 0, 0);
-#endif
-
-#if 0
-	tree = insert(tree, 2);
-	tree = insert(tree, 1);
-	tree = insert(tree, 4);
-	tree = insert(tree, 3);
-	tree = insert(tree, 5);
-	show_tree(tree, 0, 0);
-
-	tree = delete(tree, 1);
-	show_tree(tree, 0, 0);
-#endif
-
-#if 0
-	tree = insert(tree,  6);
-	tree = insert(tree,  2);
-	tree = insert(tree,  9);
-	tree = insert(tree,  1);
-	tree = insert(tree,  4);
-	tree = insert(tree,  8);
-	tree = insert(tree,  'B');
-	tree = insert(tree,  3);
-	tree = insert(tree,  5);
-	tree = insert(tree,  7);
-	tree = insert(tree,  'A');
-	tree = insert(tree,  'C');
-	tree = insert(tree,  'D');
-	show_tree(tree, 0, 0);
-
-	tree = delete(tree, 1);
-	show_tree(tree, 0, 0);
-#endif
-
-
-#if 0
-	tree = insert(tree,  5);
-	tree = insert(tree,  2);
-	tree = insert(tree,  8);
-	tree = insert(tree,  1);
-	tree = insert(tree,  3);
-	tree = insert(tree,  7);
-	tree = insert(tree,  'A');
-	tree = insert(tree,  4);
-	tree = insert(tree,  6);
-	tree = insert(tree,  9);
-	tree = insert(tree,  'B');
-	tree = insert(tree,  'C');
-	show_tree(tree, 0, 0);
-
-	tree = delete(tree, 1);
-	show_tree(tree, 0, 0);
-#endif
-
-
-#if 0
-	tree = insert(tree,  5);
-	tree = insert(tree,  3);
-	tree = insert(tree,  8);
-	tree = insert(tree,  2);
-	tree = insert(tree,  4);
-	tree = insert(tree,  7);
-	tree = insert(tree, 10);
-	tree = insert(tree,  1);
-	tree = insert(tree,  6);
-	tree = insert(tree,  9);
-	tree = insert(tree, 11);
-
-	tree = delete(tree,  4);
-	tree = delete(tree,  8);
-	tree = delete(tree,  6);
-	tree = delete(tree,  5);
-	tree = delete(tree,  2);
-	tree = delete(tree,  1);
-	tree = delete(tree,  7);
-
-	show_tree(tree, 0, 0);
-#endif
-
-	struct tree_node *tree = NULL;
-
-	srand(time(NULL));
-	for ( int i = 0; i != 300000; ++i )
-		tree = insert(tree, rand());
-
-	//show_tree(tree, 0, 0);
-
-	return EXIT_SUCCESS;
-}
-
-- 
cgit v1.3