dsa.trie module
Module containing trie class.
- class dsa.trie.Trie
Bases:
objectA trie implementation.
- build_word_list(node=None, word='', words=None)
Helper method to return a list of words given a starting node.
- Parameters:
node (TrieNode) – The current trie node.
word (str) – The word to build after each recursive call.
words – The list of words.
- Returns:
List of words that begin with a given prefix.
- Raises:
ValueError – If the word is not found.
- copy()
Create a deep copy of the Trie.
- Returns:
A deep copy of the trie.
- copy_node(node)
Recursively deep copy a node and its children.
- Parameters:
node (TrieNode) – The node to copy.
- Returns:
A deep copy of the node.
- delete(word, i=0, current=None)
Delete a word from the trie.
- Parameters:
word (str) – The word to delete.
i (int) – The index of character.
current (TrieNode) – The current node.
- Return type:
bool- Returns:
Boolean indicating if child node can be deleted.
- Raises:
ValueError – If the word is not found.
- delete_preorder(word, i=0, current=None)
Delete a word using preorder (Do not use! For demonstration purposes only).
- Parameters:
word (str) – The word to delete.
i (int) – The index of character.
current (TrieNode) – The current node.
- Returns:
Boolean indicating if child node can be deleted.
- Raises:
ValueError – If the word is not found.
- end_marker = '*'
end marker
- insert(word)
Insert a word into a trie.
- Parameters:
word (str) – The word to insert.
- Returns:
None
- list_words()
Return a list of all words in the trie.
- Return type:
list
- prefix(prefix)
Return a list of words that begin with a given prefix.
- Parameters:
prefix (str) – The prefix to search for.
- Returns:
List of words that begin with a given prefix. None if there are no matching words.
- Raises:
ValueError – If no words are found.
- root
root of the trie
- search(word)
Search for a word in a trie.
- Parameters:
word (str) – The word to search for.
- Return type:
bool- Returns:
Boolean on whether the complete word is found.
- search_node(substr)
Search for a substring in a trie.
- Parameters:
substr (str) – A substring to search for.
- Return type:
- Returns:
TriedNode where the substring begins None if the substring is not found
- suggest(prefix)
Return a list of close words with a given prefix.
- Parameters:
prefix (str) – The prefix to search for.
- Returns:
List of words that are similar to a given prefix. None if there are no matching words.
- Raises:
ValueError – If the word is not found.