Created
December 2, 2016 20:51
-
-
Save arjans/0169fb4045becb63d4673fb19bf192b2 to your computer and use it in GitHub Desktop.
Trie Implementation in Ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Meant for strings consisting of English characters. | |
class TrieNode | |
attr_accessor :terminal, :character | |
def initialize(character: "", terminal: false) | |
@character = character | |
@terminal = terminal | |
@children = [] | |
end | |
def add_node(node) | |
i = node.character.ord % 97 | |
@children[i] = node | |
end | |
def next_node(character) | |
i = character.ord % 97 | |
@children[i] | |
end | |
end | |
class Trie | |
def initialize | |
@root = TrieNode.new | |
end | |
def word_present?(word) | |
current_node = @root | |
word.chars.each do |c| | |
unless current_node = current_node.next_node(c) | |
return nil | |
end | |
end | |
current_node.terminal | |
end | |
def add_word(word) | |
current_node = @root | |
word.chars.each do |c| | |
if current_node.next_node(c) | |
current_node = current_node.next_node(c) | |
else | |
new_node = TrieNode.new(character: c) | |
current_node.add_node(new_node) | |
current_node = new_node | |
end | |
end | |
current_node.terminal = true | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment