Блог пользователя SAeed

How does trie tree work in case of more than one test case?
Автор SAeed, история, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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;
}
→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить