More specifically, an AVL tree. Is it possible? I'd like to do it, but I'm thinking the undeleted nodes may be problematic to manage with the rotations.
I have one that works normally, but I'd like to use this one with lazy deletion for something else.
If you want it to remain "balanced" with respect to all node (including the ones marked deleted) you don't have to do anything--you're already there.
If you want it to remain "balanced" with respect to the set of undeleted nodes--the question is why? The whole point of balancing is to prevent run away (linear worst case) searches and that depends on the nodes, not their deletion status.
What exactly does not deleting mean in the context of an AVL tree?
It could mean you do no work on deletion, which is to say, you don't update the tree at all.
This will cause the tree to rebalance incorrectly, because the upward scan for balance factors will be working with incorrect balance factors.
It could mean updating the balance factors but not balancing.
This means you would end up, when you did decide to delete something, with balance factors greater than 2 or smaller than -2; which implies multiple rotations to correct. The problem here though is that you can no longer know, upon a rotation, whether or not you've eliminated a subtree depth; because although you know there are say 3 subtree depths too many on one side, you no longer know it's exactly one element which is causing each level of that extra depth - something you normally know because you're adding or removing single elements at a time - so you have no idea how many rotations you need to do. You might do three rotations and only have lost one subtree depth, because there were two elements at that depth. In fact, how would you even be able to know which elements to rotate to get at the necessary elements? they wouldn't necessarily all exist in the path from your chosen delete element and the point where the balance factor is 3.
I'm not certain, but I'll go out on a limb and say lazy deletes breaks AVL as we know it.
Why would you want to delay, anyway? the whole point of AVL is to amortize the rebalance cost across each add/delete so you stay at O(log n) - why build up rebalance debt for larger, less frequent rebalancing?