0:00

Hello everybody.

Â Welcome back.

Â Today we're going to talk more about splay trees.

Â In particular,

Â we can tell how to implement your basic search tree operations using a splay tree.

Â So remember, last time, we had this idea to design a binary search tree,

Â where every time you queried a node, you brought it to the root.

Â And we know that simple ways of doing this didn't quite work out so

Â well, so we introduced the splay operation, which is a little bit better.

Â 0:26

Now, there's this problem with the splay operation that the way that the splay

Â trees are built, you don't actually guarantee the tree is always balanced.

Â Sometimes you'll end up with very unbalanced trees.

Â And when that happens, your splay operation will actually be very slow

Â because you have to sort of bring your node up to the root one or

Â two steps at a time, and it will actually take a while.

Â However, you'll note that if I have this long stretched out tree, and

Â I splay this leaf all the way to the root, we have rearranged the tree,

Â it's now a little bit more balanced than it was before.

Â And so, when you use the splay operation rather than to sort of rotate

Â to top operation, it's actually the case that you can't have a long

Â sequence of expensive splay operations.

Â Because every time you have an expensive splay operation,

Â it will rebalance the tree and make it more balanced.

Â And so, if you keep picking really unbalanced nodes, pretty quickly, the tree

Â will balance itself out, and then you'll have nice, short login time operations.

Â 1:31

But this does mean that we're no longer dealing with worst case time.

Â Well, we need to talk about amortized analysis, average case time.

Â And the big theorem that we're not going to prove today is that the amortized cost

Â of first 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.

Â 1:55

And we'll prove this later, but using it, we can analyze our splay tree operations.

Â And the basic idea is that, if you have to do a lot of work and

Â then splay a very deep node, we're going to be able to pay for that work by

Â the fact that the splay operation will rebalance our tree in some useful way.

Â And that will pay for it and so amortized cost will only be O(log(n)).

Â Okay, using this, how do we implement our operations?

Â So a splay tree find is actually very simple.

Â First we find the node in the way we normally would.

Â We then splay the node that we found and then return it.

Â 2:34

Pretty simple.

Â So how does the analysis work?

Â Now the node, remember, might not be at small depth.

Â It could be at depth D, or D could be as big as N.

Â 2:45

We then do O(D) work to find the node

Â because that's how long a find operation takes.

Â We then run a splay, so we did O(D) work, and then we splayed a node of depth D.

Â And so the amortized cost is O(log(n)) for this operation, which is what we want.

Â 3:04

Now, the idea here is that you're paying for the work again of finding this N

Â by splaying it back to the root to rebalance the tree.

Â And so, if the node was really deep, you did do a lot of work.

Â But you also did some useful rebalancing work,

Â which means you're not going to have to keep doing a lot of work.

Â 3:22

Now, there's a very important point to note here,

Â that it could be that we were doing this search,

Â you fail to find a node with exactly that key that you were looking for.

Â 3:32

But when this happens,

Â you still have to splay the closest node that you found in this operation.

Â Because otherwise, what's happening is your operation did O(D) work, but

Â since you're not doing a splay, there's nothing to amortize against.

Â You actually just spent O(D) work.

Â What you need to do is if you're doing this big, deep search, you have to pay for

Â it by rebalancing the tree.

Â And you have to,

Â therefore, splay whatever node you found, even if it does not have the right key.

Â 4:03

Okay, so that's fine.

Â Let's talk about Insert.

Â Insert, it turns out, is also really easy.

Â First, you insert a node in the same way that you would before.

Â And that's O of depth much work.

Â 4:20

Now to get deletes to work, there's actually a pretty clever way to do it.

Â If you splay your node and successor both to the top of the tree,

Â you end up with this sort of third diagram in this picture.

Â And you'll note that if we want to get rid of the red node,

Â all we have to do is sort of promote the blue node, its successor, into its place.

Â Because of the way this works out,

Â the blue node will never have a left child, and things will just work.

Â So the code for delete is you splay the successor of N to the root, you then

Â splay N to the root, and then we just need to remove N and promote its successor.

Â So we let L and R be the left and right children of N, and

Â basically what we have to do is we need to make R to become L's new parent and

Â L R's new child, and then set R to be the root of the tree.

Â And once we've rearranged a few pointers, everything works.

Â Now, there is one special case here,

Â which is what if N is the largest key in the entire tree, there is no successor,

Â you need to do something slightly different.

Â I'll leave that to you to figure out.

Â 5:28

Finally, let's talk about the split operation.

Â Now, the split is actually also very nice with splay trees.

Â The point is there's one case where split entry is really easy.

Â It's if the key at which you're supposed to split is right at the root.

Â Because then all you need to do is you need to split things into

Â two subtrees by just breaking them off the root.

Â 5:56

So what we're going to do is we're going to do a search to find the place at which

Â we are supposed to do our split.

Â Take whatever node we found, splay it to the root, and

Â then we're just going to break our tree into two pieces right at the root.

Â 6:09

So to see pseudocode for this, we're going to let

Â N be what we find when we search for the x that we're trying to split at.

Â We then Splay N to the root.

Â Now if N's key is bigger than x, we have to cut off the left subtree.

Â If the key is less than x, we cut off the right subtree.

Â And if the key is actually equal to x, well,

Â the x that we're trying to split is actually in the tree.

Â So, I mean, you might do one, or the other, depending on if you actually want

Â to keep the node in the tree, or maybe you want to throw it away, and

Â we just want to return the left subtree and the right subtree.

Â Now just to be clear, if we want to say, cut off the left subtree, all we have to

Â do is we let L be the left child, and we just have to sort of break the pointer

Â between our node and in its left child, so that they're now separate trees.

Â And we just return L and N as the two roots.

Â So that's how we do a split.

Â To do a merge, we basically have to do the opposite of this.

Â And the idea is that it's very easy to merge two trees together when you sort of

Â have this element that's in between them right up there at the root.

Â And once again, there's an easy way to do this with splay trees.

Â You just find the largest element of the left subtree, you splay it to the top,

Â and then just attach the right subtree as a child of that node.

Â And then you're done.

Â 7:35

So, in summary, splay trees.

Â Using this, we can perform actually all the operations that we wanted very

Â simply in an O(log(n)) amortized time per operation.

Â 7:46

And so this provides a very clean way to do this.

Â We left out some things in the analysis though.

Â So if you'd like to see really what the math behind

Â how we can show all of these things work, please come back for the next lecture.

Â