Video 2-8: §2.8 Balanced binary search trees

0:03 in the last little bit of unit two we'll talk about balanced binary search trees and this is really just a a teaser of what is possible and I suppose for many of you that will be just

0:27 one there we go um I'll have a list of things on the slide in a second uh so the way the way the question is posed as an open open answer thing we'll probably get uh a cloud of words without much of a sense of what percentage of people have seen it before but it's roughly a quarter in the class who have not done an undergraduate uh degree in in computer science and those will are unlikely to have seen balance binary search trees whereas everyone who has a computer science undergrad degree uh is very likely to have seen one variety of those um so I can pretty much predict it will be between 2/3 and 3/4s who have seen

1:30 it we will continue tomorrow tomorrow is that actually meaning we should stop now of course not I I'll keep the collection open we can have a peak peek at it um here's here's my list is probably not uh complete

1:55 um let me jump to this so uh AVL trees and red black trees are by far are the most widely used and widely known ones there's a few others and then there's a few more um but let me take um take a step back and uh what are we talking about here if you haven't seen this before so all of today I talked about o binary search trees are so cool because uh the operations are fast but the operations are only fast if the tree is not too tall and then I promised you if the keys come in random order in the insertions everything will be fine fingers crossed but if they don't come in random order it might be linear time so the worst case for a binary search tree if the insertion order is not controlled for in any way is is pretty poor instead we'd like to have log end time regardless of the insertion order in the worst case and that is possible um by various schemes of keeping the tree balanced where balanced is essentially defined as anything that has height at most log n in all the sub trees so um the the typical way to to do this is to impose an invariant on the shapes that are allowed we've seen an

3:14 invariant on shapes in the heaps chapter there the invariant was very simple every binary Heap shall have exactly this shape if it has n nodes we'll have to be a bit more lenient with binary search trees that will not be able to maintain such a strict in um but essentially AVL trees and red black trees and weight bounce trees these are all types of invariants on the shape of the tree uh that you can maintain so you have certain rules or certain extra steps for the updates insertions and deletions that reestablish that invariant just to make it concrete for AVL trees uh the invariant that we have is as follows if you have any node then it has potentially two sub trees and then the height of the two sub trees say if this is the left height and this is the right height then they may differ by at most

4:18 one that's the condition for AVL trees and this shall be true at every node so for every node this difference in sub trees sub tree Heights is at most one uh it might be a bit uh might need some thinking how to maintain this and this is uh another two hours or so of lectures to do it so I'll I'll not do it but you can watch the videos um which don't touch AVL trees they touch red black trees that's a slightly different variant um I'm not going to Define it formally uh it's it's a similar idea you keep some certain invariant uh and it's a little faster to implement that's why people um prefer it the Java library has red black trees same for the C++ STL python famously doesn't have binary search trees built in big shame but there's extra libraries uh there's a few others um there's another option uh instead of having these invariance on the shape that somehow need to be maintained uh there's other options that also can work uh I just want to throw these out because they're ideas that are interesting Beyond just binary search trees one is amortization which talked about this before for the doubling arrays amortization is the idea that some operations might be expensive but

5:35 if you have a long sequence of operations on average each operation is cheap uh Spate trees are the the prime example where a somewhat magic rule how to change your tree guarantees that if you have a long sequence of updates um they will always come out cheap there's actually a deep um open question open for 40 years in computer science that people are still still struggling with whether spat trees are the best way to do this kind of update I I can tell you a bit more about this offline if you're interested it's very fun and a really cool research topic uh but it's beyond the scope here I just think it's useful to know that these exist they have some some properties uh that are useful in that they don't need an extra they don't need an extra field for AVL trees you essentially have to store the height of these sub trees uh when play trees avoid that the second option is randomization uh what I said previously the height is usually good if the insertion order is random you can do better than that you can enforce the randomness so even if someone inserts things in a in a bad order it's still unlikely that you see a tall tree but you kind of enforce enforce the

6:53 randomness by explicitly doing random things it's very different and much more powerful uh again some of these are are useful in in specific scenarios like U skip lists are are good for concurrent data structures and so on but all a bit beyond the scope here just want to throw out a few things that uh if you feel that unit was a bit underwhelming because you've seen all that before there's a lot of cool stuff that um ties into this and that's worth looking at I one big slide to summarize what we've done in this module in this unit um talked about priority cues um on that side the binary heaps and we've talked about symbol tables or ordered symbol tables and binary search trees and here are all the running times that we achieve um so here assuming a balanced binary search tree any of the ones from the previous slide would do uh and if you look at this um you might wonder why people are at all excited about heaps because essentially all the operations that a heap can do like insert and removing the maximum uh a binary search tree can do that too in the same time so how would you do delete Max in a binary search tree you could do Min and Max in

8:22 logarithmic time and then you can do a delete afterwards logarithmic time so factor to slower find but apart from that if you just look at the Big O statements it's the same there's one exception and that's the first line the construction if you want to build a heap from a set of elements which are not in sorted order you can still do it in linear time we discussed this with the build little heets and do the sync where binary search tree you cannot do that and uh soon we prove why uh but that seems to be the only thing so you might come out of this of or some of you may have come out of an undergraduate algorithms class feeling a bit cheated why do people care about this priority queue abstraction if the best we can do binary heaps are not really faster than the general purpose binary search trees that can do that at the same time plus a lot of other operations and uh my Counterpoint to that would be the abstraction of a prior of a priority queue is still useful one it can express that you only need certain subsets of the functionality but two there are better implementations so um the reason you don't hear about those in most

9:42 algorithms classes uh is that they're incredibly complicated and so uh for the state-ofthe-art in research I know that there's there's a an educational implementation but not one that beats binary heaps on small inputs uh but in at least in theory it's possible to support the priority Q operations much faster so that only delete Max is logarithmic whereas insert and change key is constant time and that's even in the worst case and then for various reasons that we'll talk about in the Sorting chapter that's completely impossible for binary search trees so there's a clear separation between those two abstract data types and so um it can be useful to keep those around even if the best implementation you currently have doesn't seem to uh give you any