c++ Trie data structure implementation clarifications

Question

The current code is an implementation of the Trie data structure in C++.

For me, in the memory, a Trie contains two items, a pointer to a table of Tries and a bool.

The question is where a single character is stored in memory. if a node contains a node* and a bool?

 class Trie {
    public:
        bool isLeaf;
        Trie* character[CHAR_SIZE];
    
        //contructor
        Trie() {
            this->isLeaf = false;
            for (int i = 0; i < CHAR_SIZE; i++) {
                this->character[i] = nullptr;
            }
        }
    };
    void insert(string);
        bool deletion(Trie*&, string);
        bool search(string);
        bool haveChildren(Trie const*);

Answer 1

You do not have any characters stored anywhere. You have an array of Trie objects called 'character' but no characters.

I do not know the Trie data structure but you probably want

class Trie {
    public:
        bool isLeaf;
        char ch;  <<<<<<<<<<<<<<<<<============
        Trie* character[CHAR_SIZE];

Answer 2

The way you have set up your Trie class, a Trie object represents a character by its position in its parent's character table. So a single character x would be represented by:

• a root Trie object with isLeaf = false with all of character being null pointers, except for character[ 'x' ] pointing to...
• a Trie object with isLeaf = true.

Needless to say that this is a bit less than optimal. An ideal structure would need only one Trie object for the single character case. But given your existing code and barring major refactoring, that is how a single character would be represented by your Trie.

---

If you are looking at rather sparse data, you could optimize your Trie to store unabiguous sequences in the object. So if you have "foo" and "fornicitialicious", you would have a root Trie that stores "fo" and two pointers, one to a leaf Trie storing "o" and one to a leaf Trie storing "rnicitialicious". That way, a single character 'x' would be a single (leaf) Trie storing "x".