Video 2-6: §2.6 Binary search trees

0:00 Intro

0:03 in The Next Step section we'll talk about binary search trees for now that might seem disconnected to what we just talked about but uh you will see what's coming okay again um I would expect that for two-thirds a few this is this is known and this is my proxy question to find out if that is true so without telling you what a binary search tree is in this class uh let's have a go at this

0:11 Clicker Question

0:55 yeah again there's another another name for the same thing uh fundamental things have often been all different ways no okay I should have checked how many signed in for the

1:33 59 that's got at least 55 right okay 56 yeah good uh no no that's not what I wanted well I kind of gave the answer away which is not not a problem uh I keep doing this right it's um the the thing is okay people are changing their minds now

2:03 remember it's just about participation I think the the true picture was half or slightly more if you remembered uh like before so it's not not a not really a surprise

2:16 I do want to give the answer away here okay do I well we'll discuss this in detail there are some shortcomings of binary search uh I didn't discuss this in detail on the slides but one shortcoming which is maybe a bit academic esoterical it needs a race and maybe we don't like a race because we don't like a race uh the real shortcoming of of binary search or an a dictionary implemented as a sorted array with binary search for get is how do you update it how do you insert an element that has to go somewhere in the middle it's a it's a it's an array you have to shift all the elements over so you're spending worst case linear time again for the update you can quickly find where the element has to go but this painstakingly effort you have to move all the elements before you can get a new element in there so it's virtually useless um so what binary search trees are you should think of uh the the key concept is it's a it's a dynamic sorted array it can behave like an array it's not quite as fast for Access than just jumping to the 15th position in an array but it's virtually doing everything that an array can plus allowing you to insert

2:20 Binary search trees

3:41 at any possible position okay I think that's that's a way it's not often phrased but that's the cool way I think this is if you if I told someone who doesn't know this make that happen make an array where you can insert at any point and it's still fast they're probably stuck for a while okay we've already talked about uh binary trees so uh you'll remember this is a construct where we have notes and they have pointers to left and right children and they have a value associated with them in this case I really should say a key they have a key Associated to them if you wanted to have some uml style diagram as I had them before for a node

4:33 we should have four Fields really a pointer for the left child a pointer for the right child um a key and then a value uh okay I I told you what it should read it's hard to read again the value pointer is not very interesting there's there's nothing really happening with that one so we'll mostly ignore it but we'll have a key Associated to each node

5:03 that part's the same binary trees is the same as four heaps that's also why people often confuse it a bit so don't do that they're both binary trees the rest is different though plus second property

5:15 um also no complete binary trees right this uh this is unrestricted it's okay for a binary search tree to have all sorts of gaps it can look like this okay that's that's a valid shape for heaps we didn't like that second big property that's the important one everyone listen up the search tree property or symmetric order um symmetric ordered trees if you have any node that's the root of some subtree the key in that root element has to be bigger than everything in its left subtree all the keys in the left subtree and it has to be smaller than everything in the right sub tree now if any of the two sub trees are empty that statement also makes no restriction if there are elements they have to satisfy this

6:06 BST example & find

6:06 okay here's an example um that's that's some uh binary binary search tree um shown in the way that I think binary search trees must be drawn if you want to understand how they work which means you uh lay them out so that the root vertically separates the two subtrees and you do that recursively so the root is root key is projected down like this then the the root of the left subtree is projected down here and separates the its two subtrees and so on can you see how this this picture is generated

6:48 and then you see how the search key property naturally gives you back the sorted list at the bottom and that's really just by definition the key of the root here project it down here everything in the left subtree is supposed to go to the left of the of it in the picture and the search tree property exactly says all these Keys should be smaller than the key in the root and so if you do that for every node you end up with the sorted list all right um should maybe comment the little the little square boxes these are null pointers I included them in these pictures because they um they make um insertion a bit clearer if you explicitly draw them uh but uh in in python or if you implement this every of these nodes really is one of these these boxes is an object with a few Fields a left point a right pointer which can be null and a key and so on all right um I'm supposed to show you some interesting example of how we find an element let's use the same example as before

