Video 2-8: §2.6 Balanced binary search trees

0:00 Introduction

0:03 in this last subsection on binary search trees i want to talk briefly about balanced binary search trees and these are a way to get around this problem that the unbalanced search trees had that we've discussed before namely that if the insertion order is is unfortunate the height can degenerate to linear and then all the operations are very slow i asked you um before here before we got started what the um what kinds of binaries balanced binary search trees you might already know and here are various examples but many of you have said none which means it's it's worthwhile spending a little bit of time discussing these that said

0:56 Balanced binary search trees

0:58 uh we don't have time to really go into the detail of any of these but i want to give you a rough flavor and i want you to be able to use these as a black box in a sense um if you ever need to know more uh the the lecture videos that i referred to earlier have um details about one one of these variants so what is a balanced binary search tree it is first of all it's it consists of two components it's um a rule how the shape of the tree can look like and this rule um is similar to what we had for heaps so remember

1:45 heaps binary heaps had this very rigid shape where the tree had to be an almost complete binary tree but it turns out for binary search trees this is too strict

2:05 in in a dynamic way if you insert and delete elements at random positions but you can get something that is slightly similar to this shape invariants that are slightly weaker but still guarantee you that the height is logarithmic in the number of keys and that's the best you can hope for as the the heaps demonstrated heaps the the heap shape the complete binary tree is um a binary tree of minimal height for that that number of keys so you cannot you cannot possibly hope to get better than this and the second important part is that there are rules that if you insert or up in if you insert or delete um elements in this tree that you can maintain this shape invariant

2:56 there's many such examples known the most famous ones are avl trees and red black trees slightly less well-known but um desirable for some other more specialized properties or the weight balance trees um because not so many people have seen this let me point out uh just uh that the type of shape invariants that these that these um bounce binary search trees have

3:33 so for avl trees we insist that whenever we have a node which has two sub-trees um then one of these subtrees might be smaller right and they will have two two heights there's a height of the right subtree and the height of the left sub-tree

4:01 and the the avl condition requires that the left and the right differ by at most one so the height of this of these two trees has to be essentially the same but we leave a little bit of slack if you compare that to the heap again here the height of if there was a note here then these two subtrees had exactly the same height there's only a few nodes where the subtree heights would differ by one now in avl trees we allow this for every single node we allow the height of of the left and the right subtree to differ in in in any possible node and you can prove that this is still um balanced enough to give you a logarithmic height in the worst case if you can uh if you can maintain this invariant so you have to make sure that this invariant this is also true when you add new elements to the tree or when you remove elements from the tree and there's clever rules based on rotations that manage to to do this but i won't give more details on that a similar idea is is red black trees

5:25 it also has some restrictions on how the tree looks like here the the invariant is a slightly more complicated so maybe i won't go into detail but there are

5:44 red edges and black edges as the name might suggest and we always have if you go down a path you can never have two red edges in a row so this is um this is not allowed uh you can have red edges but they must at least alternate you can have as many black edges as you want but no two red edges in a row

6:35 and the second thing is um so that's that's one condition and a second condition is all leaves have the same black height so by black heights i mean if you start at the route and you walk down the path to this leaf you only count the black edges and you ignore any red edges now uh that makes it obvious if you had an arbitrary number of red edges then this would be not very balanced but if you have uh just every other edge is red then that means the height of two leaves can differ by at most a factor of two and it turns out that again is um is good enough and this type of trees is is introduced in this book and in the videos i referred to so i'll just say look look at cedric and wayne's book for for more details on this there's a very nice way to to motivate them

7:55 this weird type of invariant but i won't have time to discuss this in detail today all right um let me put that a bit on the side so these are these are typical examples of

8:16 balanced binary search trees that achieve a logarithmic height and they can maintain this upon updates again in logarithmic time which means all operations run in logarithmic time in the worst case so that's the best you could hope for and it's it's this type of trees that are usually implemented in libraries the java library has red black trees the c plus plus library the new implementation has red black trees many many programming libraries have one variant of of these types of trees it's to the extent that when people say binary search trees they sometimes implicitly mean balanced binary search trees there are some there are some alternatives to these which are sometimes simpler and might have some cool additional properties but given that we've already spent some time on this i will completely ignore this now and i would love to tell you more about the about the fancy variants here but maybe that's for another time

8:55 Binary search trees vs binary heaps

9:30 i want to finally show an overview that compares binary search trees and binary heaps um we have here a bounce binary search tree and all the operations that it can support uh it's quite a quite a list right so we have the the get input that was the standard symbol table delete etc and then we had the ordered symbol table operations i put down logarithmic time for min and max because in the way the the easy way you get it uh like it's shown in in satchwick and wayne's book as well would give you logarithmic time but you can tweak it to be constant time by just remembering the minimum and the maximum that is possible in a binary search tree but this these are the listed times as as implementations usually do it and it's all worst case logarithmic time and let's briefly uh compare this to binary heaps again which have somewhat similar operations so you can insert things that's similar to put you can delete the maximum well we can get the maximum and delete so that's something binary search trees can do uh change key we don't directly have that but we can delete and re-insert and uh well maximum as i said with um some additional twists you can you can try to get it in constant time

10:57 as well so the question is if you see this is there any real point to be made for binary heaps and why have i shown you this there's a pedagogical reason because they're a simple data structure that you can describe in in complete detail but that's that's beside the point a second thing is the construction is indeed one difference you can construct a heap in linear time but you cannot construct a binary search screen linear time

11:35 the second point is the abstraction of a maximum priority turned out to be useful beyond inspiring binary heaps um as a matter of fact historically speaking it came after the fact people first invented heaps in a very specific context of sorting and then afterwards figured out uh this abstract data type that's behind this is actually useful beyond just this application and it proved useful for many other algorithms in particular graph algorithms and one other example that we've seen that we will that we will see and finally this uh better abstraction inspired people to dig deeper and after a long sequence of of research papers the final result is that you can support insert and also change key in constant worst case time with an incredibly complicated data structure that we will definitely not discuss in this class and i i think few people have um have understood in all detail but simpler variants um just the fibonacci heap get the same thing in amortized time somewhat simpler variants exist there that are also practical so going to the weaker abstract data type that offers only these operations as opposed to the full range that binary search trees have allows you to make some of these operations faster than would be possible in in the more general model so

13:11 having the priority queue abstraction is definitely a big breakthrough in computer science and therefore discussing heaps and how to implement priority queues is is worthwhile doing