How to quickly deallocate an entire subtree?

Question

I'm implementing an Alpha-Beta pruning (MiniMax) algorithm for a board game. I have a Board class with GetAvailableMoves(), PlayMove(Move x) and UndoMove() which all modify the game position inside the Board class. To implement Alpha-Beta I need a tree structure to keep track of the alpha and beta values of every position.

Since I'll want to calculate the best move multiple times in a game, I want to reuse the part of the tree that I already calculated and throw away the rest. If I implement the tree as doubly-linked nodes, then I'll have to call delete on every node in all subtrees that I want to delete. This can be very expensive.

How can I implement a tree that allows me to quickly cut and destroy an entire branch, possibly in O(1) time?

Answer 1

You can implement a datapool for your data. To get an allocated node you get it from the pool, and when you delete you put it back in the pool. Then you only allocate new memory when your pool is empty, and you only delete at the end of your runtime.

This will still need to move all the out of data objects back to the pool when you cut a subtree, so not O(1). But no delete calls.

Alternatively, if you have plenty of memory available and you just want a O(1) way to delete your subtrees, you can move the root of your subtree to a ToDeleteLater queue. And at the end of your run or whenever your program has free time, it can clear out this queue by running through trees deleting.

Unless the subtrees are huge, deleting honestly should not take too long, so instead of using pointers that you need to delete. You can implement destructors that take care of the deleting (RAII) So you don't have to write a complicated deleter.

Note: It is usually recommended that you post some code or more details so users can give more specific advice.