8:02 let's use the 69. how can we find industry without looking at all the nodes right how can we find with the 69 is contained well one thing I haven't said we always keep a pointer to the root of the whole tree that's what we need to get started

8:24 so we start at the roots and now we do something similar to binary search We compare 69 to 77 it's smaller so we have to go left so we follow the left pointer to this one now we find that 12 is uh smaller so 69 is bigger and then we follow the right child because the logic behind this is at this point I know when 69 is already bigger than 12 there's no point in looking in the left subtree because all of these keys are even smaller than 12 and 12 already was too small same as binary search just that we don't really have to jump into the middle of anything we're following the the topology of the tree and that tells us what to do

9:29 and so I'll say this one more time at this point we won't just stop we will return the value that is also stored in this node okay but from now on I'll ignore that last bit we'll always just carry these value pointers around with us and there's never ever anything interesting happening uh let's do one more example where we search for something that's not there

10:00 so if you find if you try to find 88 we start at the root again 88 is bigger than 77 so we take the right pointer it's also bigger than 85 but smaller than this and at this point we end up in a leaf what an null pointer and that's the signal it's not there if it was there it had to be at this position but there is nothing so no element there and again I invite you to mentally project down this this left and right zigzagging onto the horizontal on onto this axis then you see it's doing similar things like binary search

10:37 good so we can still do binary search question oh so um what I meant is uh every node so every Circle in the picture is stores a key and a value and okay I said pointer because uh I thought this helps you with python like if you're just learning python maybe this was not very helpful everything in Python is an object so every every value that is something is really a pointer to an object that's what I meant uh you can think of it every node stores a key and a value and when you found a node that has a key that matches the one you're finding you're trying to find you return the value that this node stores that's that's all there's nothing nothing complicated going on okay this numbers are the node numbers

11:42 what's the difference between the note number and the actual values yeah so maybe let's zoom into one of these just to make that clear say we have uh 77 right um and let's say we zoom into this if you look very close then what it really looks like is this box and it has the two pointers and it stores 77 and some value that we associated with it who knows maybe uh the string 77 I'm just making this up right the dictionary can store whatever is convenient and it would have two pointers now I'll say this one would point to this this object and this one would point to that object now I'm completely messing up the slide but here

12:45 yeah last year I didn't talk about the values at all and then people got confused now I talked about and I think I confused it even more um I'm iterating this I hope it's clearer now uh good so finding things in a binary surgery is just like binary search and we could already do that on the array so that's that's not really where things get interesting so let's do something interesting I praised these as being Dynamic so let's insert something

13:07 BST insert

13:22 most operations actually start by by trying to find the element and that's natural if you want to insert something in a dictionary remember this is really the key and there's a value associated with it and we require that every key is only there once or not at all so we start trying to find 88 is bigger than 77 so we go right uh is hold on is bigger than that and it was smaller than this so we the this search ends in this null pointer now uh that signals 88 is not yet in the tree which is good we want to insert it so what we do now um is we create well this is just drawing the the picture differently okay um back and forth a few times it's just making making way on the picture the data structure hasn't changed but then we can create a new node and add it as the new Left child of this uh of this node 97 where the search stopped okay so the search brings us to some node that has a null pointer and we should replace this null pointer by the new element that's where the search left is off and so all that insert has to do is create a new node and stick it there

14:36 okay pretty easy right dynamic means not just insert also delete should work let's have a quick look at that as well uh and here things are a tiny Tad more complicated but not not too crazy um but there's there's these three cases um now let's let's do uh one example each to illustrate this if we want to remove 11 well first of all okay it's there so we'll we'll find it to find out whether it's there we do a search

14:45 BST delete

15:24 same process as before so we found 11. now we'd like to get rid of it and in this case we can just go ahead it's easy because 11 is a leaf in the tree it has no children just null pointers so we can just remove it which means in 12 uh set this one to a new null pointer and that's all that's all that's needed okay and then we have removed this element

