Delete on a very deep tree
- by Kathoz
I am building a suffix trie (unfortunately, no time to properly implement a suffix tree) for a 10 character set. The strings I wish to parse are going to be rather long (up to 1M characters). The tree is constructed without any problems, however, I run into some when I try to free the memory after being done with it.
In particularly, if I set up my constructor and destructor to be as such (where CNode.child is a pointer to an array of 10 pointers to other CNodes, and count is a simple unsigned int):
CNode::CNode(){
count = 0;
child = new CNode* [10];
memset(child, 0, sizeof(CNode*) * 10);
}
CNode::~CNode(){
for (int i=0; i<10; i++)
delete child[i];
}
I get a stack overflow when trying to delete the root node. I might be wrong, but I am fairly certain that this is due to too many destructor calls (each destructor calls up to 10 other destructors). I know this is suboptimal both space, and time-wise, however, this is supposed to be a quick-and-dirty solution to a the repeated substring problem.
tl;dr: how would one go about freeing the memory occupied by a very deep tree?
Thank you for your time.
