C++ - Trie Implementation

Question

I am trying to learn trie and this is my first implementation. I started off with the idea of being able to handle different data types for key and value; however, I found the data structure a bit complicated and switched to just string for keys and int for values. So, parts of my code are specific to some data types while other parts are generic. My code is based on this link. Here is my current code:

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <cstddef>
#include <stack>

// Class Node
template<typename T, std::size_t N>
class Node
{
    T val;
    std::vector<Node<T, N>*> paths{N, nullptr};
public:
    //ctor
    Node() : val{T{}}
    {
    }
    // Set the value of node
    void set_val(T value)
    {
        val = value;
    }
    // Return the value of node
    T get_val() const
    {
        return val;
    }
    // Set a particular child node based on index
    void set_path(Node<T, N>* new_node, std::size_t index)
    {
        this -> paths[index] = new_node;
    }
    // Return a particular child node based on index
    Node* get_path(std::size_t index) const
    {
        return this -> paths[index];
    }
};

// Class Trie
template<typename U, typename T, std::size_t N>
class Trie
{
    Node<T, N>* root = new Node<T, N>{};
public:
    Trie();
    Trie(const std::list<U>, const T);
    ~Trie();
    void delete_all(Node<T, N>*);
    void insert(U, T);
    bool search(U, T&) const;
    void deletion(U);
};

// Ctor to initialize trie with a list
template<typename U, typename T, std::size_t N>
Trie<U, T, N>::Trie(const std::list<U> init_ls, const T val)
{
    for(auto it = init_ls.cbegin(); it != init_ls.cend(); it++)
    {
        this -> insert(*it, val);
    }
}

// Dtor for trie
template<typename U, typename T, std::size_t N>
Trie<U, T, N>::~Trie()
{
    Node<T, N>* node = root;
    this -> delete_all(node);
}

// Helper function for dtor
template<typename U, typename T, std::size_t N>
void Trie<U, T, N>::delete_all(Node<T, N>* node)
{

    if(node == nullptr)
    {
        return;
    }

    for(std::size_t i = 0; i < N; i++)
    {
        delete_all(node -> get_path(i));
    }
    delete node;
}

// Insert key - value pair in trie
template<typename U, typename T, std::size_t N>
void Trie<U, T, N>::insert(U key, T value)
{
    Node<T, N>* node = root;
    for(std::size_t i = 0; i < key.size(); i++)
    {
        std::size_t index = int(key[i]) - 97;
        if(node -> get_path(index) != nullptr)
        {
            node = node -> get_path(index);
        }
        else
        {
            Node<T, N>* new_node = new Node<T, N>{};
            node -> set_path(new_node, index);
            node = node -> get_path(index);
        }
        if(i == key.size() - 1)
        {
            node -> set_val(value);
        }
    }
}

// Search key - value pair in trie
template<typename U, typename T, std::size_t N>
bool Trie<U, T, N>::search(U key, T& ret_val) const
{
    Node<T, N>* node = root;
    for(std::size_t i = 0; i < key.size(); i++)
    {
        int index = int(key[i]) - 97;
        if(node -> get_path(index) == nullptr)
        {
            ret_val = T{};
            return false;
        }
        else
        {
            node = node -> get_path(index);
        }
        if(i == key.size() - 1)
        {
            if(node -> get_val() != T{})
            {
                ret_val = node -> get_val();
                return true;
            }
            else
            {
                ret_val = T{};
                return false;
            }
        }
    }
    return false;
}

// Delete key - value pair from trie
template<typename U, typename T, std::size_t N>
void Trie<U, T, N>::deletion(U key)
{
    Node<T, N>* node = root;
    std::stack<Node<T, N>*> node_stack;
    for(std::size_t i = 0; i < key.size(); i++)
    {
        int index = int(key[i]) - 97;
        if(node -> get_path(index) != nullptr)
        {
            node = node -> get_path(index);
            node_stack.push(node);
        }
        else
        {
            std::cout << "Key does not exist\n";
            return;
        }
        if(i == key.size() - 1)
        {
            if(node -> get_val() != T{})
            {
                node -> set_val(T{});
            }
        }
    }
    while(!node_stack.empty())
    {
        Node<T, N>* curr_node = node_stack.top();
        node_stack.pop();
        for(std::size_t i = 0; i < N; i++)
        {
            if(curr_node -> get_val() != T{} || curr_node -> get_path(i) != nullptr)
            {
                return;
            }
        }
        delete curr_node;
    }
}

