Video 2-3: Splay Trees

0:02 In the next section, we'll look at at spllay trees, uh, which are in a way maybe the ultimate solution to this question of how to adapt a tree to, um, an arbitrary access sequence. Uh, what I'm hinting at here is that there's a a big open research problem, whether they really are the final definitive answer or they're only close to it. um if you present them without this prelude of move to move to root I think a lot about their extra complication that they add becomes unclear and unmotivated but I I think now you can appreciate that just moving things to the root alone seems not good enough so what's wrong with um this move to root we'll we'll try to find out um let me start with the discussion um in this case first. So their split trees are are fairly uh uh popular for mostly the reason that they're relatively simple to explain. The analysis is a bit unintuitive how to come up with it but is easy to follow. They're also reasonably fast uh in practice um with a bit of a a caveat that uh yes it's pointer based like binary search trees. you pay for that a bit. There's a lot of uh indirection or indirect accesses and cache misses. Um and split trees specifically make things a bit worse like all these adaptive uh uristics. If you modify your data structure all the time, even if you just read elements that has an extra cost specifically in the context of uh um multi-core architectures. But that aside, um if if you zoom out a bit or or focus on the theoretical cost measures, they're fairly fast and also simple to implement. Um and what's what's standing out about them compared to many other data structures are remarkable properties about their robustness in the presence of many kind of structured axis sequences. And we'll see concrete examples what that means um at the end of this section.

2:17 Let's start with move to root again. Uh what could potentially be wrong in how we approach things there. Uh the key insight for spllay trees is to not just look at the parent node and rotate with your parent to be one step closer to the root. I mean move to root just does that rotate parent until you're you're all the way up there. uh the insight is to look at the grandparent as well and see how the tree is rearranged in the process of doing that. So here we have a as the node that we have accessed and um I'm uh assuming we're in the middle of this move to root uh procedure. So A already has moved up the tree a bit. It has two sub trees. Um, I'm highlighting both because A was in one of them before. It came up, it was rotated up from one of those two sub trees. And which one we don't know and which one shouldn't matter too much. One of the two it will will have been. Now we rotate with the parent. So that brings a here.

3:31 And then in the next step we uh rotate again with the new parent, the former grandparent. And that brings a here and leaves the sub tree like this. Okay.

3:45 And this case looks kind of fine in the sense that the new tree looks more balanced than the old one. Uh the sub tree A is moved down a level so that these guys aren't happy. But crucially the part where we started our search ends up higher in the tree. now is move one level up via these rotations. And that means if we keep accessing things from this from this sub tree also if we continue uh this this whole sub tree will become the new B and C on the next level up. So if you only have these kind of rotations, um every two rotations move these these two sub trees B and C one level up, which means over the course of an entire operation of moving A to the root, we half the depth of these guys, right? Every two steps a minus one starting at the at nothing means they're at half the depth afterwards. That's pretty cool.

4:51 Unfortunately, it doesn't always go like this. And that's where move to root um fails or suffers. This is not the general picture because if I go two edges up, it could be that one is a right one I'm the left child and my parent was the right child of its grandparent. the symmetric case where it's uh is instead of right, left, left, right is completely the same and the same picture will emerge. But it could also be that they're in the same direction. Now see what happens here. Uh we rotate with the first note that brings us one level up. Then we rotate with the next um one level up. Now this sub tree D, if that's where we came from, is very happy. It moved up two levels, but the sub tree C stayed where it is. So that's a slight hint for your for your exercise problems, right? Where you're trying to generate an access sequence for for move to root in the original case uh where you constantly have a high tree or high cost to access things.

6:00 You seem to have to use many of these kind of arrangements. So here doing two rotations might not move some of the sub tree up at all. So if it was bad before, it's still bad and it will remain bad if you're if things conspire against it continuously. Okay, that's that's the key intuition. Um this is not moved up at all. And there is an easy fix and that's maybe the surprising news. If instead of doing these two separate rotations with the parent, you do this double rotation where you just decide instead of having these three nodes slope to the right, I want them inversely sloped to the left with a at the top, I have achieved what I wanted intuitively that a moves closer to the root. H and where the sub trees go is predetermined. And now lo and behold both of the sub trees move up by at least one level. So I'll have the same result as before in this upper case. Every well here it's it's called one step but it's kind of costing twice as much. So again uh whenever a moves two levels up its sub tree where it came from moves at least one level up over the course of the entire operation will have halfed the depth of these guys at least.

7:29 Okay, that is part of the magic of spllay trees. That's why uh they do better than move to root where we uh don't have this lifting up of all the sub trees we came from. Again, crucially, inevitably, some sub trees are worse off afterwards. This point, this A is moved two levels down. Poor guys down there. But the important point here is if I repeatedly access things where A came from in these sub trees, these will be cheap now because they've moved up. That somebody has to go down when something goes up in a tree is inevitable. There's nothing we can do about it. But who goes up and who goes down matters. [snorts] Okay.

8:20 And that is what is behind spllay trees. They literally do that. Uh if you have this configuration or you're the child of the root already, you do a single rotate parent as in move to root. And then there's only this special case. If you detect that both of your parents and grandparent are sloping in the right in the same direction, you do this rotation, this double rotation instead of two single rotations.

