AksLolCoding's blog

How Not to Code a Trie
By AksLolCoding, 3 weeks ago, In English

Below is a snippet from a trie implementation (the trie is stored in the 1-indexed vector t):

int get(int &u) {
    if (!u) {
        t.emplace_back();
        u = size(t)-1;
    }
    return u;
}
int insert(string s) {
    int u = 1;
    for (char c : s) {
        u = get(t[u].child[c-'a']);
    }
    return u;
}

This code is incorrect; can you figure out why?

Answer
  • Vote: I like it
  • +116
  • Vote: I do not like it

»
3 weeks ago, hide # |
 
Vote: I like it -18 Vote: I do not like it

A simple fix is to avoid passing a reference into t across emplace_back(). For example, make get take the child index by value and return the new index:

int get(int u) {
    if (!u) {
        t.emplace_back();
        u = t.size() - 1;
    }
    return u;
}

Then the original u = get(t[u].child[c - 'a']); is safe.

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This is also wrong: it doesn't update t[u].child[c-'a'] when a node is created

    → Reply
    • »
      »
      »
      3 weeks ago, hide # ^ |
       
      Vote: I like it +19 Vote: I do not like it

      How about changing get to take the parent/index instead of the child reference

      int get(int u, int c) {
    if (!t[u].child[c]) {
        t.emplace_back();
        t[u].child[c] = t.size() - 1;
    }
    return t[u].child[c];
}

      Then:

      u = get(u, c - 'a');

      This keeps the write-back behavior, while no reference into t survives the emplace_back().

      → Reply
»
3 weeks ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Hi, could I ask about the difference between implementing trie using pointers and using arrays? I usually implement it with pointers because my friend showed me that way, so I dont really know

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Pointer chasing is going to be slower as compared to array lookups, since the memory addresses are sparse which will result in more cache misses.

    Moreover, every time you want to add a new character, you have to do dynamic heap allocation, which means free space has to be found in the currently assigned memory block.

    Implementation wise, we are just mimicking the pointer approach, except whenever we have to add a new node, instead of looking for free memory, we just have to increment the pointer(like done in the above implementation). This way a lot of child nodes are close to their parent in memory and, leading to more cache hits and thus being faster.

    I don't use array based tries either since I started with pointers, and was too lazy to make a template for them.

    → Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it -8 Vote: I do not like it

    hello i love you orz

    → Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Codeforces better users be like:

→ Reply