// Main
int main()
{
    Trie<std::string, int, 26> t1{{"apple", "ball", "cat", "banana", "beach", "ballet", "dog"}, 1};
    int ret_val;
    bool success = t1.search("ballet", ret_val);
    std::cout << "Search result: " << success << "\t" << "Return Value: " << ret_val << "\n";
    t1.insert("elephant", 1);
    t1.insert("cats", 1);
    success = t1.search("cats", ret_val);
    std::cout << "Search result: " << success << "\t" << "Return Value: " << ret_val << "\n";
    success = t1.search("cat", ret_val);
    std::cout << "Search result: " << success << "\t" << "Return Value: " << ret_val << "\n";
    t1.deletion("cat");
    //t1.deletion("cats");
    success = t1.search("cats", ret_val);
    std::cout << "Search result: " << success << "\t" << "Return Value: " << ret_val << "\n";
    success = t1.search("cat", ret_val);
    std::cout << "Search result: " << success << "\t" << "Return Value: " << ret_val << "\n";
    success = t1.search("bald", ret_val);
    std::cout << "Search result: " << success << "\t" << "Return Value: " << ret_val << "\n";
    return 0;
}

The things I would like to know:

1) Is the approach and operations included correct, especially for the deletion of key?

2) When I think about it, template specialization seem to be one way to make it handle multiple data types. Are there any better suggestions?

3) Is the memory management part good?

4) Is there a check list I should follow while coding data structures?

5) General review and suggestion please.

Note: I would like to thank everyone who has helped me with my previous questions. I understand that I haven't been able to put into practice all the previous advice that I received. I am trying to get there in steps, through practice. Thank You!

Answer 1

Node

• Each node in a trie owns its child nodes, and nodes elsewhere in the trie don't ever point to nodes in a completely different branch. As such, a node can store its children by value in a container. There's no need to use pointers here which means we don't have to worry about manual memory management and we effectively get move / copy / assignment for free. :)
• Is val actually necessary? It seems to just be a marker for the end of a word, in which case a bool last_letter; would be clearer. Unless the word indexing is a feature you really need, it might be better to stick with a boolean, remove the template argument, and remove the value argument from the Trie interface.
• There's no need to create all the (empty) child nodes in the vector on initialization. This will make the trie much larger in memory than necessary. It would be better to use a map data structure.
• Using a map data structure also means there's no need to adjust characters to indices. We can use the character as a key directly.
• Using a dynamic data structure instead of a fixed size vector actually removes the need for the std::size_t N template argument!
• Why use this-> for the paths member, but not for val?

---

Trie

• With the above change (storing nodes by value), we can get rid of the destructor, and the delete_all function. Copy / assignment also becomes trivial.
• The default constructor is listed, but not implemented!
• The list constructor might be a good place to use a std::initializer_list.
• The list constructor only allows one "value" argument for all the words in the list, whereas the insert function allows different values for each word.
• Nice job on the iterative algorithms. :)
• The if (i == key_size() - 1) { ... } part doesn't actually need to be inside the for loop in insert, search, and delete. It can be placed after the loop, and without the index check (since we keep track of the last node anyway). This does mean we need to check for empty keys at the start of the functions, but we should probably be doing that anyway (and assert / throw / return false). We can then use range-based for loops, since we no longer need the index.
• Take key arguments (which are std::strings) by const& to avoid unnecessary copying.
• int(key[i]) - 97:
  • Not needed when using a map. (Otherwise it should probably be a static function of the Trie class (char_to_index() or something), and 97 should be a named constant variable.)
  • What if someone passed in a string that contains non-alphabetic chars?
  • What if someone passed in a value of 0?
