I did a test on AVL trees. One question introduced an undo function that can only be called after an insertion into the AVL tree, and which removes the previously inserted node. I'm allowed to change the way I insert a value as long as it still has O(log n) time complexity.
The question then was: what is the best time complexity for this undo function, and why?
I thought it was O(log n) because normal deletion could require rotations for every node in the path from the root to the node inserted. But apparently this is not the correct answer. What am I missing?
Best Answer
The undo action can be done in O(1) time, but indeed you'll have to change the way you insert a node.
We know a few things about the last inserted node in a standard AVL tree:
It is a leaf. Even if the insertion resulted in one or more rotations, these rotations will never append a child to the newly inserted node.
It can be removed without rotations (even if rotations were applied at the moment of insertion).
But, it could be that the insertion implied a balance factor change along all nodes on the path from the root to the inserted node (in the worst case), so we would still need to revert those balance factors if we did an undo operation.
Although the first two points hint at a O(1) undo operation, the last point means we still have a O(logš¯‘›) worst case.
Because of that last "obstacle", I would suggest the following approach:
When you insert, don't perform any rotations for it, and don't adapt any balance factors for it. Postpone these balancing actions until you perform another insertion or deletion, and at that time first perform the postponed rebalancing (if any), and only then perform that next action (in the same manner when it is an insertion). This means you add a worst case time complexity of O(logš¯‘›) to an action that itself is also O(logš¯‘›) in the worst case, but O(logš¯‘› + logš¯‘›) is still O(logš¯‘›), so we can perform this postponed rebalancing without impacting the time complexity of the action itself (the next insert/delete).
When you insert, remember where you inserted it (i.e. remember the parent node reference, if any). If you already had remembered an insertion point (for a potential preceding insertion), overwrite that information.
When you delete, remove the information mentioned in the above point, so it will not be used for a subsequent undo operation -- which would not be allowed).
Now an undo is easy: confirm that the last action was an insertion and then just remove the inserted node. Because we had postponed any rotations and calculation of balance factors, there is nothing more to do. This is now a O(1) operation.
When you search a node and it happens to be the node that was inserted with the most recent action, then you'll potentially have to traverse one more node than you would have had to do if the tree had been properly rebalanced. But this does not affect the time complexity of the search operation, as O(logš¯‘› + 1) = O(logš¯‘›).
Concluding: with this type of "postponed rebalanincg", you can implement an undo with O(1) time complexity.