malviyanshiv's blog

Content for learning implementation of trie using array
By malviyanshiv, history, 6 years ago, In English

I am struggling to find a good article on implementing trie using array. I did get some code implementing the same and attempted to read them but unable to beat my doubts!!! Please share the idea or link of some good article.

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

To implement tries as arrays, we assign each unique prefix that occurs in input a unique code (number).

(I am explaining with regard to binary numbers but idea is easily extensible when operating with words)

The size of your trie should be Number of Unique Prefixes * Alphabet size. For binary numbers, this turns out to be $$$(N * log(Max)) * 2$$$.

Let the code of some prefix P be X then trie[X]['0'] stores the code of the prefix : X + '0'.

We initialize the trie 2D array with some sentinel value (for instance -1) and each time we encounter a new prefix we give it a new code and store it according to the scheme described above. This allows us to form the chains that is otherwise created by pointers.

Refer this code by dragoon for this problem for a clean implementation.

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

    Thanks!!!
    Edit : Can you give some points to remember while implementing it. Like size to keep or something based on your experience ?

    → Reply