Video 1-14: Fringe balancing

0:03 There's one last point I wanted to get to. If you're doing these jump lists anyways and you spend linear time, uh there's a a cute little improvement that you can do.

0:17 So, in this last section, uh we'll talk about fringe balancing for binary search trees and the corresponding changes in in jump lists. Uh this is motivated from the question whether we could potentially, with any randomized data structure, ever get better than these random binary search trees. We've beaten that model to death now, I think. Uh but you know very well all its properties and it's a fairly balanced tree. The depth is 40% more than in a perfectly balanced tree where everything is completely balanced, which you cannot maintain. Can you even do much better with just randomization?

0:58 Uh one reason why you might be hopeful is that at least empirically, these worst-case balanced search trees, AVL trees, red-black trees, uh they have a worst-case height that is far worse than the expected depth of BSTs. Uh but if you build them randomly, they tend to have extremely low depth, very close to let's say say 1.01 * log n or so. And it's unclear if that's Uh I mentioned this as an open problem. Nobody could prove that this is the exact expected value, but uh empirically, it seems confirmed that they do very well. So, maybe it's possible, but uh we wanted to escape these uh hard invariants on on the shape. And one thing um one thing you you can do is try to pick a different model of the search tree uh shapes, one that has is even more balanced than these random binary search trees.

2:09 Um, for that let me take a quick digression. Um The first part you may know if you do quick sort on a list and you do a stable partition. So here is seven is chosen as pivot. Then everything smaller than seven is is to the left. And what's crucial here is that I keep the same relative order among those that are smaller. That's what I mean by stable partition. And same here for the nine and eight, they go right. Uh, if you keep doing this recursively on on the other sub lists, then you overall have sorted the list, right? If you did did read this left to right. But you've also built a tree, namely the recursion tree of quick sort. You've started with a call where seven was the pivot. Then there's a left recursive call where four was the pivot and the right one where nine was the pivot. If you connect these, you get a binary search tree.

3:04 You have to because everything on the right was bigger than the pivot, everything the left was smaller than the pivot. So it exactly satisfies the search tree properties. Uh, but there's more. Uh, if you take the same sequence of numbers and insert them into an unbalanced binary search tree. All right, you start with seven, that becomes the root, then four is smaller goes to the left. And so on, you just insert them with a standard procedure. Uh, then you obtain the same tree. It's this very same shape of the tree.

3:39 That may be uh known by now to you. Um, it's yet another way to get the random binary search trees doing simulating quick sort where you pick random pivots. Uh, but that we already know. One observation or one optimization in quicksort is to pick the pivot a bit smarter than just a random element. For example, you can take K elements, say five, and uh, sort those five elements and take the middle one. Then your pivot is a bit more likely to be closer to the middle than if you picked it uniformly. Uh, that you can do. So, what this looks like in in quicksort is, uh, first of all, this you take a a sample of elements, the first five in this case. And among those, you sort them, so it's 1 2 3 3 4. The middle one is a three. It's the median of these five elements. Now, uh, here I also have duplicate entries in the array. You can essentially ignore those. They're, uh, another aspect of this bisection that we don't need at this point.

4:46 So, all the duplicates of this pivot three are collected in the middle. Everything to the left is smaller, everything to the right is bigger. And then I recurse. If I have less than five elements, I'm going to do some base case sorting method. I don't have enough to pick another pivot. Here I I can pick one more pivot. And then I'm done. And so again, you get some sort of search tree. Uh, it's a bit of an awkward one because some of the leaves have more than a single element.

5:22 Uh, if you take the same sequence again, you can build a binary search tree variant. Uh, these are these fringe balanced binary search trees that simulates the very same process. And the idea is, um, is fairly simple. It's a normal binary search tree except that the leaves have a larger buffer. So, here for median of five, I have leaves that can hold up to five keys. And when I insert into such a leaf, I'm just collecting these elements until it's full. But once it's full, I'm uh finding the median in this leaf. That's the three. And I partition the the leaf around this median three.

