Video 2-6: §2.6 Binary search trees

0:00 Intro

0:03 in the next section we want to see how we can make binary search dynamic and what will be the solution for this is called a binary search tree so here's the question i already started before most of you already had a chance to answer and because it's it's quite clear um let me also lock it now and um show the results so the second is is the answer i was after

0:32 Clicker Question

0:37 a binary search tree is a binary tree as well so the first answer is not wrong but it's uh it's not all there is to it this one was a heap so uh peep ordered trees are no longer a thing in this chapter and yeah this this last point um i should have maybe discussed this uh when we discussed the question for heaps as well so there's there's the same term heap used for different things in computer science as you may be aware binary heaps is the data structure we discussed in the last section where we can do insert and delete the max and these things there's also a heap area in in programming languages where you can dynamically generate objects whenever you call new in java you generate an object on the heap in python pretty much everything is an object and they're all allocated on the heap it's just a separate piece of memory that you can allocate chunks of it and use it for objects it has nothing to do with the heap data structure in particular the heap space is not organized like a binary heap this it's just a very generic term something to be aware of okay what is a binary search tree then it is a binary tree so every node has

1:52 two children and it has keys and the important property is spelled out here and again here so the nice red box is what you should keep in mind if you have a root of the binary search tree it has a certain key then this key must be bigger than everything that's in the left subtree and smaller than everything that's in the light in the right subtree and you can you can also phrase this just about looking at the children and then recursively it holds for the entire tree

1:57 Binary search trees

2:23 i think the way to the way you should think about binary search trees is really this is binary search make made dynamic so that you can change the array and because we can't really change the array what we instead do is work with pointered structures so the typical way to represent the a single node in a binary search tree would be to have some object that has a key and a value and two pointers one for the left and one for the right child and then well we can have many more point many more nodes i didn't copy the box

3:18 so maybe this has a pointer to those two guys so the left points to this and the right points to this and then these can have again more and more children etc until at a certain point the pointers are null which means there is no further children okay i think um in one way or another i hope you have seen this

3:44 you could implement it exactly like this for example in python here's an example of how i want you to think about binary search trees so in the computer it's just an object a collection of objects with pointers and there's left and right child pointers we don't usually need a pointer to the parent although some implementations do this because it makes some operations easier or more efficient in some cases for what we discuss in this class you don't need them you only need pointers to the to the children and i really want you to think of a binary search tree always drawn like on this picture if you have the root it projects down its key onto a certain x position and then the two subtrees shouldn't overlap in x direction if you do this at all positions then what you project down is the keys in sorted order now this is just our imagination in the computer these are just pointers and there's no specific way to lay them out but if you draw them like this most of the algorithms become really intuitive so always do it like this i wish all books would do it like this but alas so let's do an example how you can find elements in this tree say 69

3:50 BST example & find

5:15 you always start at the root because actually the root is the only thing you really have a pointer to so the data structure consists of these of these objects and the pointer to the root so you start at the root now you compare your key 69 to the key in the root and of course this is smaller so you follow the pointer to the left because remember binary search tree property all the keys on the right are bigger than the root key so they cannot possibly be where the 69 is stored okay now we find 12 is too small so this time we follow the right pointer and again this is too small so we follow this one and here yay we found 69 so we would in that note remember we only we don't only store the key we also store a value so we can return the value and return it or do whatever we wanted with this operation one more example where the search fails so suppose we find try to find 83.

6:23 we start at the root it's bigger than 77 so we go right this time it is smaller than 85 so we go left it's bigger than 80 and it's bigger than 82 and at this point we reach a null pointer so that means there is no further thing in the tree there is nothing between this range so the last time we went left and the point where we go right here means this is the range that we know there's no key between 82 and 85 in this in this dictionary so we can return to the user sorry that key doesn't exist in our in our dictionary at this point okay i call this operation find because it's it's used as a subroutine in the other operations as well but one thing you can implement with this is get the adt operation

7:19 all right if you if you think about this what we're doing here this is really a binary search on this array down there just that we don't always jump exactly to the middle but we jump to wherever the route happens to be but still in in either case where we made a comparison we excluded one part of the tree that's the same as in binary search

7:45 BST insert

7:47 now the interesting part about binary search trees is that we can change them we can insert things without copying array elements over so let's briefly see how we can do that suppose we want to sort insert 88

