Video 2-6: §2.6 Binary search trees

0:02 in the next section I'll show you a solution to this problem maintain an array that you can fast access by index but also change that's not usually how binary search trees are presented but I think that's the key abstraction that is is actually often so useful they have other uses though so let's talk about binary search trees uh before we do that let me again check what the audience already knows

0:46 as the attentive uh listener May recognize the same set of answers as we had for the so we had something like 110 earlier okay it seems most people um got that right um remember number three was the

1:53 Heap H it's a subtle subtle difference between the two so this one that's what we called a heap ordered tree um referred to last week uh binary search tree is is this one uh we'll discuss it in in

2:15 detail so as I said before think of them as some some magic solution to have a dynamic sorted array um I'll I'll explain more what I mean by that what is it though so it's again a binary tree which is the same least as we started with four heaps it's any kind of uh structure where we have notes and they have a left and a right child and both of those can be empty now I didn't didn't go into this detail before but maybe it's useful to have something um closer to programming uh syntax so if you think about a uml diagram for for some class that represents such nodes

3:01 uh for our symol tables it would probably have these four Fields it would have a key that it stores and a value and then it would have a pointer left and a pointer right remember either of the two can be null so then the node doesn't have that kind of child um in the following I'll draw the null pointers like

3:30 this a little square me means there's nothing and the circle means this is a node good so binary search tree is is any binary tree with the following restriction namely that it has this search tree property or the search tree order which refers to the Keys nobody could read

3:56 that all the keys in the left sub tree are smaller than the key at the root and and all of those in the right sub tree are bigger now and that's that's true recursively throughout the tree or it's true for every node and its sub tree so not just at the root but in every in every Point okay

4:21 um let me show you an example this is a a binary search tree with some um Keys shown in as numbers in the nodes as numbers in all of the following we will never deal with the values the values are always just carried along I said it before they don't change the data structure uh so we don't show them in in the drawings usually and then you have a left and a right child indicated with the lines now I want to point out that I I drew the tree in a specific way you can draw the tree in another way um for example why did I choose to put node 12 so far to the left you don't have to do that but I think this is the one an only way to draw the tree that makes makes the sorted uh visible so it's drawn such that at every node the entire left sub tree is to the left of that node and the entire right sub tree is to the right okay so I take the root I draw this line down and then left and right sub tree stay in their Lane and that's true recursively if you do that that means you project down the keys to a certain X position and if you do that you see

5:32 that that's a sorted uh sorted order and that's really nothing deep it's just the search tree property but you see it in action here so that's that's the way to um that that will draw the binary search trees I think it's is very helpful to do it that way um Let's do an example of how you find a key in

6:00 this let's again find our uh 69 any search would start at the root because we actually don't have anything else from the binary search tree the way we keep the tree in our hands is keeping a pointer to the root so we're sitting here and now we're comparing the key that we're looking for with the key in the root 69 is

6:28 smaller so what we're doing looks very much like finding research except that there's no explicit Computing of the middle we just take the root as some approximate middle right so it's smaller that means we go in the left sub tree and everything in the right sub tree is by the search property bigger than 69 and can be excluded from further consideration and we continue like this 12 is too small so in this case we go to the right 57 again too small

7:00 so we go to the right and in this case we have found a node with key with that key so if we do um a look up a get in the symbol table API we would get the key uh we would get the value that's associated with this so we get the the value field from that object that's representing the

7:25 node uh let's do another example where we don't find the key so if if we look for 83 let's do it a little faster we start at the root it's bigger than 77 so we go right it's smaller than 85 so we go left but bigger than 80 so we go right and bigger than 82 so we would go right but here is a null pointer so we know the tree stops there in a way and that's the indication ah we found 83 if it was in this list it would have gone between these two keys but it's not there so it is not there right uh so it would it would uh return not found or some exception

