Docs Radix Trie on GitHub

Radix Trie¶

A radix trie, or compressed trie, is similar to a standard trie but it ensures that each internal node in the trie has at least two children. It enforces this rule by compressing chains of single-child nodes into individual edges. So, the following is a simple trie formed by inserting these three words: “car”, “cart”, and “cast”.

ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓

And the following is a radix trie, or compressed trie, created using the same three words:

ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓

The advantage of a radix trie over a standard trie is that the number of nodes of the compressed trie is less than the latter. Also, the number of nodes is proportional to the number of strings and not to their total length. This additional compression scheme reduces the total space for the trie itself from O(n) for the standard trie to O(s) for the radix trie, where n is the total length of the strings and s is the number of strings.

Searching in a radix trie is not necessarily faster than in a standard tree, since there is still need to compare every character of the desired pattern with the potentially multi-character labels while traversing paths in the trie.

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

n is the number of nodes currently in the radix trie.
m is the length of the passed string.

Method	Description	Worst-case	Optimal
is_empty()	Checks if the radix trie is empty.	O(1)	O(1)
__len__()	Returns the number of nodes inside the radix trie.	O(n)	O(1)
__repr__()	Represents the radix trie as a string.	O(n)	O(n)
__iter__()	Iterates over the radix trie.	O(n)	O(n)
__contains__()	Checks the existence of the given item in the radix trie.	O(m)	O(1)
get_height()	Gets the radix trie’s height.	O(n)	O(n)
get_depth()	Gets the radix trie’s depth.	O(1)	O(1)
get_nodes_per_level()	Returns a list of all nodes per level found in the radix trie.	O(n)	O(n)
count_leaf_nodes()	Counts all leaf nodes in the radix trie.	O(n)	O(n)
clear()	Clears the whole radix trie instance.	O(1)	O(1)
to_list()	Converts the radix trie instance to list.	O(n)	O(n)
auto_complete()	Auto-completes given index from the radix trie.	O(m)	O(m)
insert()	Inserts a new word to the radix trie.	O(m)	O(m)
remove()	Removes a word from the radix trie.	O(m)	O(m)

☕️ API¶

Here are all of the public methods that can be used with RadixTrie() objects:

class extra.trees.radix_trie.RadixTrie¶

A radix trie is a compressed trie that ensures that each internal node has at least two children. It enforces this rule by compressing chains of single-child nodes into individual edges. It is defined using a collection of tree nodes, where each node contains string value and each node has a list of references to the children tree nodes in a tree-form structure.

__contains__(word)¶

Searches the RadixTrie() for the given word and returns True if the whole word exists and False if not.

Parameters:	word (str) – The word to be searched for in the RadixTrie() instance.
Returns:	Returns True if the value exists in the RadixTrie() instance and False if not.
Return type:	bool

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> "car" in rt
True
>>> "cas" in rt
False
>>> "care" in rt
False

__init__()¶

Creates an empty RadixTrie() object!!

Example

>>> rt = RadixTrie()
>>> type(rt)
<class 'extra.trees.radix_trie.RadixTrie'>
>>> rt
--

__iter__()¶

Iterates over the RadixTrie() instance and returns a generator of the string values stored at the different nodes in breadth-first manner.

Yields:	str – The string stored at each node in the instance.

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> for value in rt:
...     print(value, end=',')
ca,r,st,t,

__len__()¶

Gets the length of the RadixTrie() instance. Length is the number of nodes in the instance.

Returns:	The length of the RadixTrie() instance. Length is the number of nodes in the instance.
Return type:	int

Examples

>>> rt = RadixTrie()
>>> len(rt)
0
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> len(rt)
5

__repr__()¶

Represents the RadixTrie() instance as a string.

Returns:	The string-representation of the RadixTrie() instance.
Return type:	str

Example

>>> rt = RadixTree()
>>> rt
--
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓

auto_complete(prefix='')¶

Parses the RadixTrie() instance and retrieves all the words that has the given prefix. In other words, auto-compeletes a given prefix using all saved words found in the RadixTrie() instance.

Parameters:	prefix (str (default '')) – A prefix to auto-complete.
Returns:	A list of all found words that have the given prefix.
Return type:	list

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.auto_complete("car")
["car", "cart"]
>>> rt.auto_complete("cas")
["cast"]
>>> rt.auto_complete()
['car', 'cart', 'cast']

Note

Using an empty prefix as an input will return all saved words in the RadixTrie() instance.

clear()¶

Removes all nodes within the RadixTrie() instance in constant time.

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.clear()
>>> rt
--
>>> rt.is_empty()
True

count_leaf_nodes()¶

Counts the number of leaf nodes in the RadixTrie() instance. Leaf nodes are the trie nodes that have no children.

Returns:	A positive integer representing the number of leaf nodes in the RadixTrie().
Return type:	int

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.count_leaf_nodes()
2

get_depth()¶

Gets the depth of the RadixTrie() instance.

Returns:	A positive integer representing the depth of the given RadixTrie().
Return type:	int

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.get_depth()
0

get_height()¶

Gets the height of the RadixTrie() instance. The trie’s height is the number of edges between the root and the furthest leaf node.

Returns:	A positive integer representing the height of the instance.
Return type:	int

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.get_height()
3

get_nodes_per_level()¶

Retrieves all trie nodes within the RadixTrie() instance so that all trie nodes in a certain level will be concatenated into a separate list.

Returns:	A nested list where the first inner-list has all the trie nodes in the first level, the second inner-list has all the trie nodes in the second level, … so on.
Return type:	list

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.get_nodes_per_level()
[['ca'], ['r', 'st'], ['t']]

has_prefix(prefix)¶

Searches the RadixTrie() for the given prefix and returns True if the whole prefix exists and False if not.

Parameters:	prefix (str) – The prefix to be searched for in the RadixTrie() instance.
Returns:	Returns True if the prefix exists in the RadixTrie() instance and False if not.
Return type:	bool

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.has_prefix("car")
True
>>> rt.has_prefix("cas")
True
>>> "cas" in rt
False

insert(word)¶

Inserts a word in the RadixTrie() instance.

Parameters:	word (str) – The new word that will be inserted.
Raises:	ValueError: – If the given word is empty. TypeError: – If the type of the given word is not str.

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓

is_empty()¶

Checks if the RadixTrie() instance is empty or not in constant time.

Returns:	A boolean flag showing if the RadixTrie() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> rt = RadixTrie()
>>> rt.is_empty()
True
>>> rt.insert("apple")
>>> rt.is_empty()
False

remove(word)¶

Removes the given word from the RadixTrie() instance.

Parameters:	word (str) – The word to be deleted from the RadixTrie().
Raises:	UserWarning: If the RadixTrie() instance is empty of if the value wasn’t found in the instance.

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.remove("cart")
>>> rt
ROOT
└─┬ ca
  ├── r ✓
  └── st ✓

to_list()¶

Converts the RadixTrie() instance to a list where values will be inserted in breadth-first manner.

Returns:	A list object containing the same elements as the RadixTrie() instance.
Return type:	list

Example

>>> rt = RadixTrie()
>>> rt.insert("car")
>>> rt.insert("cart")
>>> rt.insert("cast")
>>> rt
ROOT
└─┬ ca
  ├─┬ r ✓
  │ └── t ✓
  └── st ✓
>>> rt.to_list()
['ca', 'r', 'st', 't']

Previous Next

2020, anwarvic

Created using Sphinx (1.8.6) with Minoo (Beta 0.9.7) theme.