Trie Class Reference

Collaboration diagram for Trie:

Classes
struct	TrieNode

Public Member Functions
	Trie ()
	constructor to initialise the root of the trie.
void	insert (const std::string &word)
bool	search (const std::string &word)
void	removeWord (const std::string &word)

Private Member Functions
std::shared_ptr< TrieNode >	removeWordHelper (const std::string &word, std::shared_ptr< TrieNode > curr, size_t index)

Static Private Member Functions
static bool	hasChildren (std::shared_ptr< TrieNode > node)

Private Attributes
std::shared_ptr< TrieNode >	m_root

Static Private Attributes
static constexpr size_t	ALPHABETS = 26

Detailed Description

A basic implementation of trie class to store only lower-case strings. You can extend the implementation to all the ASCII characters by changing the value of @ ALPHABETS to 128.

Constructor & Destructor Documentation

Trie()

Trie::Trie ( )

inline

constructor to initialise the root of the trie.

: m_root(std::make_shared<TrieNode>()) {}

Member Function Documentation

hasChildren()

static bool Trie::hasChildren ( std::shared_ptr< TrieNode > node )

inlinestaticprivate

Function to check if a node has some children which can form words.

Parameters

node	whose character array of pointers need to be checked for children.

Returns

true if a child is found

false if a child is not found

                                                                 {
        for (size_t i = 0; i < ALPHABETS; i++) {
            if (node->character[i]) {
                return true;
            }
        }
        return false;
    }

insert()

void Trie::insert ( const std::string & word )

inline

Insert a word into the trie.

Parameters

word	which needs to be inserted into the string.

                                       {
        auto curr = m_root;
        for (char ch : word) {
            size_t index = ch - 'a';
 
            // if a node for current word is not already present in trie, create
            // a new node for it.
            if (!curr->character[index]) {
                curr->character[index] = std::make_shared<TrieNode>();
            }
 
            curr = curr->character[index];
        }
        curr->isEndOfWord = true;
    }

removeWord()

void Trie::removeWord ( const std::string & word )

inline

                                           {
        m_root = removeWordHelper(word, m_root, 0);
    }

removeWordHelper()

std::shared_ptr< TrieNode > Trie::removeWordHelper ( const std::string & word, std::shared_ptr< TrieNode > curr, size_t index )

inlineprivate

A recursive helper function to remove a word from the trie. First, it recursively traverses to the location of last character of word in the trie. However, if the word is not found, the function returns a runtime error. Upon successfully reaching the last character of word in trie, if sets the isEndOfWord to false and deletes the node if and only if it has no children, else it returns the current node.

Parameters

word	is the string which needs to be removed from trie.
curr	is the current node we are at.
index	is the index of the @word we are at.

Returns

if current node has childern, it returns @ curr, else it returns nullptr.

Exceptions

a	runtime error in case @ word is not found in the trie.

                                                             {
        if (word.size() == index) {
            if (curr->isEndOfWord) {
                curr->isEndOfWord = false;
            }
            if (hasChildren(curr)) {
                return curr;
            }
            return nullptr;
        }
 
        size_t idx = word[index] - 'a';
 
        // Throw a runtime error in case the user enters a word which is not
        // present in the trie.
        if (!curr->character[idx]) {
            throw std::runtime_error(std::move(std::string("Word not found.")));
        }
 
        curr->character[idx] =
            removeWordHelper(word, curr->character[idx], index + 1);
 
        // This if condition checks if the node has some childern.
        // The 1st if check, i.e. (curr->character[idx]) is checked specifically
        // because if the older string is a prefix of some other string, then,
        // there would be no need to check all 26 characters. Example- str1 =
        // abbey, str2 = abbex and we want to delete string "abbey", then in
        // this case, there would be no need to check all characters for the
        // chars a,b,b.
        if (curr->character[idx] || hasChildren(curr)) {
            return curr;
        }
        return nullptr;
    }

Here is the call graph for this function:

search()

bool Trie::search ( const std::string & word )

inline

Search if a word is present in trie or not.

Parameters

word	which is needed to be searched in the trie.

Returns

True if the word is found in trie and isEndOfWord is set to true.

False if word is not found in trie or isEndOfWord is set to false.

                                       {
        auto curr = m_root;
        for (char ch : word) {
            size_t index = ch - 'a';
 
            // if any node for a character is not found, then return that the
            // word cannot be formed.
            if (!curr->character[index]) {
                return false;
            }
            curr = curr->character[index];
        }
        return curr->isEndOfWord;
    }

---

The documentation for this class was generated from the following file:

• data_structures/trie_modern.cpp