StoneCold_'s blog

By StoneCold_, 4 years ago, In English,

Please can anyone provide a good implementation of trie using a 2D array instead of using recursion ?

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

let f be the matrix representation of your trie

let f[k] be the list of links for the k-th node

let f[k][x] = m, the node who represents the son of k-th node using x-th character, m = -1 is there is not a link.

int MAX = Max number of nodes
int CHARSET = alphabet size
int ROOT = 0
int sz = 1;

f[MAX][CHARSET]

void init() {
 fill(f, -1);
}

void insert(char [] s) {
 int node = ROOT;
 for (int i = 0; i < size(s); i++) {
   if ( f[node][ s[i] ] == -1 )
      f[node][ s[i] ] = sz++;
   node = f[node][ s[i] ];
 }
}

Notes: Root node is at f[0] sz is the numbers of nodes currently in trie

I guess would be easy to you implement other functions.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain it by taking an example?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is an explanation where you are storing the size of the trie ..But it is not suitable when we need to use this for finding the prefixes or calculating the xor or something like that ...Is it ???

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    How to mark a complete word? Using another array of same size of f? If we can't mark complete word, incomplete word will be found by searching.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's my implementation of trie without using recursion and with using 2D array.

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My code here

I like this because 'add' and 'query' are in the same function (: