A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!
(Optional) Splay Trees: Analysis
Loading...
From the course by University of California San Diego
Data Structures
1526 ratings
University of California San Diego
1526 ratings
Course 2 of 6 in the Specialization Data Structures and Algorithms
From the lesson
Binary Search Trees 2
In this module we continue studying binary search trees. We study a few non-trivial applications. We then study the new kind of balanced search trees - Splay Trees. They adapt to the queries dynamically and are optimal in many ways.
Meet the Instructors
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Michael LevinLecturer
Computer Science
Daniel M KaneAssistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil RhodesAdjunct Faculty
Computer Science and Engineering
Hello everybody.
Welcome back.
Today we're still talking about splay trees and we're actually going to go into
a little bit of the math behind analyzing their run times.
So remember last time we analyzed splay trees and in order to do so
we needed the following important result,
that the amortized cost of doing O(D) work and then splaying a node of depth
D is actually O(log(n)) where n is the total number of nodes in the tree.
And today we're going to prove that.
So to do this of course we need to amortize, we need to pay for
this extra work by doing something to make the tree simpler.
And the way we talk about this being simple is we're going to pick a potential
function, and so that if we do a lot of work it's going to pay for
itself by decreasing this potential.
And it takes some cleverness to find the right one and it turns out more or
less the right potential function is the following.
We define the rank of a node N to be the log of the size of it's subtree,
where the size of it's subtree is just the number of nodes that are descendants of
N in that tree.
Then the potential function for
the tree is P is just the sum over all nodes N in the tree of the rank of N.
Now to get a feel for what this means if your tree is balanced, or
even approximately balanced,
potential function should be approximately linear in the total number of the nodes.
But if on the other hand, it's incredibly unbalanced,
say just one big chain of nodes, then the potential could be as biggest N(log(n)).
And so, a very large potential function means that your tree is very unbalanced.
And so, if you are decreasing the potential,
it means that you're rebalancing the tree.
So what we need to do is we need to see what happens when you perform a splay
operation, what does it do to the potential function.
Now, to do that, the splay operation is composed of
a bunch of these little operations, zig, zig zigs and zig zags and
we want to know for each operation what does that do to the potential.
So for
example when you perform a zig operation how does the potential function change?
Well you'll note that other than N and P, these two nodes that were
directly affected, none of the nodes have their subtrees change at all.
And therefore the ranks of all the other nodes stay exactly the same.
So the change in potential function is just the new rank of
N plus the new rank of P, minus the old rank of N and the old rank of P.
Now, the new rank of N and the old rank of P are actually the same,
because each of those had subtrees that were just the entire tree.
And so this is just the new rank of P minus the old rank of N and
it's easy to see that's at most, the newer rank of N minus the old rank of N.
That's not so bad.
Now let's look at the zig-zig analysis which is a little bit trickier.
So here the change in the potential is the new rank of N plus the new rank of
P plus the new rank of Q minus the old rank of N, and
the old rank of P and the old rank of Q.
So the new ranks minus all the old ranks.
Now the claim here is that this is at most 3 times
the new rank of N minus the old rank of N minus 2.
And to prove this we need a few observations.
The first thing is that the rank of N is equal to the old rank of Q and
that this term is actually bigger than any other term in our expression.
And that's simply because, I mean, both of these nodes what are their subtrees?
Well, it's N, P and Q.
And then the red, green, blue and black subtrees.
They're the same subtrees, the same size.
They've got the same rate.
But the next thing to note is that the old size of N's subtree and the new size of
Q's subtree, when you add them together, it's going to be the red subtree,
the green subtree, the blue subtree, and the black subtree plus two more nodes.
And that's actually one less than the size of either of these two big terms.
And what that says, when you take logarithms,
you can actually get that the size, the rank of N, the old rank of N
plus the new rank of Q is at most twice the new rank of N minus 2.
Because they're sort of half the size each.
And therefore, if you combine these inequalities together,
you can actually get the one that we wanted on the previous slide.
Now, the zig-zag analysis is pretty similar to this.
Here, you can show the change in potential is at most twice the new rank
of N minus the old rank of N minus 2.
Okay, great.
So now we perform an entire splay operation.
So we splay once, and then again, and then again, and then again,
all the way up until we finally have the final version of N that's the root.
And we want to know what the total change in the potential function is over
all of these little teeny steps.
Well what is it?
Well it's at most the sum of the changes in potentials from each steps.
The last one you have three times the final rank of N
minus the rank of N one step before that, minus two.
You add to that the rank of N one step before the N minus the rank of N two steps
before the N minus 2.
Then you add three times the rank of N two steps before the end minus the rank three
steps before the N minus 2 and so on and so forth.
And this sum actually telescopes.
The rank of N one step before the end there are two versions of it and
they cancel.
The rank two steps before the end,
there are two terms that cancel and so on and so forth.
And the only terms that are left is well you've got three times the rank of N at
the very end of your splay operation, minus the rank of N at the very
beginning of your splay operation, and then for each of these steps, for
each two levels the N went up the tree, you have this copy of -2.
So that's minus the depth of the node app.
And so the change in potential is just O of log(n) minus the depth,
which is minus the work that you did.
And note it's O of log(n) because the rank of n is at most
log of the total number of nodes in the tree.
And so if you add the change in potential to the amount of work that you did,
you get out O of log(n).
And so the amortized cost of your O of D work plus your splay
operation is just O of log(n).
Now, that shows there our splay trees runs an O of log(n) amortized time per
operation.
And if that was all you could say there is nothing really to be too excited about.
I mean it gets about the same run time,
maybe it's a little bit easier to implement.
It's a little bit more annoying because it's only amortized rather
than worst case.
Some operations will be much more expensive than
log(n) even if on average the operations are pretty cheap.
But another great thing is that splay tree has also have many
other wonderful properties.
For example, if you assign weights to the nodes in any way such
that the sum of all nodes of their weight is equal to one,
the amortized cost of accessing a node is actually just O(log(1/wt (N))).
And that means that if you spend a lot of time accessing high weight nodes it might
actually be much quicker that log(N) time per operation.
And so, and note that this run time bound holds no matter what weights you assign.
You don't need to change the algorithm based on the weights.
This bound happens automatically.
And so if there are certain nodes that get accessed much more frequently than others,
you could just sort of artificially assign them very high weights and
then that actually means that your display tree automatically runs
faster than log(n) per operation.
Another bound is the dynamic finger bound.
The amortized cost of accessing a node is O(log(D + 1)) where here,
D is the distance in terms of the ordering between nodes between the last access and
the current access.
So if say you want to list all the nodes in order or search for all the nodes
in order, it's actually pretty fast to do a display tree because D is 1.
It's a constant per operation rather than O of log(n).
Another bound is the working set bound.
The amortized cost of accessing a node N is O(log(t+1)) where t is
the amount of time that has elapsed since that node N was last accessed.
And what that means, for example, is that if you tend
to access nodes that you've accessed recently a lot.
So you access one node pretty frequently and
then they move to accessing a different node pretty frequently,
then this actually does a lot better again than O of log(n) per operation.
Finally we've got what's known as the dynamic optimality conjecture.
And this says if you give me any list of splay tree operations, inserts, finds,
deletes whatever.
And then you build the best possible dynamic search tree for
that particular sequence of operations.
You can have it completely optimized to perform those operations as best possible.
The conjecture says that if you run a splay tree on those operations it does
worse by at most a constant factor.
And that's pretty amazing.
It would say that if there is any binary search three that does particularly well
on a sequence of operations than at least conjecturally a splay tree does.
So the conclusion here is that splay trees, they're pretty fast,
they require only O of log(n) amortized time per operation which, remember,
it can be a problem if you're worried that the occasional operation might take
a long time.
But in addition to this, splay trees can actually be much better if your input
queries have extra structure, if you call some nodes more frequently than others, or
you tend to call nearby nodes to the ones that you most recently accessed, and
things like that.
But that's actually it for today.
That's a splay tree, that's why they're considered to be useful.
And that's this course, I really hope that you've enjoyed it,
I hope you'll come back for our next course and best of luck.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
