Please can anyone provide a good implementation of trie using a 2D array instead of using recursion ?
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Please can anyone provide a good implementation of trie using a 2D array instead of using recursion ?
Name |
---|
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.
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.
It's my implementation of trie without using recursion and with using 2D array.
chrome Can you please explain your code. It would be really nice and helpful.
Thanks chrome!
You can find it in PrinceOfPersia's blog on data structures.
My code here
I like this because 'add' and 'query' are in the same function (:
Why is this used instead of making nodes by using struct?
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.