Trie¶

1

import "std/data/trie";

Trie struct¶

A trie (also called prefix tree) is a data structure that stores a set of strings in a way that makes prefix-based lookups efficient. Every edge is labeled with a single character, so a word corresponds to a path from the root down to a node marked as the end of a word. Words that share a common prefix also share the nodes that spell out that prefix.

Time complexity (k = length of the word/prefix):
Insert: O(k)
Contains: O(k)
Starts with: O(k)
Remove: O(k)

Constructors¶

ctor¶

1

public p Trie.ctor()

Construct an empty trie

ctor¶

1

public p Trie.ctor(const Trie& original)

Construct a trie as a deep copy of another trie

Parameters

dtor¶

1

public p Trie.dtor()

Destruct the trie, freeing all allocated nodes

Methods¶

insert¶

1

public p Trie.insert(string word)

Insert a word into the trie. Inserting a word that is already present has no effect.

Parameters

contains¶

1

public f<bool> Trie.contains(string word)

Check if the trie contains the given word.

Parameters

Returns: bool — True if the exact word was inserted before, false otherwise

startsWith¶

1

public f<bool> Trie.startsWith(string prefix)

Check if the trie contains any word that starts with the given prefix. The empty prefix is contained in every trie.

Parameters

Returns: bool — True if at least one stored word starts with the prefix, false otherwise

countWordsWithPrefix¶

1

public f<unsigned long> Trie.countWordsWithPrefix(string prefix)

Count how many stored words start with the given prefix.

Parameters

Returns: unsigned long — Number of stored words that start with the prefix

remove¶

1

public p Trie.remove(string word)

Remove a word from the trie. Removing a word that is not present has no effect. Nodes that become unused after the removal are pruned and their memory is freed.

Parameters

getSize¶

1

public f<unsigned long> Trie.getSize()

Get the number of words stored in the trie.

Returns: unsigned long — The number of stored words

isEmpty¶

1

public f<bool> Trie.isEmpty()

Check if the trie is empty.

Returns: bool — True if no words are stored, false otherwise

clear¶

1

public p Trie.clear()

Remove all words from the trie, freeing all nodes but the root.

Operators¶

operator=¶

1

public p operator=(Trie& this, const Trie& other)

Copy-assign another trie into this one, replacing all currently stored words

Parameters