From ff3374a099f0f91c1029a025c705fdc0cb921247 Mon Sep 17 00:00:00 2001 From: Julian T Date: Mon, 7 Oct 2019 12:33:36 +0200 Subject: Added binary tree assignment --- sem1/algo/mm6/Makefile | 31 ++++++++++ sem1/algo/mm6/main.c | 37 ++++++++++++ sem1/algo/mm6/tree.c | 155 +++++++++++++++++++++++++++++++++++++++++++++++++ sem1/algo/mm6/tree.h | 31 ++++++++++ 4 files changed, 254 insertions(+) create mode 100644 sem1/algo/mm6/Makefile create mode 100644 sem1/algo/mm6/main.c create mode 100644 sem1/algo/mm6/tree.c create mode 100644 sem1/algo/mm6/tree.h 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 + +#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 +#include +#include + +#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 + +#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 -- cgit v1.2.3