Video 2-8: §2.8 Balanced binary search trees

0:05 um the last part just takes five minutes just really a remark so maybe we can squeeze that in unless someone has to run for a slot right after this um

0:22 if you've seen something like this before so maybe just on slido now if you've seen any way of balancing binary search trees maybe it can be more specific and say what ways so uh what types of yeah that's one

1:10 okay many many i've seen red black trees it seems and many have seen none and if we uh sum up all the different emoji we might get more more for none than what we have

1:32 so this is something you can treat as a black box for this class and because we're running out of time um i'll i'll skip explaining the examples the basic thing what this is about is we had binary search trees if insertions come random and we don't have deletions the the height stays logarithmic but in the worst case it was linear which is terrible but there is a way to enforce the height to stay logarithmic there are tricks and balances and here are some examples that shown up so these are avl trees or red black trees is one of those as usually shown there are many others indeed and many more ways to get this but in short as a black box concept you can make a binary search tree worst case height logarithmic by just making the insertions deletions a little smarter and enforce a certain invariant and these are all different invariants i explained this last year in a little more detail if you're interested you can check out the video from last year

2:43 for us all that we need to know is that it is possible we won't need how and here's a quick summary of of what we've seen in this uh in this section uh especially the the more interesting data structures heaps and binary search trees so binary searches can do a lot more operations and indeed they're in a sense a superset of the operations of heaps so you might wonder why do we need heaps if a binary search tree can do all of that and more and the thing is there's a few operations where binary search trees are slower one is the construction you can do it in linear time for a heap and for a binary search tree you cannot

3:31 the abstraction of a priority queue is like when we talked about bags as a restriction of of stacks or queues it's sometimes useful to express the intent that you only need a priority queue and not a fully sorted fully ordered symbol table and so people found that if you stick to this abstraction of a priority queue you can actually get both insertion and change key to constant time even in the worst case so this is a fairly recent results less than 10 years ago i think a very celebrated thing that settled a long line of research so um even though binary search trees in the way that we implemented them are not much better than heaps there are better heaps at least in theory and some also in practice so it's a useful abstraction