I'm struggling with two propositions in my algorithms book. I'm unsure how to proof this. The insertion is abolutely logical that it takes up to O(log(n)) recoloring and at most one restructuring (as the BT is already soerted befor its inserted). However, I'm unsure how to proof this. Can someone help?
I believe that this was first shown in :-
Tarjan, Robert. (1983). Updating a balanced search tree in O(1) rotations. Information Processing Letters. 16. 253-257. 10.1016/0020-0190(83)90099-6.