If at first you don't succeed, try, trie again

My apologies in advance, that title came to me and I just had to make this post. Plus I feel like it's been pretty applicable to my life recently 😂

Anyhow! As my studies continue, I wanted to do a little introduction to tries!

What is a trie?

Apparently a trie is a relatively new computer programming concept, aimed to solve a problem with the time and space complexity of trees.

It is used mainly for alphabetical characters and stores them in a tree like structure for easy traversal to create word or patterns. The trie starts with an empty root node which is connected or linked to a node for every single letter in the alphabet.

note: that means depending on the alphabet you're using, it could be over 50 different nodes!

The node itself holds a value and one or more references to other nodes in sequence.

Big O

The time complexity of tries are O(n) on average, worst case being that the entire word is present in your trie and you cannot simply return false upon a few traversals. But in best case, that we are only searching for one letter perhaps, the time complexity would be O(1).

For the space complexity, tries really are just strings for the most part and would not take up more than O(n) space even to create new nodes for each letter. Again, in a similar case where our string is just one letter it would be best case O(1).

Code Example

So I think that rubyguides actually has an awesome example and I'll replicate it here for everyone. But I'll write out the functions in a way that is a bit more understandable for me.

First we will initialize our node class which will have a value, a next array to contain all of the references, and a word value to indicate if we have found/completed the word we are looking for.

class Node
  attr_reader   :value, :next
  attr_accessor :word
  def initialize(value)
    @value = value
    @word  = false
    @next  = []
  end

Next we have our trie class, which has a few different methods. One to add a character into the trie which will either try to find the character if it already exists or add it. Another method that only finds the character if it exists. And lastly a method to simply add a node to the trie.

class Trie
  def initialize
    @root = Node.new("*")
  end

  def add_character(character, trie)
    trie.each do |node|
      if node.value == character
        return node
      end
    end
    add_node(character, trie)
  end

  def find_character(character, trie)
    trie.each do |node|
      if node.value == character
        return node
      end
    end
  end

  def add_node(character, trie)
    new_node = Node.new(character)
    trie.push(new_node)
  end
end

Now that we've established our node and trie classes, we can get to making the methods that will actually make use of our trie!

def add_word(word)
  base = @root
  word.each_char do |letter|
    base = add_character(letter, base.next)
    base.word = true
  end
end

def find_word(word)
  base = @root
  word_found =
  word.each_char.all? { |letter| base = find_character(letter, base.next) 
  }
  yield word_found, base if block_given?
  base
end

The add_word method is very clear in that we are looping through the word and adding characters to create that word. The second method for find_word I didn't modify as much as I found that the all? method was difficult to simplify. It effectively finds out if the case is true for each of the letters then it will return true. If it finds any matches it will return those via yield.

Resources

Found some great resources to aid in your learning of tries:

• Trying to Understand Tries
• Tries with Gayle Laakmann McDowell

Thanks for reading and have an awesome weekend everyone!