data_structures.trie.radix_tree

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

Classes

RadixNode
TestRadixNode	A class whose instances are single test cases.

Functions

test_trie(→ None)

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 whether 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 = ''

class data_structures.trie.radix_tree.TestRadixNode(methodName='runTest')

Bases: unittest.TestCase

A class whose instances are single test cases.

By default, the test code itself should be placed in a method named ‘runTest’.

If the fixture may be used for many test cases, create as many test methods as are needed. When instantiating such a TestCase subclass, specify in the constructor arguments the name of the test method that the instance is to execute.

Test authors should subclass TestCase for their own tests. Construction and deconstruction of the test’s environment (‘fixture’) can be implemented by overriding the ‘setUp’ and ‘tearDown’ methods respectively.

If it is necessary to override the __init__ method, the base class __init__ method must always be called. It is important that subclasses should not change the signature of their __init__ method, since instances of the classes are instantiated automatically by parts of the framework in order to be run.

When subclassing TestCase, you can set these attributes: * failureException: determines which exception will be raised when

the instance’s assertion methods fail; test methods raising this exception will be deemed to have ‘failed’ rather than ‘errored’.

• longMessage: determines whether long messages (including repr of

  objects used in assert methods) will be printed on failure in addition to any explicit message passed.

• maxDiff: sets the maximum length of a diff in failure messages

  by assert methods using difflib. It is looked up as an instance attribute so can be configured by individual tests if required.

test_trie() → None

test_trie_2() → None

Now add a new test case that inserts foobbb, fooaaa, foo in the given order and checks for different assertions

data_structures.trie.radix_tree.test_trie() → None