CODEWITHSUNDEEP
c++data-structurestrie
Joe
Joe

Reputation: 111

C++ Trie Data Structure implementation with multiple parameters

I need to create a Trie data structure to store first name, last name and age. I will later need to implement a search for records using last name, or first and last names.

I know how to create a Trie, insert, delete and search. However, I don't know how to store multiple values appropriately (first name, last name and age).

Could someone please point me in the right direction?

#include <string>
#include <iostream>

using namespace std;
const int ALPHA_SIZE = 26;

struct Trie 
{
    struct Trie* child[ALPHA_SIZE];
    bool endofstring; //It is true if node represents end of word.
};

// Create new node
struct Trie* createNode(void) 
{
    struct Trie* tNode = new Trie;
    tNode->endofstring = false;
    for (int i = 0; i < ALPHA_SIZE; i++)
        tNode->child[i] = NULL;
    return tNode;
}

void insert(struct Trie* root, string key) 
{
    struct Trie* curr = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!curr->child[index])
            curr->child[index] = createNode();
        curr = curr->child[index];
    }
    curr->endofstring = true; //last node as leaf
}

bool search(struct Trie* root, string key) 
{ 
    struct Trie* curr = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!curr->child[index])
            return false;
        curr = curr->child[index];
    }
    return (curr != NULL && curr->endofstring);
}

bool isEmpty(Trie* root) //check if root has children 
{
    for (int i = 0; i < ALPHA_SIZE; i++)
        if (root->child[i])
            return false;
    return true;
}

Trie* deletion(Trie* root, string key, int depth = 0) 
{
    //If tree is empty return null.
    if (!root)
        return NULL;
    if (depth == key.size()) //If last character of key is being processed,
    {
        if (root->endofstring)
            root->endofstring = false; //then that node will be no more end of string after deleting it.
        if (isEmpty(root)) { //If given key is not prefix of any other string,
            delete (root);
            root = NULL;
        }
        return root;
    }
    //If key not last character,
    int index = key[depth] - 'a';
    root->child[index] =
        deletion(root->child[index], key, depth + 1); //Then recur for the child which will be obtained by using ASCII value.
    if (isEmpty(root) && root->endofstring == false) //If root does not have any child leftand it is not end of another word
    {
        delete (root);
        root = NULL;
    }
    return root;
}

int main() 
{   
    struct Trie* root = createNode();    

    insert(root, "joe");
    insert(root, "hanna");
    insert(root, "john");
    insert(root, "jane");

    search(root, "joe") ? cout << "Key is Found\n" :
        cout << "Key is not Found\n";

    search(root, "he") ? cout << "Key is Found\n" :
        cout << "Key is not Found\n";

    deletion(root, "john") ? cout << "Key is deleted\n" :
        cout << "Key is not Deleted\n";    

    return 0;
}

Upvotes: 0

Views: 386

Answers (1)

Lajos Arpad
Lajos Arpad

Reputation: 76464

It depends on what you need to search by. If you need to search by all elements, then you could use a format of

<FIRST NAME>;<LAST NAME>;<AGE>

Example: John;Doe;16

and use this as the key.

If you need to store additional data, like height, then you could add it to your struct Trie.

Upvotes: 0

Related Questions