Class: DSA::Trie

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

Overview

DSA::Trie - A prefix tree (trie) data structure for string storage and lookup.

Efficient for prefix-based searches and word lookups.

Examples:

trie = DSA::Trie.new
trie.insert("apple")
trie.search("apple")     # => true
trie.search("app")       # => false
trie.starts_with("app")  # => true
trie.delete("apple")

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DSA::Trie

Initialize a new empty trie.



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

def initialize
  @root = Node.new
end

Instance Method Details

#delete(word) ⇒ Boolean

Deletes a word from the trie if it exists.

Examples:

trie.insert("apple")
trie.delete("apple")  # => true
trie.delete("banana") # => false

Parameters:

  • word (String) —

    the word to delete

Returns:

  • (Boolean) —

    true if the word was deleted, false if not found



81
82
83
 
# File 'lib/dsa-ruby/trie.rb', line 81

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

#insert(word) ⇒ DSA::Trie

Inserts a word into the trie.

Examples:

trie.insert("apple").insert("banana")

Parameters:

  • word (String) —

    the word to insert

Returns:



38
39
40
41
42
43
44
45
46
 
# File 'lib/dsa-ruby/trie.rb', line 38

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) ⇒ Boolean

Searches for an exact word in the trie.

Examples:

trie.insert("apple")
trie.search("apple")  # => true
trie.search("app")    # => false

Parameters:

  • word (String) —

    the word to search for

Returns:

  • (Boolean) —

    true if the word exists in the trie



56
57
58
59
 
# File 'lib/dsa-ruby/trie.rb', line 56

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

#starts_with(prefix) ⇒ Boolean

Checks if any word in the trie starts with the given prefix.

Examples:

trie.insert("apple")
trie.starts_with("app")  # => true
trie.starts_with("ban")  # => false

Parameters:

  • prefix (String) —

    the prefix to search for

Returns:

  • (Boolean) —

    true if any word starts with the prefix



69
70
71
 
# File 'lib/dsa-ruby/trie.rb', line 69

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