Video 2-9: Dynamic Optimality I: The Splay Tree Conjecture

0:03 In the next section we'll bring this notion of competitive analysis to splay trees and you'll see it has a very very natural um meaning there. Uh and interestingly um if the question on splay trees predates the term. Um I'll I'll come to the formulation there. Uh as I said, for data structures it's very natural to assume some online scenario where you don't know all the future queries and updates. Uh so having a binary search tree that has to serve accesses, updates, all the operations that splay trees support online, that's the natural example of how how we use these. Um let me stress here that basically you've seen for the updates all that counts is the splay operation. And basically by modifying the potential a bit we got away from really dealing with updates in any special way. So for this chapter let's entirely focus on read accesses. So you only can read out the value of an element and you splay it to to the root if you use a splay tree. That's that's all we're going to do.

1:14 Uh but remember from yesterday this this is whole bunch of uh clever clever upper bounds for certain access sequences. You can guarantee good running times and so on. Uh so accesses are already quite interesting. And that clearly splay trees are one possible online algorithm. Um in a way specifically designed to not have to deal with the future and also not keep much knowledge of the past to be honest. Okay. How can we um apply competitive analysis to this this realm of um maintaining binary search trees under under such accesses? Uh we want of course to compare it in competitive analysis to some optimal offline algorithm. But that is easier said than done because you somehow need to fix what this optimum is allowed to do. And um there's clearly things we wouldn't want it to be able to do. Say uh take all the keys and throw them into a hash table or so. That clearly would defeat the purpose.

2:22 Then it's no longer a sort maybe it wouldn't even work because it's not sorted. Uh also if you know the access in accesses in advance and you know exactly when you need something again you're going to build an entirely different data structure. Probably just an array sorted by the next access time you just step through and you rebuild that. That's a lovely exercise problem. Good that I think of it now. So [snorts] if you don't restrict what the optimal algorithm the offline algorithm can do uh you're comparing against something uninterestingly powerful.

2:59 So we do get the entire access sequence in advance but we cannot do arbitrary computation with it. And here the model that gives you a a clean interesting well-defined and kind of cool problem is that also the offline has to maintain a binary search tree. But that's only that's essentially all the restrictions. So um the model is you have a binary search tree over the elements that we talk about at any point in time. And you also have a finger that points to some node. And this is what all the algorithms that we've looked at so far kind of do. You start with your finger at the root. You move it down to some search path. Maybe you do some rotations. Maybe you go further down the tree if that sounds useful. That's what you're allowed to do. A bit more formally uh each operation can be exactly one of five different things. I have my finger in the tree.

3:58 I can move the finger to uh one of the children or the parents. I'm assuming here that we have parent pointers to make it easier to to do that. Or you can rotate the edge of the parent edge of the current node. All the rotation-based algorithms that we've seen fall into this uh this model. Yeah, you can reformulate them to be in that model. And the only other thing we can do is find. So if we're if we promise uh that we've found the we're trying to access I can say find then I'm forced to be at the right node and that ends the current search and puts the finger back back to the root. So that's the the assumption is that apart from this binary search tree you only have a a pointer to the root and you don't maintain any other shortcuts into the tree or so. Again, remember this is this is the model for what opt is allowed to do.

5:01 We can be more lenient in what our online algorithms are allowed to do. Uh maybe it's still interesting but for the optimum offline we should be careful not to allow it too many things. Otherwise it will be very hard to compare against this. And you'll see even this is um is tricky enough. So in a way every anything um you can do with these operations opt is allowed to do which means opt simply has to take an access sequence and find the best long sequence of these uh five options, move to one of three targets, rotate or find and output this sequence. Then you could act that out on a binary search tree to find hopefully uh the the accesses served correctly.

5:51 Uh and clearly the cost model is easy to define here. It's just the number of operations. So each of these five things has unit cost and the optimum is the shortest such sequence, right?

6:07 Now with that we can formulate the the problem that this is getting at. Uh and indeed because of these these cool properties that splay trees have already the original publication contains this a bit wordy conjecture. Let let me read it briefly. So that's the dynamic optimality conjecture. Consider any sequence of successful accesses on an N-node search trees on the model we have. Uh let A be any algorithm that carries out each access by traversing path from the root to the node containing the access item at a cost of one plus the depth of the node containing the item. So we pay for touched nodes. And that between accesses performs an arbitrary number of rotations anywhere in the tree at a cost of one per operation. It's even a bit more generous. Uh it allows rotations outside of where you visited the tree. I'll I'll come back to that. Then the total time to perform all the accesses by splaying is no more than this big O of N plus a constant times the time required by algorithm A.

7:13 Okay. Uh the reason why they spell this out is that the same I mean this Robert Tarjan was also involved in this and the competitive term competitive ratio wasn't a thing at the time. Today we would just say splay is one big O of one constant competitive against the offline algorithm I've defined on the previous slide.

7:40 Um that's a a bold statement, right? Uh because you're saying this consider any sequence of successful this is a for all statement. For all access sequences splay serving with a splay tree the access sequence is up to constant factors and maybe a plus order N term. So if the access sequence is very long this matters not at all. So just a constant factor remains. Splay up to this constant factor is as good as any thinkable search BST algorithm. And because the sequence is fixed this is includes offline algorithms. Even if you know the sequence in advance you can't beat splay by more than a constant factor. That's a very bold statement and unfortunately we are very far from answering whether this conjecture is true. Uh we don't know if any algorithm is possible that achieves this. Let alone let alone splay or let alone one that we can put our hands on. And uh it's open whether splay is little O of log N competitive where log N competitive order log N is kind of trivial.

8:55 Uh well as the slide says once my pen works again. Just wanted to underline this. Uh the access sequence of M accesses needs time M in total. It's constant per access. That's clearly a lower bound for optimum. And any static balanced tree even if you don't change the tree at all you just arrange things in a balanced way that already gives you M times log N. So an big O of log N competitive ratio you get by any balanced search tree. So basically this this open problem here says we know nothing about splay with respect to competitive uh ratios. The trivial upper bound is all that we know and nothing better than that really is known.