0
$\begingroup$

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?

enter image description here

$\endgroup$
0
$\begingroup$

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. 
$\endgroup$
  • $\begingroup$ No idea how to use this sorry. $\endgroup$ – raviolican May 11 at 12:00
  • $\begingroup$ It is the reference that contains the original proof. $\endgroup$ – Jon Guiton May 11 at 12:06
  • $\begingroup$ do you have a link to the paper so i can read it $\endgroup$ – raviolican May 11 at 12:07

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.