Video 2-6: §2.4 Binary search trees

0:00 Introduction to BSTs

0:05 so welcome to binary search trees again binary search trees as i said get you the best of both worlds they're maintaining the list in a way so that you can insert at any position but you can also jump into the middle to do this binary search and that's a really ingenious idea and gives you essentially a dynamic sorted array that's what they make possible okay uh what is a binary tree we've seen these uh seen these before um maybe um yeah so let me first draw this a little smaller over here so we we draw nodes in a binary tree like this there are these little

0:28 Structure and definitions

0:52 circles that's a note and it has a left and a right child they can be null in which case i that means there's there's nothing but drawing nothing is not as explicit as drawing something so i drew something and then there's um maybe in the left chart there's another node that might have two null pointers so that's that's a binary tree every node has a left and a right child and they can be null plus uh a binary search tree has to satisfy the search tree property um that most of you remember it correctly it just means the key in the root has to be bigger than what's in the left subtree but smaller than what's in the right subtree

1:41 in java you might represent each node as an object and then i would have fields and usually you would need just three of them well maybe you need the values separately so you would store the key and the value so that was the x from the picture here now the value we don't really draw the values in the pictures because they're largely irrelevant you just carry these values along and if someone does a get or a put operation you store or retrieve the value but you don't really do anything otherwise with the values so we tend to not draw them in pictures and then left and right are two pointers to again such an object so let me remove the x here and then

2:47 maybe just show this again and make it a little smaller so these might be the left and right subtrees so left might point to this one and right might point to this one and then really these two

3:17 two children let's grab this one again so in a way this is very naturally a recursive way of thinking about trees every tree is a root and two trees right

3:46 so if you want um we sometimes well okay not sure if you find this useful it's empty or this uh so that's that's to say a tree and this is not really nice uh what i mean by this is this null element

4:19 uh a binary tree is either empty null or it's a node with two binary trees attached and that's a naturally recursive way to define binary trees and hence binary search trees and all the other ones okay good i think this is this probably clear let's look at an example here's a binary search tree and it's drawn in the way that i think everyone on this planet should draw binary search trees but it's not always done like this so i want to stress this a little bit i drew it so that you can go you can project the keys of the notes down and you get a sorted list you can always draw a binary search tree like this because well you just start with the root make a line and then just make sure that the entire left sub-tree is left of that line and the entire right sub-tree is is right of that line now you might think why would you sometimes not draw things like this uh it naturally happens if um a tree becomes big or so so if you draw a tree like this then uh the the left subtree is not entirely left of this line and that's that's why it sometimes

4:38 Search operations

5:44 is not possible to draw just project the keys down but in terms of thinking and working with the trees i think this is this is really what you should do okay let's do a quick example um

6:04 and do the same so this is essentially the same example that we've seen for binary search before um except that of course it's not perfectly balanced the binary tree so the comparisons would be different how do we find 69 we start at the root we compare the 77 to 69 and 69 is smaller so we go to the left 12 is much smaller so 69 has to be in the right subtree is also bigger than 57 so we go to the right and oh we actually found it so you return it and yeah you're happy um let's do one more example

6:54 let's try to find i don't know uh 83 you would start at the root again it's bigger than 77 so you go right but it's smaller than 85 so you go left but it's bigger than 80 and it's also bigger than 82 so you would go here but we reach a null pointer so we know it's a not in the tree whereas 69 was in the tree that's how you can find elements in a binary search tree and that's how you implement get you use find to find the position and it's either the node that stores the value so you return it or you find a null pointer then you can say no it's not in the tree

7:41 Inserting elements

7:44 what else can we do with binary search trees well it's only interesting if it's dynamic so let's see how we can insert a new element into a binary search tree

8:04 we try to find the element we're inserting that's also a good way to have a sanity check is the thing we insert already in the tree if so we should probably not insert it again but update its its value for example if it's a put operation so we find it uh using the same process it's bigger than 77 the 88 is also bigger than this but it's smaller than 97 so we end up in this leaf

8:41 okay that's good so what next now we have to make room in if this if this was an array we would have to make room in the array luckily it's not an array which means instead what we can do is just move let me flip back a bit we just move everything to the right a little bit to the right and we can do this just in the drawing there's nothing really happening from going from here to here is only me drawing the tree slightly differently but there's otherwise nothing happening and now we have the room for our 88 in the sorted list and we can insert a new note here and the only thing that's left is to connect it back into the tree there's only one position that any element can go to there's only one position in the sorted list so that's a unique place you will also notice that every insertion position so every position between two of the keys that are already in the tree corresponds to exactly one of these null pointers of these white leaves so let me maybe just show this for a few of them

