diff options
Diffstat (limited to 'strbst.c')
-rw-r--r-- | strbst.c | 131 |
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); +} |