Class: DSA::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/dsa-ruby/trie.rb

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

Returns a new instance of Trie.



9
10
11
 
# File 'lib/dsa-ruby/trie.rb', line 9

def initialize
  @root = Node.new
end

Instance Method Details

#delete(word) ⇒ Object 



32
33
34
 
# File 'lib/dsa-ruby/trie.rb', line 32

def delete(word)
  delete_recursive(@root, word, 0)
end

#insert(word) ⇒ Object 



13
14
15
16
17
18
19
20
21
 
# File 'lib/dsa-ruby/trie.rb', line 13

def insert(word)
  node = @root
  word.each_char do |char|
    node.children[char] ||= Node.new
    node = node.children[char]
  end
  node.word_end = true
  self
end

#search(word) ⇒ Object 



23
24
25
26
 
# File 'lib/dsa-ruby/trie.rb', line 23

def search(word)
  node = find_node(word)
  !!(node && node.word_end)
end

#starts_with(prefix) ⇒ Object 



28
29
30
 
# File 'lib/dsa-ruby/trie.rb', line 28

def starts_with(prefix)
  !!find_node(prefix)
end