1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.