Does inserting and immediately removing a node change a red-black tree? I have the following problem:


  Does inserting a node into a red-black tree and then immediately deleting it always result in the original tree? Prove that it does or give a counter-example if it does not. Does deleting a leaf node from a red-black tree, then reinserting the same node always result in the original tree? Prove that it does or give a counter-example if it does not.


I have used several demos, but none of them have made much sense to answer this question. I havent been sure as to yes or no, I am still new to binary trees.
It's not obvious that there is a "correct" answer to this question, as there are multiple insertion/deletion algorithms for red-black trees. Tarjan explicitly explains this in his book Data Structures and Network Algorithms, where he demonstrates (in section 4.2) update algorithms that require $O(1)$ rotations and references algorithms that require $\Omega(\lg n)$ rotations.

This is also mentioned in Hize's "A Simple Implementation Technique for
Priority Search Queues" and Driscoll et al.'s "Making Data Structures Persistent"