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:
Thanks for reading and have an awesome weekend everyone!
Top comments (0)