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 elements currently in the container.
• m is the length of the passed string.

☕️ API¶

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

class extra.trees.trie.Trie¶

A trie is a tree-based data structure that can be defined recursively using a collection of tree nodes, where each node contains a string value and each node has a list of references to the children tree nodes in a tree- form structure.

__contains__(word)¶

Searches the Trie() 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 Trie() instance.
Returns:	Returns True if the value exists in the Trie() instance and False if not.
Return type:	bool

Example

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

__init__()¶

Creates an empty Trie() object!!

Example

>>> t = Trie()
>>> type(t)
<class 'extra.trees.trie.Trie'>
>>> t
--

__iter__()¶

Iterates over the Trie() instance and returns a generator of the nodes values in breadth-first manner.

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

Example

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> for value in t:
...     print(value, end=',')
c,a,r,s,t,t,

__len__()¶

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

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

Examples

>>> t = Trie()
>>> len(t)
1
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> len(t)
7

__repr__()¶

Represents the Trie() instance as a string.

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

Example

>>> t = Trie()
>>> t
--
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓

auto_complete(prefix='')¶

Parses the Trie() 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 Trie() 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

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.auto_complete("car")
["car", "cart"]
>>> t.auto_complete("cas")
["cast"]
>>> t.auto_complete()
['car', 'cart', 'cast']

Note

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

clear()¶

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

Example

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.clear()
>>> t
--
>>> t.is_empty()
True

count_leaf_nodes()¶

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

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

Example

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.count_leaf_nodes()
2

get_depth()¶

Gets the depth of the Trie() instance.

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

Example

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.get_depth()
0

get_height()¶

Gets the height of the Trie() 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

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.get_height()
4

get_nodes_per_level()¶

Retrieves all trie nodes within the Trie() 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

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.get_nodes_per_level()
[['c'], ['a'], ['r', 's'], ['t', 't']]

has_prefix(prefix)¶

Searches the Trie() 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 Trie() instance.
Returns:	Returns True if the prefix exists in the Trie() instance and False if not.
Return type:	bool

Example

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

insert(word)¶

Inserts a word in the Trie() 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

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓

is_empty()¶

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

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

Example

>>> t = Trie()
>>> t.is_empty()
True
>>> t.insert("apple")
>>> t.is_empty()
False

remove(word)¶

Removes the given word from the Trie() instance.

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

Example

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.remove("cart")
ROOT
└─┬ c
  └─┬ a
    ├── r ✓
    └─┬ s
      └── t ✓

to_list()¶

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

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

Example

>>> t = Trie()
>>> t.insert("car")
>>> t.insert("cart")
>>> t.insert("cast")
>>> t
ROOT
└─┬ c
  └─┬ a
    ├─┬ r ✓
    │ └── t ✓
    └─┬ s
      └── t ✓
>>> t.to_list()
['c', 'a', 'r', 's', 't', 't']