AfanasevGad7

commit 761eeba0b7c121bc8f57706770446634a4a4599b
parent 0ca2f4cc4e6ebcc751ee89eda6083548afe12832
Author: Plat <plat@stellar-nexus.ru>
Date:   Fri,  7 Nov 2025 09:33:27 +0000

Major overhaul to AVL

Diffstat:
M
Makefile
 | 
2
+-
A
avl.c
 | 
189
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 190 insertions(+), 1 deletion(-)
diff --git a/Makefile b/Makefile
@@ -1,5 +1,5 @@
 include config.mk
-BIN = fib rb
+BIN = avl fib rb
 LIBS = ${wildcard libutil/*.c}
 OBJS = ${LIBS:.c=.o}
 
diff --git a/avl.c b/avl.c
@@ -0,0 +1,189 @@
+#include <iostream>
+
+
+struct Node {
+	int val;
+	Node* left;
+	Node* right;
+};
+
+
+
+Node *
+init(int val)
+{
+	Node *n = malloc(sizeof(Node));
+	if (n == NULL)
+		return NULL;
+
+	n->val = val;
+	n->left = NULL;
+	n->right = NULL;
+
+	return n;
+}
+
+
+Node *
+add(Node *root, int val)
+{
+	if (!root)
+		return init(val);
+
+	if (val < root->val)
+		root->left = add(val, root->left);
+	else if (val > root->val)
+		root->right = add(val, root->right);
+	else
+		return root;
+
+	return balance(root);
+}
+
+int
+get_height(Node *root)
+{
+	int r, l;
+
+	if (!root)
+		return 0;
+
+	l = get_height(root->left) + 1;
+	r = get_height(root->right) + 1;
+
+	if (l > r) {
+		return l;
+	}
+
+	return r;
+}
+
+
+inline int
+get_balance_factor(Node *root)
+{
+	if (!root)
+		return 0;
+
+	return get_height(root->left) - get_height(root->right);
+}
+
+
+Node *
+right_turn(Node *root)
+{
+	if (!root || !root->left)
+		return root;
+
+	Node *buf = root->left;
+	root->left = buf->right;
+	buf->right = root;
+	return buf;
+}
+
+
+Node *
+left_turn(Node *root)
+{
+	if (!root || !root->right)
+		return root;
+
+	Node *buf = root->right;
+	root->right = buf->left;
+	buf->left = root;
+	return buf;
+}
+
+
+Node *
+balance(Node *root)
+{
+	if (!root)
+		return NULL;
+
+	int bf = get_balance_factor(root);
+
+
+	if (bf > 1) {
+		if (get_balance_factor(root->left) < 0)
+			root->left = left_turn(root->left);
+		return right_turn(root);
+	}
+
+	if (bf < -1) {
+		if (get_balance_factor(root->right) > 0)
+			root->right = right_turn(root->right);
+		return left_turn(root);
+	}
+
+	return root;
+}
+
+
+Node *
+search(Node *root, int val)
+{
+	steps++;
+	if (root->val == val) return root;
+
+	if (root->val > val) return search(root->left, val);
+
+	return search(root->right, val);
+}
+
+static inline void
+usage(void)
+{
+	eprintf("usage: %s [filename]\n", argv0);
+}
+
+int
+main(int argc, char *argv[])
+{
+	argv0 = argv[0];
+	if (argc > 2)
+		usage();
+	const char *filename;
+	if (argc == 2)
+		filename = argv[1];
+	else
+		filename = FILENAME;
+	
+	FILE *file;
+	if (!(file = fopen(filename, "r")))
+		eprintf("fopen %s:", filename);
+	
+	int arr[TESTNUMBER+1], ch;
+	char w[64];
+	int len = 0, wi = 0;
+	do {
+		ch = fgetc(file);
+		if (!isspace(ch) && ch != EOF) {
+			w[wi++] = ch;
+		} else if (wi > 0) {
+			w[wi] = '\0';
+			arr[len++] = estrtonum(w, 0, INT_MAX);
+			wi = 0;
+		}
+	} while (ch != EOF && len <= TESTNUMBER);
+	efshut(file, filename);
+	if (len < TESTNUMBER)
+		eprintf("Array too small\n");
+	if (len > TESTNUMBER)
+		weprintf("Array too big - using only the first %d elements\n", TESTNUMBER);
+
+	Node *root = NULL;
+
+	for (int i = 0; i < TESTNUMBER; ++i) {
+		root = add(root, arr[i]);
+		SET_COLOR(root, BLACK);
+	}
+
+	volatile uintptr_t checksum = 0; /* to avoid optimization */
+	clock_t start_time, end_time;
+	start_time = clock();
+	for (int i = 0; i < TESTNUMBER; ++i)
+		checksum = (uintptr_t)search(root, arr[i]);
+	end_time = clock();
+	printf("%f\n", (double)(end_time-start_time)/CLOCKS_PER_SEC);
+}