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

---
 src/avl.c | 471 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 471 insertions(+)
 create mode 100644 src/avl.c

(limited to 'src/avl.c')

diff --git a/src/avl.c b/src/avl.c
new file mode 100644
index 0000000..874cc6c
--- /dev/null
+++ b/src/avl.c
@@ -0,0 +1,471 @@
+// AVL Tree
+#include <assert.h>
+#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