Delete on a very deep tree

Question

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.

Answer 1

Do you initialize the memory for the nodes themselves? From what I can see, your code only allocates memory for the pointers, not the actual nodes.

As far as your question goes, try to iterate over the tree in an iterative manner, not recursively. Recursion is bad, it's nice only when it's on the paper, not in the code, unfortunately.

Answer 2

Have you considered just increasing your stack size?

In visual studio you do it with /FNUMBER where NUMBER is stack size in bytes. You might also need to specify /STACK:reserve[,commit].

Answer 3

One option is to allocate from a large buffer then deallocate that buffer all at once.

For example (untested):

class CNodeBuffer {
    private:
        std::vector<CNode *> nodes;

    public:
        ~CNodeBuffer() {
            empty();
        }

        CNode *get(...) {
            CNode *node = new CNode(...);
            nodes.push_back(node);
            return node;
        }

        void empty() {
            for(std::vector<CNode *>::iterator *i = nodes.begin(); i != nodes.end(); ++i) {
                delete *i;
            }

            nodes = std::vector<CNode *>();
        }
};

If pointers to a std::vector's elements are stable, you can make things a bit simplier and just use a std::vector<CNode>. This requires testing.

Answer 4

You're going to do quite a few deletes. That will take a lot of time, because you will access memory in a very haphazard way. However, at that point you don't need the tree structure anymore. Hence, I would make two passes. In the first pass, create a std::vector<CNode*>, and reserve() enough space for all nodes in your tree. Now recurse over the tree and copy all CNode*'s to your vector. In the second step, sort them (!). Then, in the third step, delete all of them. The second step is technically optional but likely makes the third step a lot faster. If not, try sorting in reverse order.

Answer 5

I think in this case a breadth-first cleanup might help, by putting all the back-tracking information into a deque rather than on the OS provided stack. It still won't pleasantly solve the problem of making it happen in the destructor though.

Pseudocode:

void CNode::cleanup()
{
    std::deque<CNode*> nodes;
    nodes.push_back(this);
    while(!nodes.empty())
    {
        // Get and remove front node from deque.
        // From that node, put all non-null children at end of deque.
        // Delete front node.
    }
}