8:15 okay that's the easy part if we have a binary search tree given then we can use it to find or look up Keys now I promise that this is a dynamic data structure so let's make it Dynamic the first kind of updates that we want to look at are inserts if this is dynamic we should be able to insert new things so let's take um I should take a different color I resered that dark blue for um for uh corrections after this lecture so I usually avoid using that color so that so that I have one free to do corrections in the lecture notes before I upload them in case I sometimes do uh something wrong Let's do let's do green how do you insert into a binary search tree uh the first step is we try to find whether the thing is already contained so again start at the root we do the same procedure as before and you can follow along um it would have gone here but it's not there that's good we want to insert it so if it had already been there we would have to reject that but it's not there so we can make room for it h and the way to do it is in in the

9:28 program you would just take this null pointer and insert a new note with key 88 there in the drawing I'll uh first have to make room but all I did was move this over I hope you can see if I go back a few times uh I've just moved this around and remember the picture is just uh imaginary what this really is is objects in memory with pointers to each other so there's no moving around to make space they stay where they are we just add a new object there's the new object object and we we put it in the right place but again in memory it would be anywhere and now we connect it with pointers to the previous one um and that way it becomes linked into the tree that's

10:19 insert and insert always works like this you follow a path down and if the element is not already there you have to stop in some null pointer in some some of these uh little squares and and then you can add your new thing into that little n

10:41 pointer we also want to delete Keys again um if it's properly Dynamic that should be possible now there's a few cases uh depending on what kind of node we delete this is either easy or uh needs a little extra step but let's go through it if we delete number 11 key 11 of course as always we start by the search and we find 11 now the important bit is this is uh a leaf in this case a leaf is I should have maybe introduced a little bit of tree and graph notation at this point a leaf is a note without children um and we say parent and child and sun or child I try to use child as the neutral form and then we have parent Leaf is the the one without children what else do we need sometimes I say unary node for a node that has just a single child not sure how relevant this will be in this section that should be probably all so there's there's un if we have a leave the way to remove it is by just setting the parent pointer to null so imagine this is no longer there and you just replace that pointer with null and gone it is that's easy because there's nothing below it that would be disconnected from

12:04 the tree um if we look at the second case if we delete 69 let's do our search again we found 69 so now let's get rid of it but it has some children so we can't just uh set the parent pointer to null that would be wrong but it has one null pointer so what we can do is rewire the parent pointer to point to the single child of that node instead so we get rid of the 69 and reconnect this and then uh again everything that was in the tree below this is still reachable that leaves us with the last case which is the only a bit more tricky one so if we find a Noe that has the key we want to delete but it's not a un node and not a leave so it has two children we'd like to do the similar tricks so we'd like to get rid of this note but then we have two dangling children ah shoot what do we do with both we can't link them both to the parent uh so instead we find the predecessor in sorted order remember this is actually corresponding to this um position in the sorted list so it has a predecessor note it has to have one if it has a left child there must be at

13:26 least one further note smaller than this so it can never run empty how do we find that um oh I circled the wrong Noe you're right yeah yeah I know it's just a typo

13:53 yeah but it's otherwise correct it's the right order just uh incorrectly copied so that's our predecessor 82 thanks thanks for checking how do we find this in the tree we go one step to the left from 85 and then keep going right until we can no longer go right in this case it's a single step but you can imagine in general it might be here's our Noe then we can go here here here here here but at some point it has to stop because you're running into that node in sorted order there must be a last node and then this one is our predecessor right so we find this this predecessor and then we swap those two nodes or their values and delete Instead This predecessor that we found and the way the predecessor is defined it means it definitely has a null pointer as the right child so this doesn't recurse further after we've done the single Swap we're definitely in the medium case or maybe even the easy case possible and so um we can the rest is done in in constant time with the changing one two points question he could have a left child

15:20 yeah so um 82 could have a let's um hypothetically there's some some other node and so on that's all right so we would then be in the medium case instead of the easy case so when we delete this node we would rewire its parent link to the single child yeah if you if you code this you will actually not need to distinguish the easy and medium case you're just rewiring a pointer and it doesn't actually matter if that pointer is null or not but it's I think it's a bit clearer to split it into three

15:58 cases okay that's all that's uh that's binary search Tre so you can search you can insert you can delete that's pretty much all you need you can build a symbol table based on that um I'll leave the details for the videos that I showed you or your memory from some undergraduate

