I've been working on a Trie program for practice and i'm running into some logic/coding issues when it comes to trying to create a method that removes or destroys words that are currently in the trie:
#include "trie.h"
/**************************************************************************/
/* Helper Functions
* trie_node_t * trie_new( void );
* Allocates memory for a new trie node
* Returns NULL if memory allocation was not possible or
* a memory address to a trie_node in the heap
/**************************************************************************/
trie_node_t * trie_new( void ){
trie_node_t * tmp = NULL;
int i;
if ( ( tmp = ( trie_node_t * ) malloc ( sizeof( trie_node_t ) ) ) == NULL )
return NULL;
for( i = 0; i < ALPHA_SIZE; i++ ) {
tmp->child[ i ] = NULL;
tmp->end = 1;
}
return tmp;
}
/**************************************************************************/
/* Functions functions
* int trie_size ( trie_node_t * root );
* Returns the number of words in the trie
* int trie_contains ( trie_node_t * root, char word[ ] );
* Returns 1 if a the word is in the trie
* 0 otherwise
* int trie_insert ( trie_node_t ** rootRef, char word[ ] );
* Returns 1 if the word is inserted in the trie
* 0 otherwise
* int trie_remove ( trie_node_t ** rootRef, char word[ ] );
* Returns 1 if the word is removed from the trie
* 0 otherwise
* int trie_destroy ( trie_node_t ** Tref );
* Returns 1 if the trie and all its node are destroyed
**************************************************************************/
int trie_size ( trie_node_t * root ) {
int i = 0;
int count = 0;
trie_node_t *temp = root; //Creates a temp variable (Because its being modified)
//if the reference does not exist(no more children)
if (temp == NULL){
return EXIT_FAILURE;
}
//loops through the child array
for (i = 0; i < ALPHA_SIZE; i++){
//if the reference to next child is not null
if(temp->child[i] != NULL){
//and the end character is '/0' (or not)
if(temp->child[i]->end == '/0'){
count += 1;
}
//add the return of trie_size to count, then run through the method again at the lower level.
count += trie_size(temp->child[i]);
}
}
return count;
}
/**************************************************************************/
int trie_contains ( trie_node_t * root, char word[ ] ){
trie_node_t *temp = root; //Create a temp variable, can't use the default root. (just a location).
int i = 0;
int length = strlen(word); //finds the length of array
int index = 0;
if (temp == NULL){
return EXIT_FAILURE;
}
if(!valid_word(word)){
return 0;
}
for (i = 0; i < length; i++){
index = charToInt(tlower(word[i]));
if (!temp->child[index]){
return 0;
}
temp = temp->child[index];
}
if (temp->end != '/0'){ //Checks if the end character at the last index is '/0' if it is not, it is not a word. Return 0 (not found)
return 0;
}
return 1;
}
/**************************************************************************/
int trie_insert ( trie_node_t ** rootRef, char word[ ] ){
trie_node_t *temp = *rootRef; //Create a temp variable, can't use the default rootRef. (just a location).
int i = 0;
int length = strlen(word); //finds the length of array
int index = 0;
if (temp == NULL){ //checks that the reference is not null
return EXIT_FAILURE;
}
if (!valid_word(word)){//checks if word is valid.
return 0;
}
for (i = 0; i < length; i++){
if (word[i] == '/0'){
index = 26;
} else if (word[i] >= 'A' || word[i] <= 'Z'){
index = charToInt(tolower(word[i])); //turns the word[i] into a usable integer.
}
else {
return EXIT_FAILURE;
}
if (!temp->child[index]){ //if there is not a child reference.
temp->child[index] = trie_new(); //create one.
}
temp = temp->child[index]; //move down to next level (next child)
}
temp->end = '\0';
return 1;
}
/**************************************************************************
* I'm pretty sure the majority of this method is incorrect, this was just an attempt I had. From what I understand I have to do is this:
* (1) Find the last character in the word (Found with the '/0' end char) and as long as there are no nodes connected at a lower level free the memory.
* (2) Move up (recursion is probably the easiest way to do this, but I haven't been able to figure out how) and check again.
* (3) Continue until the first letter of the word is reached, then exit.
* My question is how do I check to see if another node is connected? Also what would be the format of the recursive call?
**************************************************************************/
void trie_remove ( trie_node_t ** rootRef, char word[ ] ){
trie_node_t *temp = *rootRef;
int i = 0;
int index = 0;
int length = strlen(word);
if (temp == NULL){
return;
}
if (!valid_word(word)){
return;
}
//Code is incomplete, just an attempt.
for (i = 0; i < length; i++){
index = charToInt(tolower(word[i])); //not sure if this is necessary.
if (temp->child[i]->end == '/0'){
free(temp->child[i]);
}
}
return;
}
/**************************************************************************/
int trie_destroy ( trie_node_t ** rootRef ){
//issues with logic here, not exactly sure how to do this.
return 1;
}
/**************************************************************************/
int trie_init(trie_node_t **rootRef){
if ( *rootRef == NULL) {
*rootRef = trie_new();
}
return 1;
}
/**************************************************************************/
int valid_word (char word[]){
int length = 0;
int i = 0;
for (i = 0; i < length; i++){
if(charToInt(word[i]) > 26 || charToInt(word[i]) < 0){
return 0;
}
}
return 1;
}
/**************************************************************************/
int charToInt(char c){
return (int)c-(int)'a';
}
Trie.h: (Important stuff anyways) ALPHA_SIZE is 27.
typedef struct trie_node {
char end;
struct trie_node *child[ ALPHA_SIZE ]; //reference to trie node.
}trie_node_t;
I hope I formatted this question correctly, and I have looked on the site for possible solutions already but have yet to find any. If anyone can help me check my logic/ assist me in the coding of these methods that would be amazing. I don't just want the code I want to learn why it works!
Thanks in advance.
for Remove, you need to remove free'd pointers from the trie:
for (i = 0; i < length; i++){
index = charToInt(tolower(word[i])); //not sure if this is necessary.
if (temp->child[i]->end == '/0'){
free(temp->child[i]);
temp->child[i]=0; // lets not point to free'd elements
}
}
For destroy - try recursion, roughly:
for (int i=ALPHA_MIN; i < ALPHA_MAX; ++i)
{
if (rootRef->child[i])
{
trie_destroy(rootRef->child[i]);
}
}
free (rootRef);