6:12 And then I splice off this median as the new as a new internal node. And it gets two children partially filled from the previous uh keys already in this leaf. And then this is my root of the binary search tree. And the next insertion for the five starts here and oh, it's bigger than three, so it has to go to the right subtree. Okay. So, if we do that here, then uh there's a few more elements that collect in this leaf. Uh nitpick with equal keys inside the tree, they're absorbed. In the leaves, they're kept. Now, forget about that for now. And then I have another uh splice and then I'm done. And you see again, uh I get the same tree in both cases again. So, whatever we've learned, if you've learned something about median of K quick sort or you trust me that there's literature that anal- analyze these, uh you can apply the same thing to these French balanced search trees if they are a thing. Like uh you could of course build these. You could say I'm I'm doing a binary search tree and uh I'm not going to rebalance them. I'm going to trust that things will come in random order.

7:30 But I'm going to help a little bit by giving leaves a buffer for more than one element. And when that buffer is full, I'll take the median of those to promote it up. I could do that. Um it's not so promising because again, you rely on elements to come in random order.

7:53 >> What do you get from this? If you look at the literature for quicksort or literature for these fringe balanced search trees, I'm not going to do uh the math at this point, is that the expected depth goes down from our infamous two times ln n, right? The 40% more 1.4 times log base two of n, to this weird number involving harmonic numbers. So, that's the K plus first harmonic number, that's the T plus first this choice of parameters. Uh with with five, you get 1.12 instead of our 1.39. So, the tree is somewhat more balanced. And you get this from essentially waiting or choosing who becomes a subtree root by collecting a few elements in the leaves.

8:47 Fine. So, this is our alternative random BST model. Instead of random BSTs that just do unbalanced insertions, I'm slightly balancing things by collecting buffers in the leaves. But again, this is our hypothetical model that we would need to rely on randomness in the inputs to achieve. But the thing is you can simulate this in jump lists uh in roughly the same same way as we've done for the previous uniform case. Whenever it comes to choosing a jump pointer, there's my sampling range. Now, I'm not just uniformly picking the target, I'm picking say three targets if I want median of three, or I could pick five random elements, and then take the the median in terms of the distance, so the middle one among those. And pick this one in this case as the target for the jump pointer.

9:50 Uh this you can do uh we've been I've spent some time uh on doing this. Um including some full implementation and a precise analysis of how much you win from the slightly more balanced uh search trees. You essentially get this these better constants depending on uh uh your your analysis from uh median of K quick sort.

10:16 I'm going to leave it with that. Um but I think this is uh is a potentially cute extension. And it clearly shows that randomization is not bound to be this random binary search tree model. You can do something different. If you spend a bit more time in establishing the the random structure, you can lower the search cost a bit.

10:41 Uh a slight extension here is you can also play with the second parameter W that popped up all the time. By essentially saying if my sublist is shorter than 20 elements, I'm not going to bother to storing or drawing these jump pointers. It's fast enough to walk 20 uh steps in the linear search. Uh that's what this last part gets at. You can analyze how many jump pointers you need.

11:21 You could do the same approach with this more balanced median of K trick or random binary search trees. It's It's just nobody worked out the details. I think it's the same trick should work. Um but to my knowledge, this hasn't been explored. So, let me wrap up with the whole chapter on on randomized search trees. This time for good, we'll leave them behind. Uh we've seen various schemes to keep data structures in essentially good shape by bringing them to the random binary search tree shape or even slightly better. It's quite possible that in this rich design space, there's more to explore. There's no guarantee that the best solutions have been found already. In terms of the implementation, code size, and conceptual simplicity, I think these randomized data structures have a clear benefit. And sometimes, they also bring additional things like having this linear list structure below it. Um On the other side, some individual elements might still be deep in the tree.

12:30 And now, sometimes applications are not so uniform in how often they touch things. And instead, might have some favorite items, some some heavy hitters that are touched most of the time, whereas other elements are only searched for very rarely. And wouldn't it be cool if we somehow could make a profit from that? That our data structures, without having to know up front which elements are going to be hot, can adapt to them being accessed a lot. Uh in particular, when this is dynamically changing over time.

13:08 It seems that as long as we aim for a random binary search tree, we're never going to get there because they by definition bake in a uniform distribution.