16:16 class I want to briefly talk about how quick this is though that's a an an important part uh let's first analyze search and for that remember so we have some binary tree let me add a small example without wasting too much of our time when we search for say this this Noe the time this takes is to start at the root and follow the path down to this to this node in the tree so the time for search is if we want to be precise say um the number of comparisons we do of

17:09 keys that's exactly the depth of this node plus one because at every node on the path from the root down to this node we would have to do one comparison to check which way to go or whether we've already landed on the right thing and here I'm I'm essentially assuming that comparisons tell me one of three possible outcomes either one key is strictly smaller or bigger than the other or they are the same so it would be cost four in this case and the Noe is I guess we set at depth three because that's the number of edges so depth plus

17:50 one so the number of comparisons we need is the depth of the node let's say that we call this X plus one now uh in general it's hard to say how deep a certain node is but we can upper bound this by the height of the

18:18 tree by call the entire thing T and keep the plus one so uh if we know the height of the tree then we know an upper Bound for all the search costs and so if we want to be bit briefer let's call this H and understand that AG is this the

18:45 height and that's uh that's counting the number of comparisons the rest of the of the work that we have to do is proportional to that so you have to follow a few pointers you have to access memory and so on um but in in the Big O terms in asmic notation Big O of H is is a precise statement for for the total cost of the search now if you look at what insert and delete do they're also so insert specifically is first a

19:24 search and then we create a new node and Link it into the so we already argued that this is at most the height and the second part is constant time with our assumption that the memory management is is able to do that but changing the pointers takes constant time on a on a ram

20:03 now for delete there were the three cases but in a way it's still bounded by the height so you had one pointers the last part again constant time and the first and the second together are at most the height because remember how this worked we were walking down the tree to some point we wanted to delete that node either it's already fine because it's a leaf or un node or we had to find its predecessor but then the search would start at this node and go further down so it can't in total be more than the

20:54 height of course we could have been lazy and said search is at most order h o of H predecessor is also at most the total height so it would be two times the height which in Big O notation doesn't show up the factor two is just swallowed but if you want to count the number of comparisons precisely you could do and it's bounded by the total height okay so in summary this is also order H right Big O of

21:29 H so all the three operations are bounded by the height of the tree so it looks like the height of the binary search tree is a really important parameter uh to summarize for uh what we've seen so far this also translates to the symbol table operations as I said um coding this up uh is a little extra step that um uh we won't do here but that's what you get from

21:58 this now how high is a b inary search tree unfortunately the height can be very bad if you insert keys and what happens is this or even if it's a little less

22:14 um it could also look like this depending on the insertion order of your keys you could get a tree that's basically one long chain and if you have that the height is essentially linear n minus one that's terrible that means all the operations are just as slow as what we've had before with all without all the fancy trees and so on o bummer so what do we do the good thing is that this is a very rare and somewhat degenerate case and you almost never ex observe this if you have some Randomness in your insertion order so more specifically if you assume that the insertions come in completely random order so you insert the elements According to some random permutation then you can show the the expected height is logarithmic and um I don't want to I don't want to go into the detail of the analysis here this is a is a lovely topic but uh um maybe I'll I'll I'll spare you with it for now um You can make this statement much stronger so instead of just the expected value of the height you can get something that quantifies how unlikely it is to be above a certain height so um you can uh you can make a statement spelled out here in in formal Lang in in

23:40 with formal uh quantifiers uh basically whatever um what whatever multiplicative Factor you give me that you want above log N I can tell you an exponent how unlikely that is so in a way it's it's a way to say not just the typical height is very close to this log n uh also almost always it is if you have a large number of keys and they come in random

24:20 order also remember we discussed this in a bit more detail um in the chapter on heaps uh any binary tree with n nodes must have uh at least this log uh oh yeah base two let me stress that

24:54 here so in this sense um what we what we find here as the typical height of a random binary search tree when you insert things randomly is very close to the best possible height so it's not just okay it's it's almost as good as if you perfectly balance everything out