10:03 so you always for every of these insertion positions there's exactly one leaf that you find okay and then you replace that nut pointer by a new node that's how you insert in a binary search tree that's really all there is to it now as a little side note what i'm presenting here are unbalan unbalanced binary search trees for now we will at the end briefly comment about the balanced version but i think it's uh for those of you who have never seen binary search trees before this will be challenging enough because it's a lot of material in in one session

10:49 i will comment on on how to balance these at the end so if if you haven't heard these terms before just forget it we'll come back to it if you do have heard these before these are unbalanced binary search trees so we only insert the element by replacing the null pointer and that's it

11:07 Deleting nodes

11:10 all right insert is fairly simple delete is a tiny little bit trickier because there's different cases that we have to distinguish but they're also not not too hard so let's first look at an easy case so basically delete again is similar to insert in that we first search the element that we're looking for and we do this with the same route to node traversal we're always comparing with the key in the node i will not show this again in in detail but uh you get the thing you get the idea so let's first look at an easy case we try to delete the key 11. start at the root go to the left because it's smaller go to left because it's smaller so here you found the node storing that key now notice that this is a leaf a leaf is a node that has no children only these null pointers if we have to remove a leaf well we just remove this leaf and we set this to a null pointer

12:29 slightly more challenging is when we have a unary note that's a note that has a single child that happens if we delete the 69 so again we do our search smaller than this bigger than this bigger than this there we found it

12:48 now here see it's it's a unary note it has a left child but no right child so what we can do there is we want to get rid of this one so we just rewire its parent edge to its single child edge so at the end of course we can pull this straight then the 63 just becomes the new right child of the 57 and we just short circuit this edge by removing 69. was also still easy we have to work a little harder for the other case that occurs if we delete 85 okay start at the root it's bigger than that oh there we already found it good so we want to get rid of this note but if i just delete this here i have a problem because there's two children now and i only have one parent edge that i could use to wire these two so i cannot delete these binary nodes easily what i can do is delete something else instead but ok i can't really delete something else instead the user asks me to delete 85 i can't do something else but i can do something down here i want to remove the 85 but that seems to be inconvenient um oh dear there's uh a typo yeah that's an

14:20 82. it's probably wrong on all the slides because i copy and pasted it so i'll have to fix that on the other slides as well that reminds me i should check the q a yeah thanks for noticing um

14:41 there's another question about this thing maybe worth showing um which is which so that's um going back to this the 69 uh movement on this on the other side if you delete the 69 you don't have any choice you only have really one option because the parent edge is the edge from the parent that goes to the right so the only thing you can do is take the single child of 69 and make it the right child of 57.

15:26 you could have a symmetric case where um 69 has only a right child and not a left child but that's actually the very same thing that also means you make that single child this right child of the former parent of 69. um hope that clarifies the question um if not we can come back to that

15:50 yeah thanks for uh flagging that mistake um i think you've seen it earlier um back to deleting the 85 what we do in this case is we can't delete this one conveniently in the tree but we can find um its predecessor

16:14 in the sordid list and uh well we'll we'll discuss this later in in the context of a different operation uh but really what you do is you go one to the left and then all the way right right right as long as you can so

16:37 and then write star which is my short hand of saying go to the right child as long as that is not null and that means you end up with the key that precedes the one we want to delete in

16:56 in rank order in the sorted order and now what we'll do is we'll delete this node instead but we move the 82 up into this node okay that's what we'll do i should actually do this i should use no i want to use gray it's not the same gray okay but in principle i should be able to write in red and you should be able to read this

17:32 okay it's not great but okay you get the thing so by by doing this swap and then removing this one instead we achieve the same effect we've removed the 85

17:53 we reduced the note that we delete to one that definitely doesn't have a right child because we uh followed right edges as long as there was no right child anymore so this this deletion here is always one of the the medium cases or an easy case as in this and as in this example so that's what you can always do find the note if it's binary swap the key with its predecessor and then delete the predecessor instead

