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.
Today we covered Danny and Bob’s (Sleator and Tarjan, respectively) favorite data structure, the Splay tree.
But first, a bit about the midterm. It’s coming up on Wednesday. Manuel mentioned that he’ll have a couple short questions to test your understanding of the basic material from lectures, as well as a data structure design question. Other than that, all material mentioned in lecture at any point is fair game, even if it wasn’t written down.
A couple students mentioned that they want to share HW4 problems to help you study, so if you wish, comment on the HW4 post with your question. Try not to give the solution (or at least try to hide it) so that we can think about it first.
Now, back to trees. We covered the basics of binary search trees and found that they can actually be quite bad if we don’t balance them. But balancing is a pain, so its better if the tree does it on its own (just like malloc and garbage collection).
The magic in splay trees is the all-powerful Splay(i, S) operation, that brings the element i to the root of S, but instead of doing vanilla rotations, which we saw don’t help very much, we’re going to have some special rotations (elsewhere called zig, zig-zig, and zig-zag) that help balance the tree on the way up.
Today was mostly terminology so on Friday we’ll actually dive into the analysis of the operations.
Good luck studying for the midterm!