Added binary tree assignment

4 files changed, 254 insertions, 0 deletions

diff --git a/sem1/algo/mm6/Makefile b/sem1/algo/mm6/Makefile
new file mode 100644
index 0000000..c157cef
--- /dev/null
+++ b/sem1/algo/mm6/Makefile
@@ -0,0 +1,31 @@
+CC = gcc
+# Enable gdb and pull include files from current dir
+CFLAGS = -ggdb -I.
+LDFLAGS = 
+
+BINARY = main
+BUILD_DIR = build
+
+# Capture c files 
+c_files = $(wildcard *.c)
+
+# Convert c names to corrosponding o names
+OBJ = $(patsubst %.c, $(BUILD_DIR)/%.o, $(c_files))
+
+# $@ is the %.o file and $^ is the %.c file
+$(BUILD_DIR)/%.o: %.c
+	mkdir -p $(dir $@)
+	$(CC) -c -o $@ $^ $(CFLAGS)
+
+# $@ becomes left part thus linked
+$(BINARY): $(OBJ)
+	$(CC) -o $@ $^ $(LDFLAGS)
+
+.PHONY: clean run
+
+run: $(BINARY)
+	./$(BINARY)
+
+clean:
+	rm -f $(OBJ) $(BINARY)
+	rmdir $(BUILD_DIR)
diff --git a/sem1/algo/mm6/main.c b/sem1/algo/mm6/main.c
new file mode 100644
index 0000000..abc8d02
--- /dev/null
+++ b/sem1/algo/mm6/main.c
@@ -0,0 +1,37 @@
+#include <stdio.h>
+
+#include "tree.h"
+
+int main() {
+	tree_t t;
+	t.root = 0;
+
+	node_t *a = tree_insert(&t, 1, "Hej");
+
+	node_t *b = tree_insert(&t, 3, "med");
+
+	tree_insert(&t, 11, "dig");
+	tree_insert(&t, 9, "dig");
+	tree_insert(&t, 12, "dig");
+
+	tree_insert(&t, 10, "hvordan");
+
+	tree_insert(&t, 8, "det");
+
+	tree_insert(&t, 4, "branch");
+
+	tree_insert(&t, 5, "2");
+
+
+	tree_insert(&t, 0, "Og den sidste");
+
+	tree_insert(&t, 2, "Cool nok");
+	tree_print(&t);
+
+	printf("%s\n", tree_search(&t, 10));
+	printf("%s\n", tree_search(&t, 11));
+	printf("%s\n", tree_search(&t, 1));
+	printf("%s\n", tree_search(&t, 0));
+	printf("%s\n", tree_search(&t, 99));
+
+}
diff --git a/sem1/algo/mm6/tree.c b/sem1/algo/mm6/tree.c
new file mode 100644
index 0000000..47378f3
--- /dev/null
+++ b/sem1/algo/mm6/tree.c
@@ -0,0 +1,155 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "tree.h"
+
+static node_t *create_node(unsigned int index, char *val) {
+	node_t *node = malloc( sizeof(node_t) );
+	memset(node, 0, sizeof(node_t));
+
+	node->value = val;
+	node->index = index;
+}
+
+/* Comments are based of dir = CHILD_LEFT */
+void node_rotate(tree_t *tree, node_t *x, int dir) {
+	/* Node below which we should rotate with */
+	node_t *y = x->children[!dir];
+
+	/* Move y's left to x's right */
+	x->children[!dir] = y->children[dir];
+
+	/* Update parent */
+	if( y->children[dir] ) {
+		y->children[dir]->p = x;
+	}
+
+	/* Switch around x and y */
+	y->p = x->p;
+
+	/* Check if y is new root if not update x's parent */
+	if( !y->p ) {
+		tree->root = y;
+	} else if( x == x->p->children[CHILD_LEFT]) {
+		x->p->children[CHILD_LEFT] = y;
+	} else {
+		x->p->children[CHILD_RIGHT] = y;
+	}
+	
+	/* Update y's ref */
+	y->children[dir] = x;
+	x->p = y;
+
+}
+
+static void insert_fixup(tree_t *tree, node_t *z) {
+	while( z->p && z->p->black == false ) {
+		/* Set the right direction */
+		int dir = (z->p == z->p->p->children[CHILD_LEFT]) ? CHILD_RIGHT : CHILD_LEFT;
+
+		/* Get uncle */
+		node_t *y = z->p->p->children[dir];
+		if( y && !y->black ) {
+			/* Case 1 */
+			z->p->black = true;
+			y->black = true;
+			z->p->p->black = false;
+
+			z = z->p->p;
+		} else if( z == z->p->children[dir] ) {
+			/* Case 2 */
+			z = z->p;
+			node_rotate(tree, z, !dir);
+		} else {
+			/* Case 3 */
+			z->p->black = true;
+			z->p->p->black = false;
+			node_rotate(tree, z->p->p, dir);
+		}
+	}
+
+	tree->root->black = true;
+
+}
+
+static node_t *insert_recur(node_t *node, unsigned int index, char *val) {
+	int dir = node->index < index ? CHILD_RIGHT : CHILD_LEFT;
+
+	if( node->children[dir] ) {
+		return insert_recur(node->children[dir], index, val);
+	}
+
+	/* Found stop */
+	node_t *new = create_node(index, val);
+	new->p = node;
+	node->children[dir] = new;
+
+	return new;
+}
+
+node_t *tree_insert_pleb(tree_t *tree, unsigned int index, char *val) {
+	if( !tree->root ) {
+		tree->root = create_node(index, val);
+		return tree->root;
+	}
+
+	return insert_recur(tree->root, index, val); 
+}
+
+node_t *tree_insert(tree_t *tree, unsigned int index, char *val) {
+	if( !tree->root ) {
+		tree->root = create_node(index, val);
+		tree->root->black = true;
+		return tree->root;
+	}
+
+	node_t *new = insert_recur(tree->root, index, val); 
+	insert_fixup(tree, new);
+
+	return new;
+}
+
+char *tree_search(tree_t *tree, unsigned int index) {
+	node_t *z = tree->root;
+	while( z->index != index ) {
+		z = z->children[z->index < index ? CHILD_RIGHT : CHILD_LEFT];
+		if( !z ) {
+			return NULL;
+		}
+	}
+
+	return z->value;
+}
+
+static inline void print_indent(int num) {
+	for( int i = 0; i < num; i++ ) {
+		printf("  ");
+	}
+}
+
+static inline void print_text(node_t *node, bool bold) {
+	if( bold ) {
+		printf("\033[1m%d\033[22m\n", node->index);
+	} else {
+		printf("%d\n", node->index);
+	}
+
+}
+
+static void print_recur(node_t *node, int ident) {
+	if( !node ) {
+		return;
+	}
+	print_recur(node->children[CHILD_RIGHT], ident+1);
+	
+	print_indent(ident);	
+	print_text(node, node->black);
+
+	print_recur(node->children[CHILD_LEFT], ident+1);
+}
+
+void tree_print(tree_t *tree) {
+	print_recur(tree->root, 0);	
+}
+
diff --git a/sem1/algo/mm6/tree.h b/sem1/algo/mm6/tree.h
new file mode 100644
index 0000000..0d1c5c6
--- /dev/null
+++ b/sem1/algo/mm6/tree.h
@@ -0,0 +1,31 @@
+#ifndef TREE_H
+#define TREE_H
+
+#include <stdbool.h>
+
+#define CHILD_LEFT 0
+#define CHILD_RIGHT 1
+
+typedef struct node_struct{
+	struct node_struct *p;
+	struct node_struct *children[2];
+	unsigned int index;
+	bool black;
+	char *value;
+} node_t;
+
+typedef struct {
+	node_t *root;
+} tree_t;
+
+void tree_print(tree_t *tree);
+
+node_t *tree_insert(tree_t *tree, unsigned int index, char *val);
+node_t *tree_insert_pleb(tree_t *tree, unsigned int index, char *val);
+
+void node_rotate(tree_t *tree, node_t *x, int dir);
+
+char *tree_search(tree_t *tree, unsigned int index);
+
+
+#endif