I believe that wraps up the main lemma of Splay trees.
We went through the three cases and showed that 3(Mu(S)-M(x))+1 credits were enough to pay for the splay operation and maintain the credit invariant of the tree.
As we saw, the 1 is just for the case where there’s one last zig rotation.
At the end, we discussed a bit about why you do a zig-zig instead of a normal rotation and as we saw before, normal rotations don’t end up balancing the tree how we want.
Today we proved (most of) the main technical lemma of Splay trees which let’s us to say all the operations are amortized O(log n) time.
We’ll wrap it up on Friday.
More on our (my) favorite data structure, Splay trees. We discussed two approaches for splay(x, S): bottom-up or top-down.
We started the analysis and presented the main lemma. We’ll prove it on Wednesday so make sure to read over it in case you have any questions.
We covered the amortized bounds for the Binomial Heap today. Most of the class was spent talking about amortized analysis and how we can apply it to the insert operation. At the end, we discussed the fact that either the insert or the delete can be chosen to have amortized constant time, but not both. The choice is arbitrary, depending on your application.
Near the end, we also thought about whether the meld operation took amortized constant time, because every tree has been paid for, but one student noted that the NILs do not have a dollar allocated to them, so meld must be O(log n).
Don’t forget to work on the next homework over the weekend.