StoneCold_'s blog

Trie

By StoneCold_, 10 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

Comments Comments (8)
| Write comment?
»
10 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.

→ Reply
»
10 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.

→ Reply
»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

You can find it in PrinceOfPersia's blog on data structures.

→ Reply
»
8 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 (:

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

Why is this used instead of making nodes by using struct?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    1) because accessing values in arrays can benefit from caching while it won't be the case with struct since every node will be allocated wherever memory is available on heap(i.e. not contiguously).
    2) Dynamically allocating memory on heap is slower(i.e. using new when using struct).
    There might be other reasons but the above are the only one's which i can think of now.

    → Reply