data_structures.trie.radix_tree

A Radix Tree is a data structure that represents a space-optimized trie (prefix tree) in whicheach node that is the only child is merged with its parent [https://en.wikipedia.org/wiki/Radix_tree]

Classes

RadixNode

Functions

main(→ None)
pytests(→ None)
test_trie(→ bool)

Module Contents

class data_structures.trie.radix_tree.RadixNode(prefix: str = '', is_leaf: bool = False)

delete(word: str) → bool

Deletes a word from the tree if it exists

Args:

word (str): word to be deleted

Returns:

bool: True if the word was found and deleted. False if word is not found

>>> RadixNode("myprefix").delete("mystring")
False

find(word: str) → bool

Returns if the word is on the tree

Args:

word (str): word to check

Returns:

bool: True if the word appears on the tree

>>> RadixNode("myprefix").find("mystring")
False

insert(word: str) → None

Insert a word into the tree

Args:

word (str): word to insert

>>> RadixNode("myprefix").insert("mystring")

>>> root = RadixNode()
>>> root.insert_many(['myprefix', 'myprefixA', 'myprefixAA'])
>>> root.print_tree()
- myprefix   (leaf)
-- A   (leaf)
--- A   (leaf)

insert_many(words: list[str]) → None

Insert many words in the tree

Args:

words (list[str]): list of words

>>> RadixNode("myprefix").insert_many(["mystring", "hello"])

match(word: str) → tuple[str, str, str]

Compute the common substring of the prefix of the node and a word

Args:

word (str): word to compare

Returns:

(str, str, str): common substring, remaining prefix, remaining word

>>> RadixNode("myprefix").match("mystring")
('my', 'prefix', 'string')

print_tree(height: int = 0) → None

Print the tree

Args:

height (int, optional): Height of the printed node

is_leaf = False

nodes: dict[str, RadixNode]

prefix = ''

data_structures.trie.radix_tree.main() → None

>>> pytests()

data_structures.trie.radix_tree.pytests() → None

data_structures.trie.radix_tree.test_trie() → bool