initial commit: an AVL tree

1 files changed, 131 insertions, 0 deletions

diff --git a/strbst.c b/strbst.c
new file mode 100644
index 0000000..e4494ab
--- /dev/null
+++ b/strbst.c
@@ -0,0 +1,131 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+#include <stdio.h>
+
+#include "strbst.h"
+#define max(a,b) ((a > b) ? a : b)
+#define min(a,b) ((a < b) ? a : b)
+
+typedef char height;
+
+typedef struct strbstnode{
+    char* ind;
+    void* data;
+    struct strbstnode* left;
+    struct strbstnode* right;
+    int ht;
+} strbstnode;
+
+strbst* newbst(void) {
+    strbst* out = malloc(sizeof(strbst));
+    out->head = NULL;
+    return out;
+}
+
+static strbstnode* newbstnode(char* ind, void* data) { // does not ins
+    strbstnode* out = malloc(sizeof(strbstnode));
+    out->ind = ind;
+    out->data = data;
+    out->left = out->right = NULL;
+    out->ht = 0;
+    return out;
+}
+
+int getht(strbstnode* node) {
+    return node ? node->ht : -1;
+}
+
+static void rightrot(strbstnode** bst);
+static void leftrot(strbstnode** bst);
+
+int insnode(strbstnode** bst, strbstnode* new) { // Find good parent
+    if (!*bst){
+        *bst = new;
+        return 0;
+    }
+    strbstnode** node;
+    if (strcmp(new->ind, (*bst)->ind) < 0)
+        node = &((*bst)->left);
+    else
+        node = &((*bst)->right);
+    int heavy = insnode( node, new );
+    int diff = getht((*bst)->right) - getht((*bst)->left);
+    if (diff > 1) {
+        if (heavy == -1)
+            rightrot(node);
+        leftrot(bst);
+    } else if (diff < -1){
+        if (heavy == 1)
+            leftrot(node);
+        rightrot(bst);
+    }
+    (*bst)->ht = max( getht((*bst)->left), getht((*bst)->right) )+1;
+    return ( getht((*bst)->right) - getht((*bst)->left) );
+}
+
+void insbst(strbst* bst, char* ind, void* data) {
+    insnode(&(bst->head), newbstnode(ind, data)); // allows recursion
+}
+
+void* querynode(strbstnode* node, char* ind){
+    int cmp = strcmp(ind, node->ind);
+    if (cmp > 0)
+        return querynode(node->right, ind);
+    else if (cmp < 0)
+        return querynode(node->left, ind);
+    else if (node)
+        return node->data;
+    else
+        return NULL;
+}
+
+void* querybst(strbst* bst, char* ind) {
+    return querynode(bst->head, ind);
+}
+
+void rightrot(strbstnode** bst) {
+/*
+    a         b
+   / \       / \
+  b   e =>  c   a
+ / \           / \
+c   d         d   e
+*/
+    strbstnode* flip = (*bst)->left->right; // flip = d
+    (*bst)->left->right = *bst; // position of d = a
+    *bst = (*bst)->left; // tip = b
+    (*bst)->right->left = flip;
+}
+
+void leftrot(strbstnode** bst) {
+/*
+  a            b
+ / \          / \
+e   b   =>   a   c
+   / \      / \
+  d   c    e   d
+*/
+    strbstnode* flip = (*bst)->right->left; // flip = d
+    (*bst)->right->left = *bst; // position of d = a
+    *bst = (*bst)->right; // tip = b
+    (*bst)->left->right = flip;
+}
+
+void printnode(strbstnode* node) {
+    if (!node) return;
+    if (node->right)
+        printnode(node->right);
+    if (node->left)
+        printnode(node->left);
+    printf("node %s", node->ind);
+    if (node->right)
+        printf(" (right) %s",node->right->ind);
+    if (node->left)
+        printf(" (left) %s", node->left->ind);
+    printf("\n");
+}
+
+void printbst(strbst* bst) {
+    printnode(bst->head);
+}