tries

[nitin1]

#include<iostream>
#include <cstdio>
 #include<string>

 using namespace std;
typedef struct node node;

struct node
{
       int value;
       node * child[26];

}*root;


node * newnode()
{
     node * nn;

     nn=(node*)malloc(sizeof(node));

     nn->value=0;

     for(int i=0;i<26;i++)
     {
            nn->child[i]=NULL; 
     }

     return nn;
}

bool insert(string s)
{
     node * temp=root;
     bool xx=false;

     for(int level=0;level<s.length();level++)
     {
             int index=s[level]-'0';

             temp=temp->child[index];


             if(temp==NULL)
             {
                           cout<<"here"<<endl;
                        temp=newnode();
                        xx=true;                 
             }

             if(temp->value==1)
             {
                         return false;      
             }
     } 

     temp->value=1;

     if(xx==true)
     return true;
     else
     return false;
}

int main()
{
    root=newnode();
    string s;
    int n;
    int t;
    bool p=true;

    cin>>t;

    while(t--)
    {
           root=NULL;

           root=newnode();

           cin>>n;
           p=true;   

          while(n--)
          {    
              cin>>s;

              if(p==true)
              {
                  bool z=insert(s);

                  if(z==false)
                  {
                         p=false;     
                  }
              }

              if(root->child[9]==NULL)
              cout<<"nnnnn"<<endl;

          }

          if(p==false)
          {
                      cout<<"NO"<<endl;
          }
          else
          cout<<"YES"<<endl;    

    }


    return 0;
}

this is my code for tries. i am allocating memory to each node in the insert function. but when i check that it is value of the inserted node is null, then it says yes. problem is in insert function. i am calling this from main(). when i have inserted one string, then it should insert it again. please see whats can be the solution. thanks. i am entering "911" 2-3 times. and it is saying that root->child[9] is till NULL, which should not be there. thanks

[deceptikon]

The problem is on line 47, where you overwrite temp but temp was already NULL, so the tree doesn't reflect the change. I'm also concerned that you may be somewhat confused as to how a trie works. Consider the following example:

#include <limits>
#include <memory>
#include <string>
#include <vector>

template <typename CharT>
class trie {
    struct node {
        std::vector<std::shared_ptr<node>> link;
        CharT key;
    public:
        node(CharT key): 
            link(std::numeric_limits<CharT>::max() + 1), 
            key(key)
        { }
    };

    std::shared_ptr<node> root;
public:
    trie(): root(nullptr) {}

    /*
        @description:
            Adds a word path to the trie.
    */
    void add(const std::basic_string<CharT>& s)
    {
        if (root.get() == nullptr) {
            root.reset(new node(CharT()));
        }

        auto it = root;

        for (auto c : s) {
            if (it->link[c] == nullptr) {
                it->link[c].reset(new node(c));
            }

            it = it->link[c];
        }
    }

    /*
        @description:
            Returns the first index in the string s that doesn't match 
            a path in the trie, or npos for a complete match.
    */
    typename std::basic_string<CharT>::size_type match(const std::basic_string<CharT>& s)
    {
        auto end = s.begin();
        auto it = root;

        while (end != s.end() && it->link[*end] != nullptr) {
            it = it->link[*end++];
        }

        if (end == s.end()) {
            return std::basic_string<CharT>::npos;
        }

        return end - s.begin();
    }
};

Note in the add() member function how I carefully checked for a null root and then make sure to only access child nodes for assignment. This is one method for ensuring that changes to the data structure are propagated back to the top.

[nitin1]

hats off !! out of world code!! 101% readable and understadable in one go. sir, yes! i come to know about my mistake now . thanks. i know i am doing a very stupid mistake, but still i wana ask. when i am on root which has 26 pointers and all NULL. then i have made temp to go to one of that 26 pointers. okay? then after allocating memory to it, why not it is made part of the complete tree (because that child pointer is also part of tree). thanks alot.

[deceptikon]

then after allocating memory to it, why not it is made part of the complete tree

Because it's too late at that point. Once temp points to NULL, it's no longer related to the tree.

[nitin1]

sir, can you tell me that how can i optimize my code so as to reduce the memory consumption ? because in my ocde, i am using 26 pointers on each node which is very costly if string is too large. can you tell me any way to optimize it further ? thanks .

[deceptikon]

You can use a dynamic array instead of an array. This is a classic trade off of speed versus space, because the dynamic array will be drastically slower while the static array will take up more overall space for your average case (assuming the average case is a half full array of links).

[deceptikon]

On a side note, I figured that trie code was useful enough to post as a code snippet. So I updated it a bit and created one.