Actually, I'm not doing anything, this was a purely hypothetical case constructed to create an example of where it could make sense to allocate in a destructor(though in the end, with the other post, I noticed that it probably wasn't needed).
Anyway, no, it's not about rebalancing. Even on a normal tree removal of an object is an O(h) operation(with h equal to the height of the tree). In an rb-tree, being it a balanced tree, the height of the tree is (a*log(n))(with some "a" number which now I don't remember). Thus the removal of all the n elements becomes an O(nlog(n)) operation. If instead you do a find_minimum() followed by an inorder visit from there, you're gonna have a delete_tree() operation which is O(n).