15:51 things are only slightly different if the element that we find is uh one with a single child so uh 69 has one child but the other one's null in that case we can still just remove the node and we can shortcut uh we can jump over over this node that we delete and just remain put the single child that's 69 had as the new child of its parent that's again not such a big deal and they they're Troublesome case is as you may guess when you want to delete something that has two children because then you can't possibly stake both children in the parent pointer uh there's it's only room for one uh so there's there's different ways how you can solve this uh the easiest that we will do is you continue a search and you find the element that's just smaller than 85 so the largest element that's in the dictionary but smaller than 85 which always means you go first one to the left and then to the right as long as as long as you can that always gets you to the the predecessor in the in the search tree

17:21 uh and then you swap these two which could just mean replacing key in value okay and now why does this work why does this not destroy the invariant of the search tree the reason is that these two were adjacent in the array waste is a 72 anyways so these two are adjacent in the array there's nothing between them so after we've removed this one that one is still in the in the middle of the the right subtree and the left sub tree of of this node so it can just take this one's place okay

18:07 so we've removed this one but we might have to recursively remove this node but because it's the predecessor it all we follow right links as long as we can so it always has at most one child so the the second bit this doesn't Cascade the second will always be a simple case either easy or medium okay I guess you're you're now bimodal the half is lost and the other half is bored because they've seen this uh so the average is happy right

18:40 Analysis

18:46 I promise there will be other kinds of topics in the future no no evaluation let's briefly analyze how expensive all these operations are now a search if you remember we always we always had some some tree it may look in all sorts of ways and the search followed some path down the tree okay that dependent on the key but in either case

19:22 the length of this path is at most the height of the tree remember the height is just the maximal number of edges on any route to Leaf path so it's kind of by definition the the larger the longest path we can we can follow if we just go down

19:43 if you want to count the number of comparisons so if the height is H then the number of comparisons we make is is it most h plus 1 because you need to compare at the node where you start and you add the node where you stop you might get away with one less because if you end up with a null pointer maybe you can can be done early and also you can't be lucky if you're looking for an element you find it in the root then it's just one but it can't go can't go on for more than the height of the tree

20:32 if you remember what insert did insert walk down a path and found a found a null pointer and then stuck the element there so it's dominated by the search

20:49 and again we have to basically same number of comparisons we just have to create a new object at the end and stick it there no big difference and delete is a little more tricky if you look at the different cases but even the hard one if you combine the two orange paths that we followed so if you have a hard case then the first search stops somewhere in the middle of the tree but then you continue from there so in total you still just follow one big path and so again it's bounded by The Hand by height so it's really everything's everything depends on the height of this binary search tree

21:33 BST summary

21:36 uh so I summarized this here in terms of the abstract data type operations if you want to construct a tree you unlike for heaps there's no no really smarter way than inserting one after the other so we might as well just do that that's n insertions and each is bounded by the final height if you just do insertions the tree will only ever grow so the final height is a Bound for all the Heights in in between all the other operations are essentially doing one kind one search plus a little bit of extra things but if we ignore the exact count of operations if we allow ourselves this fudge using Big O notation ignore constant factors they are either bounded by the height or they're even even faster

22:30 What is the height of a BST?

22:32 so the height seems to be pretty important what is the height what can it be in the worst case and the unfortunate answer is it can be pretty awful and the example is quite clear if you insert elements in sorted order the binary search tree you get will look like this because you always if the new element you insert is always bigger than any before you always follow the right paths until you find the rightmost leaf and stick the new element there so this is it's not just an unfortunate case it's also something you can run into fairly naturally if you insert things in sorted order so you really shouldn't do that uh the good news is is also a rare and pathological case in some other sense namely in the average case if you can somehow make sure that the insertions are not sorted and it's it's really enough so if they come in random order that's fine then you get logarithmic Heights which remember from heaps that's the best possible the only question is what the constant inside this here is so the constant might not be optimal but it's close to Optimal if things come in random order um and you can even prove slightly more sophisticated statements under this model it's not just the expected height

23:56 is is good but also it's very rare to see a bad height you can prove things that it doesn't have to be quite completely random but there's some caveats if you also add deletions things become a bit more tricky again so for us we'll we'll mostly just say the height is normally good if you don't have really unlucky inputs question

24:28 yeah so we'll we'll come to that uh the question was can you rebalance the tree and so that's exactly the answer to that um uh we'll revisit that at the end