• insert() - What if the same word is already in the trie with a different value? (Maybe return a boolean for success / failure of insertion).
• deletion() should probably be called erase (more consistent with std:: data structures).
• deletion() - Maybe return a boolean for success / failure (if the key isn't there).
• deletion() - By using a map data structure in the node, we no longer need to iterate all of a node's children. We can simply remove the relevant entry. (This requires a couple more member functions on the Node class).
• The logic inside the loops in insert, search and delete() calls get_path(index) more than strictly necessary.

---

Modified Code

I've renamed a few things and used auto a bit more, but these are just stylistic changes; the important things are mentioned above.

#include <iostream>
#include <map>
#include <initializer_list>
#include <string>
#include <stack>
#include <cassert>

class Node
{
    bool last_letter;
    std::map<char, Node> paths;

public:
    Node(): last_letter{ false }
    {
    }

    void set_last_letter(bool value)
    {
        last_letter = value;
    }
    bool is_last_letter() const
    {
        return last_letter;
    }

    void add_child(Node new_node, char index) // renamed set_path
    {
        auto inserted = paths.insert({ index, std::move(new_node) });
        assert(inserted.second); // make sure it doesn't already exist
    }
    Node* get_child(char index) // need const and non-const versions now
    {
        auto path = paths.find(index);

        if (path == paths.end())
            return nullptr;

        return &path->second;
    }
    Node const* get_child(char index) const // need const and non-const versions now
    {
        auto path = paths.find(index);

        if (path == paths.end())
            return nullptr;

        return &path->second;
    }
    void remove_child(char index)
    {
        paths.erase(index);
    }
    bool has_multiple_children() const
    {
        return paths.size() > 1u;
    }

};

class Trie
{
    Node root;

public:
    Trie() {}
    Trie(std::initializer_list<std::string>);

    void insert(std::string const&);
    bool contains(std::string const&) const;
    bool erase(std::string const&);
};

Trie::Trie(std::initializer_list<std::string> init_ls)
{
    for (auto const& key : init_ls)
        insert(key);
}

void Trie::insert(std::string const& key)
{
    assert(!key.empty());

    auto node = &root;
    for (auto ch : key)
    {
        auto next_node = node->get_child(ch);

        if (next_node == nullptr)
        {
            node->add_child({}, ch);
            next_node = node->get_child(ch);

            assert(next_node != nullptr);
        }

        node = next_node;
    }

    node->set_last_letter(true);
}

bool Trie::contains(std::string const& key) const
{
    assert(!key.empty());

    auto node = &root;
    for (auto ch : key)
    {
        node = node->get_child(ch);

        if (node == nullptr)
            return false;
    }

    return node->is_last_letter();
}

bool Trie::erase(std::string const& key)
{
    assert(!key.empty());

    auto node = &root;
    auto node_stack = std::stack<Node*>{ };

    for (auto ch : key)
    {
        node = node->get_child(ch);

        if (!node) // key not in trie
            return false;

        node_stack.push(node);
    }

    if (!node->is_last_letter()) // not at end of word!
        return false;

    node->set_last_letter(false);

    assert(node_stack.size() == key.size());

    while (!node_stack.empty())
    {
        auto curr_node = node_stack.top();
        node_stack.pop();

        auto index = node_stack.size();

        if (curr_node->has_multiple_children() || node_stack.empty())
            curr_node->remove_child(key[index]);
    }

    return true;
}

---

Unit Tests

You've added a few tests, but it's best to split things up and test individual features / functionality - proper unit testing!

In the simplest case, you can just use a function that takes a boolean and outputs whether it's true or false. But it's worth getting to know GoogleTest or another unit testing framework.

void test(bool condition, std::string const& message)
{
    if (condition)
        std::cout << "pass\n";
    else
        std::cout << "FAIL: " << message << "\n";
}

...

{
    Trie t;
    test(t.is_empty(), "default construction produces empty trie");
}
{
    Trie t;
    t.insert("moo");
    Trie copy(t);
    test(copy.contains("moo"), "copy construction copies other trie");
}
{
    Trie t;
    t.insert("moo");
    Trie copy(std::move(t));
    test(copy.contains("moo"), "move construction copies other trie");
    test(t.is_empty(), "move construction empties moved from trie");
}
// todo: test assignment too...
{
    Trie t;
    t.insert("cats");
    test(!t.contains("cat"), "partial prefix of word in trie does not count when searching");
}
{
    Trie t;
    t.insert("cat");
    t.insert("cats");
    t.erase("cat");
    test(t.contains("cats"), "erasing partial prefix of word in trie does not affect longer word");
}
//{
//  Trie t;
//  t.insert(""); // hits assertion in the modified code above! if we had a proper testing framework we could EXPECT_DEATH() or EXPECT_THROW() here...
//}

As well as helping to make your code bug-free and maintainable, it also helps with thinking about the interface and desired functionality. Unit testing is where you decide "when a user attempts to add a string that already exists in the trie, should I silently allow it, return false, assert, or throw?". Once you have decided, you can write a unit test to prove and document that behavior.

---

Misc Advice

• Rather then writing a generic template data structure right away, it's often better to write the specific version first. Start off with no templates and hard-code in char and std::string. Once that version works and is tested thoroughly, it should be relatively easy to make it generic.
• Don't add comments for obvious things (like // Class node or // Main).

---

Q&A

1. Yep. The algorithms look correct to me.
2. I don't think I've ever seen a Trie that wasn't used for strings. I'm not sure template specialization means what you think it means here. Template specialization is used for particular types that need to be treated differently, and effectively overrides the generic template behaviour. I don't think it would be useful here. Using templates to allow different key / value types as in your original code is reasonable if you need that feature.
3. No! Since we can store nodes by value, the memory management is not needed at all. If it were necessary, you should still use std::unique_ptr instead of manually newing and deleteing things.
4. Probably, but this is already getting too long...
5. See above!