A problem that may be related is one where I have program to show the changing process trees running on a computer, as a real-time animation.
In that context each level of the tree generally goes from narrow to wide. So to keep regularity, you could keep larger subdivisions around for a little while before reducing them.
For example. I have at the top level 1 item. Next level 3 items, next level 10 items. Suppose an item at level 2 and 3 children of that disappear. You could keep the positions they are at still around but now just as invisible items and lines so that nothing else changes. So visually it would be as one expects, they just disappear. Then slowly over time that gap could get closed up. But in my case, often a new set of processes would take its place. I'd have that then in the space occupied by the gap.
The paper describing my situation and solution is http://motif-pstree.sourceforge.net/xps-full.ps
The main idea is laying out a grid for each depth to put stuff in and keeping that around for a little bit of time.