8:01 the first thing we do is try to find it that's the same procedure as before we only allow to insert it if it's not already present and in this case we end up at this leaf so find says it's it's all right 88 is not already in the tree so you can go ahead and insert it so that's the first step you know this lists leave now and in a sense you're just replacing this null pointer with a new node but to draw it nicely i just first swap this over so this is just moving the node out as you can hopefully see leave some space then we put in this new node and link it into the tree okay

8:47 good that's insertion and last thing is we can also delete elements that's the the most tricky operation of the three so uh it has different cases let me just briefly run through those again i think many of you will have seen this but if not this should be should give you enough of an idea to understand how these work if we want to delete 11 well first we search for it

8:54 BST delete

9:22 same as always uh in this case 11 is a leaf both children are null so we can just get rid of it and that's it okay so we set this pointer to null and remove delete this node that's all we need to do to remove 11. a slightly harder case is

9:48 if we end up at a node that has one child like in the case of 69 in this case we can't just remove this node because then we would leave this subtree dangling in in the in thin air what we instead do is we rewire the right edge from the parent to point to this single subtree that is now parentless so the the parent of 69 adopts this subtree

10:18 then that's also an easy case because it's just a local change the most tricky one is when we want to delete a binary node because in this case if we got rid of this there's two subtrees that now need a parent and we kind of don't have two pointers left we only have one parent pointer to spare so the standard way to solve this is to find the predecessor in the tree of this key which means you want to find the first one that's to the left and you can do this by once

11:00 once going left and then go right as long as needed until you find the null pointer that must bring you to the predecessor key and so what you do then is you take this note sorry take this one and just move the 82 into here

11:30 and then you have to to recursively delete this node but that by definition has a single child at most because the right child was now so this is never again the tough case it might just be the the medium case again and in this case it's actually a leaf so nothing happens okay uh that's how you can also remove nodes from binary search tree again and let's briefly see how expensive all of these operations are and then i promise we'll do a little break so for search or operation get in the adt

11:57 Analysis Search

12:14 all we needed all we did was the find operation and remember find started at the root and made its way down the tree until we arrive at some point where either the search stops because we have found the element or we reach a null pointer

12:49 the cost is pretty much the height of the binary search tree it's never more than the height because that's the longest possible path you could have and the number of comparisons is is the length of the search path maybe plus one for finding the the actual key where you get

13:29 and so again this is this is at most the height plus one um and so all we can say for now is if h is the height of the tree then the cost of finding an element or finding a node in the tree has caught has cost at most uh h or order h big o of h if you want to be less precise for an insertion remember how insertion worked there were two steps first we find the position where we want to insert and then we only really create a new node and wire it in so the second step is just rewiring a few pointers and allocating a new object but that's a constant amount of effort it doesn't depend on how big the tree is and the first step is again find

14:28 so again the cost is essentially dominated by the height of the tree and for delete if you think about it again a bit more carefully it has these these separate steps that say the hard case happens you search some some note then you find it then it's a binary node so you have to further find its predecessor but again if you take the two fine steps together they both together find uh give a path from root to some node to some predecessor node and that's again bounded by the height of the tree because you can't go further down

15:10 so it's it's two times fined but they actually together are one path and more constant effort because you rewire pointers and delete a note but again the effort is essentially bounded by the height and so here i summarize this nicely in a table again the construction for binary search trees unlike for heaps we don't know anything smarter than inserting things one after each other

15:25 BST summary

15:39 and all the other operations are bounded by the height except for the very simple ones so that brings us to the question what is the height of a binary search tree and unfortunately in the worst case it's really really bad you can see this if you sort if you insert the elements in sorted order

15:50 What is the height of a BST?

16:07 you would always find the next insertion would always go to the right most elements say we try to insert five here it's bigger than this bigger than this bigger than this bigger than this bigger than okay here's the null pointer so here it should go

16:21 and it's clear you can keep going like this so in this case the binary search tree deteriorates to a linear linked list that's really terrible so in the worst case the height can be linear so why all the fuss why do people still like binary search trees there's two answers but the first answer is if you look at the average case then this doesn't happen if the insertions come in random order then you can show that the the height is logarithmic

16:53 and you can even make a stronger statement uh for like for the experts we say with high probability the height is logarithmic and it's spelled out here in detail but i what i mean precisely by that and there's interesting proofs behind this that uh we'll skip but in a sense if you have if you have any reason to believe that your keys come not in the worst case order but some there's some randomness in the process you will not see such a high binary search tree it almost always is fine okay