Video 2-15: Deferred Data Structuring Motivation

0:04 For the last part of our adaptive trees unit, we'll pivot a bit away from the few of splay trees where everything was accesses um and look at a different way how you can be adaptive. It's a good thing about adaptive, such an adaptive term it can mean anything you want. Uh so far everything has been binary search trees, which in particular means they're sorted. Right? So, what we can do in a binary search tree is we can somehow wish for certain items which we are expecting to need soon or often or something of that sort to be high up in the tree so that we can access them cheaply. Uh if you think about what we do for insertions, this helps not at all because uh we have to keep everything perfectly sorted.

0:55 And as long as we insist on having the items in sorted order, we have to pay to satisfy the sorting lower bound at the end of the day, which means insertions must most of them most of the time must cost log n at least. You can of course have sometimes cheaper insertions, but over a sequence of many accesses, as long as your data structure can sort by sometimes even called BST sort or splay sort, because the hope is that if splay trees are so good, then inserting things in a clever order will be cheaper than the n log n. And that is not a contradiction to this lower bound, that for some clever lucky insertion sequences, you get uh faster time. But for most of the insertion sequences, you have to have n log n total time. Because you can in general sort.

1:53 So, if we want to stick with the comparison-based model, we like the comparison-based model because it's so clean and general. You can of course try to do something if you have integers and uh I hope we get to that. Uh but that's a very different world. If we stay in the comparison based model, how can we possibly improve upon this? Uh if we somehow expect to have many insertions and these are in in the expensive operation. Um in particular for queries, if we give up on this sorted property, it seems all to go downhill from there. Uh it all seems to go uh seems to break the fast queries. Uh and that that is kind of true and inevitable. So, um what we'll have from here on is in a way an amortized setup where some of the queries are expensive because they have to make up for the work that you were lazy about before.

2:50 Uh on the other hand, if you have many insertions, this might be a worthwhile bargain. So, um it's also somewhat somewhat reason- reasonable in some applications, say. Uh I guess uh it's not the focus of the data structures to come, but in principle, many database systems are insertion heavy. They insert a lot and once in a while um you build indices and you get queries, but you have to be fast on the insertions primarily. And that's why people use log-structured merge trees and all these these kind of data structures. Uh but that's a slightly different focus. Here, my main point is why would you even want to sort if basically you're all just uh inserting a lot more. And in particular, if you have fewer queries than insertions, you can't even look at all of your all your precious elements. Okay.

3:48 That's the motivation. Um that's the goal to do something about that. Um before we get to a solution for that, uh, I'll take a detour to build up what we can possibly expect. And that's why we'll, uh, next time talk about this seemingly unrelated problem of multiple selection. Uh, which again, there bear with me for a bit. It'll all fit back together to the original motivation. Uh, it's this innocent problem that you're given some, uh, Uh, that's the single selection. That's multiple selection. Uh, you're given some elements that are not necessarily sorted, eventually our insertions. And you're given some queries, usually fewer than the total number of elements. Um, and these are ranks that you want to find elements for. So, in a way, the simple way to think about it is if you had the elements sorted in an array, then these are indices in that sorted array, and I want to know what are the elements at these indices.

4:51 But without paying the full price of sorting if possible. That's multiple selection, and you've seen the little brother of this probably in many, uh, places, where you only ask for a single rank, then it's just a selection selection problem, or maybe the median problem if the rank is in half. Okay.