Last active
November 7, 2015 01:07
-
-
Save beoliver/963ae6ac7248c89a4860 to your computer and use it in GitHub Desktop.
basic trie
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// tries.c | |
// chitchat | |
// | |
// Created by Ben Oliver on 06/11/15. | |
// Copyright © 2015 Ben Oliver. All rights reserved. | |
// | |
// assume that we allow 8 char sequences from an alphabet of 26 characters | |
// there are 26 ^ 8 possible sequences 208,827,064,576 | |
// if a trie had 208,827,064,576 entries | |
// the worst case lookup would be (26 * 8) + 1 = 209 | |
// average case (13 * 8) + 1 = 105 | |
// best case 8 + 1 = 9 | |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <assert.h> | |
#include "tries.h" | |
typedef struct ascii_trie_s { | |
char key; | |
int val; | |
unsigned short weight; | |
struct ascii_trie_s* child; | |
struct ascii_trie_s* next; | |
} ascii_trie ; | |
void free_ascii_trie(ascii_trie* node) { | |
if (node != NULL) { | |
free_ascii_trie(node->next); | |
free_ascii_trie(node->child); | |
free(node); | |
} | |
} | |
void print_weights(ascii_trie* node) { | |
if (node != NULL) { | |
printf("node: %c weight: %d\n", node->key, node->weight); | |
print_weights(node->next); | |
print_weights(node->child); | |
} | |
} | |
static ascii_trie* unsafe_trie_insert(char* key, int val, ascii_trie* node) { | |
// element must not allready exist in trie | |
while (1) { | |
// move right untill we find a match OR reach the end of the row | |
while ((*key != node->key) && (node->next != NULL)) { | |
node = node->next; | |
} | |
if (*key == node->key) { | |
node->weight += 1 ; | |
node = node->child ; | |
key = key+1 ; | |
} else { | |
node->next = malloc(sizeof(ascii_trie)); | |
node = node->next; | |
node->weight = 1; | |
node->key = *key; | |
node->next = NULL; | |
node->child = NULL; | |
while (*key != '\0') { | |
key = key+1; | |
node->child = malloc(sizeof(ascii_trie)); | |
node = node->child; | |
node->weight = 1; | |
node->key = *key; | |
node->next = NULL; | |
node->child = NULL; | |
} | |
node->weight = 0; | |
node->val = val; | |
return node; | |
} | |
} | |
} | |
static void unsafe_trie_delete(char* key, ascii_trie* node, ascii_trie* parent) { | |
ascii_trie* prev = NULL; | |
while ((node->key != *key) && (node->next != NULL)) { | |
prev = node; | |
node = node->next; | |
} | |
// we have now found the node that we need to use | |
if (node->weight < 2) { | |
if (prev == NULL) { | |
assert(parent != NULL); | |
parent->child = node->next; | |
} else { | |
prev->next = node->next; | |
} | |
// only one string uses this node | |
// thus only one string uses the children of the node | |
// use < 2 as we might allready be at the terminal node | |
// which has weight 0 | |
// remember that we might not be at the end of a row | |
// so we use prev->next to join the previous node with node->next | |
// which is either a node or NULL | |
free_ascii_trie(node->child); | |
free(node); | |
} else { | |
// node weight is > 1 | |
node->weight--; | |
unsafe_trie_delete(key+1, node->child, node); | |
} | |
} | |
ascii_trie* ascii_trie_lookup(char* key, int* valp, ascii_trie* node) { | |
while (1) { | |
while ((*key != node->key) && (node->next != NULL)) { | |
node = node->next; | |
} | |
if (*key != node->key) { | |
return NULL; | |
} | |
if (*key == 0x00) { | |
*valp = node->val; | |
return node; | |
} | |
key = key+1; | |
node = node->child; | |
} | |
} | |
int main(int argc, char** argv) { | |
printf("%lu\n", sizeof(ascii_trie)); | |
ascii_trie* root = malloc(sizeof(ascii_trie)); | |
root->weight = 0; | |
root->key = 0x00; | |
root->child = NULL; | |
root->next = NULL; | |
char* ben = "ben"; | |
char* benjamin = "benjamin"; | |
char* cat = "cat"; | |
char* dog = "dog"; | |
unsafe_trie_insert(ben, 10, root); | |
unsafe_trie_insert(benjamin, 20, root); | |
unsafe_trie_insert(cat, 30, root); | |
unsafe_trie_insert(dog, 40, root); | |
print_weights(root); | |
int val; | |
if (ascii_trie_lookup(ben, &val, root) != NULL) { | |
printf("%s exists with key: %d\n", ben, val); | |
} else { | |
printf("%s does not exist\n", ben); | |
} | |
printf("deleting: %s\n", ben); | |
unsafe_trie_delete(ben, root, NULL); | |
if (ascii_trie_lookup(ben, &val, root) != NULL) { | |
printf("%s exists with key: %d\n", ben, val); | |
} else { | |
printf("%s does not exist\n", ben); | |
} | |
print_weights(root); | |
free_ascii_trie(root); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment