TRIES Implementation

Question

I have recently learned Tries algorithm and am struggling hard to implement it using linked list. I have done the array implementation and is working fine.

I am expecting the Tree for the words (bear,bed, bull,bid,buy,sell,stock,stop) to be created like this:

 /
 |              
 b--------------------------------->s
 |                                  |
 e------->i--->u                    e---->t
 |        |    |                    |     |
 a--->d   d    l--->y               l     o
 |             |                    |     |
 r             l                    l     c--->p
                                          |
                                          k

But I realize that my insert function is not doing the same and hence when I try to find these words I am not able to find them.

For example: when i search for (bear,bull,buy,sell,stop) the result is FOUND but when i search for (bed,bid,stock) the result is NOT FOUND. The expected result for all the inserted strings should have been FOUND.

I am posting my code below. Looking forward to some help and not exactly the code but just a pointer to where I m going wrong or what I am missing.

/* I am trying to add few words in the tree using Tries Algorithm and 
 * then trying to find them */

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    char info;
    struct node *nextSibling;
    struct node *child;
    int count;
} node;

struct node* insert(struct node *ptr,char *string);

typedef enum Result {FALSE,TRUE} SEARCH;

SEARCH find(struct node *ptr,char *string);

void main()
{
    struct node *headptr = NULL;
    char string[256];

    headptr = insert(headptr,"bear");
    headptr = insert(headptr,"bed");
    headptr = insert(headptr,"bid");
    headptr = insert(headptr,"bull");
    headptr = insert(headptr,"buy");
    headptr = insert(headptr,"sell");
    headptr = insert(headptr,"stock");
    headptr = insert(headptr,"stop");

    printf("bear bed bid bull buy sell stock stop\n");
    printf("Enter a string to search:\n");
    scanf("%s",string);

    if(find(headptr,string)){
        printf("Found\n");
    }else{
        printf("Not Found\n");
    }

}

struct node* insert(struct node *ptr,char *string){

    struct node *temp = NULL;   
    struct node *p    = NULL;   
    char   info       = '\0';

    if(!string[0])
        return NULL;

    info = string[0];
    string++;

    temp = (struct node *)malloc(sizeof(struct node));
    temp->info    = info;
    temp->nextSibling = NULL;
    temp->child       = NULL;
    temp->count       = 1;

    if((ptr == NULL)||(ptr->info > info)){
        temp->nextSibling = ptr;
        ptr = temp;

        ptr->child = insert(ptr->child,string);
        return ptr;
    }
    else{
        p = ptr;
        while(p->nextSibling){
            if(p->info == info){
                p->count += 1;
                free(temp);
                p->child = insert(p->child,string);
                if ( ptr->nextSibling == p )
                    return ptr;
                else
                    return p;
            }

            if((p->nextSibling)->info > info){
                temp->nextSibling = p->nextSibling;
                p->nextSibling = temp;

                temp->child = insert(temp->child,string);
                if ( ptr->nextSibling == p )
                    return ptr;
                else
                    return p;
            }

            p = p->nextSibling;
        }

        if(!(p->nextSibling)){  
            if(p->info == info){
                p->count += 1;
                free(temp);
                temp = NULL;
                p->child = insert(p->child,string);
                if ( ptr->nextSibling == p )
                    return ptr;
                else
                    return p;
            }
            else{
                temp->nextSibling = p->nextSibling;
                p->nextSibling = temp;
                temp->child = insert(temp->child,string);
                if ( ptr->nextSibling == p )
                    return ptr;
                else
                    return p;
            }
        }
    }
}


SEARCH find(struct node *ptr,char *string){

    char info = '\0';
    struct node *p = NULL;
    SEARCH rc = FALSE;

    if(!string[0]){ 
        rc = TRUE;
        return rc;
    }

    info = string[0];
    string++;

    if(ptr == NULL){
        rc = FALSE;
    }
    else{
        p = ptr;
        while(p){
            if(p->info == info){
                rc =find(p->child,string);
                break;
            }
            else if(p->info > info){
                if (!string[0])
                    rc = FALSE;
                else
                    rc =find(p->child,string);  
                break;
            }
            else if ( p->info < info)
            {
                rc =find(p->child,string);
                break;
            }
            p = p->nextSibling;
        }
    }

    return rc;
}

