SAeed's blog

How does trie tree work in case of more than one test case?
By SAeed, history, 9 years ago, In English

Hello everyone !!

I have this implementation for trie tree :

const int MAX_CHAR = 10;
struct trie {
	trie* child[MAX_CHAR];
	bool isLeaf;

	trie() {
            memset(child, 0, sizeof(child));
            isLeaf = 0;
	}

	void insert(char *str) {
		if(*str == '\0')
			isLeaf = 1;
		else {
			int cur = *str - '0';
			if(child[cur] == 0)
				child[cur] = new trie();
			child[cur]->insert(str+1);
		}
	}
};

I was wondering, what will happen in case of more than one test case? I know that C++ doesn't support garbage collector.

So, do I need to add the following destructor:

~trie(){
            for(int i = 0; i < 10; i++) delete child[i];
        }

Or can C++ delete this tree? I know bool isLeaf will be deleted at root node, and so is trie* child[MAX_CHAR];, but I'm not sure about the remaining part of my trie (the part where child array is pointing to).

Or may be there is another way of deleting this trie?

The reason I'm asking is because I'm afraid of MLE with big number of test cases. Can any one help?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I always delete it this way. 

void init(trie *cur)
{
    for (int i = 0; i < MAX_CHAR; i++)
        if (cur->child[i] != NULL)
            init(cur->child[i]);
    delete cur;
}
→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use std::unique_ptr<tree> child[MAX_CHAR];

→ Reply