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*);

CodePudding user response：

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];

CodePudding user response：

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".