8:53 Uh I should say to keep consistent with what other people call these cases. Um well, let's let's walk through the code briefly because I think that's the most clear description. uh display operation on a tree displaying at a node x means I'm making x the root afterwards. That's what the picture is supposed to say. X was somewhere down here before and then afterwards uh it's moved up to the root which also means its two sub trees essentially split the binary search tree into smaller and larger has to uh how do we do this? uh while x is not the root itself, we check its parent. If the parent is the root, we can't do a double rotation. So, we just do a single rotation up and then we're done. That's the zig case because the I don't know why they came up with this name. Uh that's what it's called in the original paper. If I'm not the root or my parent is not the root, then I have a grandparent.

9:57 So, G is the grandparent. Now I have this zigg zig. So I'm going in the same same direction if I move up. So they're both left or both right children of their respective parents. Then I do this special double rotation. Otherwise I'm in the zigzag case back and forth. Then uh I'm doing two normal rotations. Okay, fairly simple um code. Uh implementing each of these parent rotate parent a double rotate parent is not much. It's bending a couple of pointers and that's all you need to implement trees. That's why they're so uh popular also for competitive programming in these things because they're relatively clean and small in the code size.

10:48 Um, for today we might have to leave it with the operations. So, so far I've explained this mysterious display operation, but we want a proper dictionary in the end. So, how do we do insert? Well, it turns out all the operations that you ever would want on such a search tree, you can essentially do byplaying. Uh, for insert, you play at the element you want to insert. that's not going to be in the tree. So you're not going to find X at the or if you do then well you're done. Uh but in the interesting case you're going to find some different ver uh key in the root afterwards. Uh but the point is you found this while searching for X. So it was somewhere here where you would have wanted to insert X here and then this was the last node where uh your search path ended and you're going to play there instead of at X because X is not in in the tree.

11:49 That means this element that we have in the root is now the predecessor or successor of X in the dictionary. It's the closest in key space to X. Either smaller or bigger depending how you break ties. Um here let's say X is smaller. So Y is slightly bigger. Then I can make X the new root of the tree. Make Y the right child. Append this part bigger than Y to the to the right. And this becomes the left subtree of X. The left subree of Y necessarily is empty because there's nothing between X and Y. That's precisely from Y being the successor of X or the the ceiling of X in the the dictionary. So what we need is one play operation. We do a search for X and play what we found up and we rebend uh two pointers or three pointers. Then we have inserted X uh and we've inserted it at the root which display trees always want to keep the pre the last last touched thing in the root.

12:58 [snorts] Deletion is almost the same. You can again delegate everything to play. If you want to delete key X, you're playing at X. Okay. Well, if the root now is not X, then X is not in the tree and you do nothing. If it is X, then you delete this this node. And so you're left with two disjoint sub trees that you would want to join. And one way to join is to play for X again in the left subree. Say again what this means is you're trying to search for X and you find not X but say it's successor and so you play at this node I guess has to be predecessor in this case maybe you'd want to play to be consistent with the previous picture here uh my X was bigger my Y was bigger maybe I should have split the right sub tree to be consistent but You can of course implement it both ways. So you try to find X again in this left subree.

14:07 Uh what you find is not going to be X but you can display what you find to be at the root. That's going to be the maximum in this left subree. So null pointer here which means there's a a space where you can put the other node into. So you've effectively implemented the join operation that we've seen from trees and randomized binary search trees in the last unit. Um and you can naturally support this via play and split kind of is the essence of what spllay does. So that's also supported.

14:44 All of the operations that you could possibly do come down to spllaying. So that's convenient for the analysis because it means all we ever have to analyze is play.

15:00 Let's have a bit of uh a feel for what happens. So here's some animation now. I guess I need keyboard for that. Uh give me some numbers. Seven.

15:26 Okay. So now you see it searches and now it plays and you've seen this was the zigz case. Uh let's do something bigger again. Becomes the right child and it's going to move up. So now I'm I'm trying to build something very unbalanced. Okay.

15:42 I can uh I can do this by inserting things in sorted order. This is not going to go well for this play tree. But now what happens if I um if I eventually in um touch again something uh far down in the tree. So you can see how you could make the tree go really bad. Let's say we try to find seven. What should happen is that we essentially have the height of this this thing which now is one or well counting edges one two three four five six so it should be at three afterwards. So we're going to walk down until we find seven. And now we spllay up zigzag zigz. And you see uh okay seven is up here. It's a bit a bit hard to see. Now the left sub tree of seven is even further up. the halfing is an upper bound. But now uh some of the other things move further down especially the big keys but the tree overall I guess this is um can I go back?

16:51 Yeah. Um Okay, loop. And it's 1 2 3 four afterwards. You can't expect the height to be cut in half each time, right? That's impossible. There's a lower bound for login. Uh but if the tree starts out being very unbalanced, you tend to see this cutting in half for a while. Even though we've accessed some nodes and there's no guarantee that those further away from the touched node move further up, if it was in a very bad shape before, a very long chain, all of those move up by the magic of zigz Okay.

17:57 >> Uh, well, it's just four-digit numbers. I think it's that's that's the implementation of this animation. We say not the best. Yeah. Yeah. Okay. So then um you would have the the normal case, right? Um in this case you you can potentially generate more unbalanced things again as a side effect. Um in particular the 30 is far down now. Interesting. Yeah.

18:40 Let's uh include it here as well just uh so I don't forget. Well, uh there's probably going to be five other animations out there because splies are so popular. Um there's lots to be found. Uh this one I like because it's it's relatively clean and somewhat fast. Yeah.

19:05 So it's still sometimes a bit mysterious what some specific operation does even though every single step of course is clear.