Apologies for that..I am basically trying to add few words in the tree using Tries Algorithm without any compaction technique and then I try to find them. I think that I have understood the theory but just messing up in the implementation. — Albert, Dec 21 '15 at 20:11
What exactly is not working? Please try to give us an input, the desired output and what you get instead, see http://stackoverflow.com/help/how-to-ask. — terence hill, Dec 21 '15 at 20:46
char info = NULL is wrong (if you don't have a warning compile with -Wall). Should be char info = 0 or whatever NULL, is for pointers. See http://stackoverflow.com/questions/1296843/what-is-the-difference-between-null-0-and-0 — terence hill, Dec 21 '15 at 20:49
@terencehill thank you for your comment, I have corrected that and have added the problem description this time. — Albert, Dec 22 '15 at 07:28
[Trie explanation and C source code](http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/trie01.html) — houssam, Dec 22 '15 at 09:29
+1 Now it's much better! However you should also include what happen for a given input. You ask for a string at the beginning. If I want to try your code first thing I do is not looking inside it but just compile and test so it would be helpful to know what to input and which is your output and the desidered one. For example I guess that one possible input is bear. What's happen when you input bear and what you would like instead? — terence hill, Dec 22 '15 at 10:16

score 1 · Accepted Answer · answered Dec 28 '15 at 12:02

I think i was just messing up the return addresses in the insert function which was amounting to wrong result. Also I don't know what I was thinking while writing find function.

I am posting my working code here, but i m not very happy with this as I think that it can be made better.

Please comment on it :)

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
        char info;
        struct node *nextSibling;
        struct node *child;
        int count;
    } node;

struct node* insert(struct node *ptr,char *string);

void print(struct node *ptr);

typedef enum Result {FALSE,TRUE} SEARCH;

SEARCH find(struct node *ptr,char *string);

void main()
{
    struct node *headptr = NULL;
    char string[256];

    headptr = insert(headptr,"bear");
    headptr = insert(headptr,"bid");
    headptr = insert(headptr,"bed");
    headptr = insert(headptr,"bull");
    headptr = insert(headptr,"buy");
    headptr = insert(headptr,"sell");
    headptr = insert(headptr,"stock");
    headptr = insert(headptr,"stop");

    printf("bear bed bid bull buy sell stock stop\n");
    printf("Enter a string to search:\n");
    scanf("%s",string);

    if(find(headptr,string)){
        printf("Found\n");
    }else{
        printf("Not Found\n");
    }
}

struct node* insert(struct node *ptr,char *string){

    struct node *temp = NULL;   
    struct node *p    = NULL;   
    char   info       = '\0';

    if(!string[0])
    return NULL;

    info = string[0];
    string++;

    temp = (struct node *)malloc(sizeof(struct node));
    temp->info    = info;
    temp->nextSibling = NULL;
    temp->child       = NULL;
    temp->count       = 1;

    if((ptr == NULL)||(ptr->info > info)){ /*Inserting 1st node or first node greater than the new node*/
        temp->nextSibling = ptr;
        ptr = temp;

        temp->child = insert(temp->child,string);
        return ptr;
    }
    else{
        p = ptr;
        while(p->nextSibling){
            if(p->info == info){
                p->count += 1;
                free(temp);
                p->child = insert(p->child,string);
                return ptr;
            }

            if((p->nextSibling)->info > info){
                temp->nextSibling = p->nextSibling;
                p->nextSibling = temp;

                temp->child = insert(temp->child,string);
                return ptr;
            }

            p = p->nextSibling;
        }

        if(!(p->nextSibling)){  
            if(p->info == info){ /*1st node or last node equal to the new node*/
                p->count += 1;
                free(temp);
                temp = NULL;
                p->child = insert(p->child,string);
                    return ptr;
            }
            else{  /*New node is to be inserted at the end*/
                temp->nextSibling = p->nextSibling;
                p->nextSibling = temp;
                temp->child = insert(temp->child,string);
                        return ptr;
            }
        }
    }

}

SEARCH find(struct node *ptr,char *string){

    char info = '\0';
    struct node *p = NULL;
    SEARCH rc = FALSE;

    if(!string[0]){ /* End of string case */
        rc = TRUE;
        return rc;
    }

    if(ptr == NULL){
        rc = FALSE;
    }
    else{
        p = ptr;
        while(p){
            if(p->info == string[0]){/*Checking the first node for match*/
                rc = find(p->child,++string);
                return rc;
            }
            p = p->nextSibling;
        }
    }
    return rc;
}

TRIES Implementation

1 Answers1