18:29 uh there's the question if you could also go to the right and then left so instead of taking the predecessor take the successor that also works um i just state con consistent to the book but you can actually do both and there's also um a reason to do both in some sense um but i'm i'm not sure i will have time to cover this so as a shorter site because i won't have time to do it properly if you take unbalanced binary search trees and you keep inserting and deleting in this way where you always go to the predecessor and remove that you will create trees that are not nicely balanced over time because you always tend to make the the left subtrees shorter whereas the right subtrees continue to grow

19:29 so if you if you don't use a balanced binary search tree then many deletions can be can turn into a problem and and on that um in that sense it can be um problematic to uh always go to the same side if you go always to the right you have the same problem reflected so there's uh tricks where you say you always go to the deeper of those two notes and that that fixes this problem basically

20:02 but indeed that's one of the open research problems exactly analyze what happens in this situation with the better deletion is still not fully understood but that was a side note that is not really part of the the core material for this for this class but i'm happy to include a little bit of these extra remarks um for those who have seen this before and are bored by the core part

20:35 with these three cases you always get the job done let's uh briefly talk about how long these different operations take and let's start with the search which was used as a as a key component in in all the other operations as well before you insert you have to find the position before you delete you have to find that node that you want to delete you just have the key at the beginning

20:36 Performance analysis

21:07 so what search does is it always follows some root to leave path that's the way i drew it before now how long can this path be if you look at this you pay essentially for the number of edges that you can follow down

21:39 so any such path is at most as long as the height of the search tree and if you want to be precise you need a comparison at each node but the height counts the number of edges so you could say it's h plus one comparisons

22:05 and then you can get into the question um by comparison i mean one that tells you less or equal again um it's one of my favorite topics so i have a lot more to say about this than i can squeeze into 90 minutes so i'll not try not to that's uh that's the complexity of search you go down um the search path so if you have a good bound on the height of the binary search tree we have a good bound on the cost of search

22:49 well it turns out insert is essentially search you search down your path until you find um a leaf that's um one one way how a search can end and uh if you found this leaf you just stick the new note there and rewire one pointer

23:09 so it's dominated by the cost of search bounded by order h if h is the height of the search tree and finally delete and it turns out that's almost the same again it's also dominated by the search but it's a different search uh you have to search one once for the element that you're deleting and then in the case where we had the heart case the binary node we have to conti continue the search to the predecessor

24:05 but that's it so that's still bounded by the height of the search tree now uh it looks like we would like to bound the height of a search tree

24:25 Worst-case and efficiency

24:28 okay this is let's let's put it on the next side so the key question is what is this height of a binary search tree it comes as an innocent question but it's really a tricky one because the answer depends

25:00 if you're pessimistic and you look at the worst case then it's actually a very a very uh a terrible result the worst case for example is if you insert the keys in order let me illustrate this we start inserting key one then we insert key two well it's bigger than one so here's your null pointer that's where you stick the two and you make it the right child let's insert the three now it's bigger than one bigger than two okay okay it goes here now you insert the four and you see how this goes blah blah you always walk down the entire chain and uh your nice binary search tree is not really binary at all it's just a glorified linked list there's all these unused left pointers that buy you exactly nothing and all just point to null and so uh that's the worst case so if we have n elements the height is n well i should say n minus one if n is the number of keys and we count the number of edges so in in any way this is definitely theta of n practice the asymptotic bounds so if if we go back to this here um it would mean that the height is is

26:34 is linear so insert delete and search they all take linear time that's just as bad as the the poor binary the poor sorted linked list sounds sounds really bad

26:53 the good news is that this looks only that bad in very rare uh cases so the average case here i mean um that insertions come in random order i commented on that already a bit um the the analysis becomes easy in this case and we'll actually revisit this in the next unit so i will not um i will not comment on this um in in great detail now but basically what happens is that uh you get that the height is logarithmic in the number of notes in in the average case uh we'll get a little more precise about this um in unit 3 so let me leave it with that and it's actually not only the expected case so it's even

28:05 let me just add this here even with high probability now uh this phrase um this phrase has a technical meaning it's a precisely defined mathematical uh statement i don't want to give that definition or i don't want to really talk about that

28:36 we'll we'll come back to it it just says that you have to be super unlucky to get this this bad worst case almost all the time you can rely on the average case as long as something random is going on in your insertions you will be fine

29:00 i thought i had a slide on on that table uh maybe it's after this one i think this is a good point um to to recap so uh the basic binary search trees can support insertion as can support search insert and deletion in in logarithmic time in expectation if your insertions are not chosen by some adversarial villain then your performance will be very good logarithmic in the number of keys