Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed.
The question is why is there the difference in number of potential rotations for these two operations.
To me it seems like these operations should be the reverse of each other but this difference in their properties suggests they're not. Why?
Adding one element to a set, versus deleting one element from a set, are indeed rather symmetric operations. You are right.
However, in the case where the sets are represented by a tree, the two operations turn out to be asymmetric. When adding an item one branch may be too long, and one well-chosen rotation will rebalance. When deleting an item one branch may be too short, and the local rotation needed to rebalance will change the height of the current tree, so we may be forced to repeat rotating at other spots.
So it seems that "too long" and "too short" are not symmetric for tree rotations.
There are various other set representations that are not symmetric with adding and deleting.
We can keep sets as unordered arrays. Adding is easy, just put a new item at the end. Deleting is slightly harder. Assuming we have actually found the item, it is removed in the array, and then the last item is moved to the open spot.
We can also keep sets as hash-tables, with open adressing. Then adding has a standard solution, but deleting is hard, as doing it in the naive way may make other items untraceable (when we have a method other than linear probing).
