# transcripts

session: S06-39
timestamp: 00:04:05.29
speaker: LOW
utterance:
we got to find the b@l, and then we got to get this new node, and then we got to find these two links.


session: S06-39
timestamp: 00:10:03.05
speaker: LOW
utterance:
this node contains the address of the next one, but this node doesn't contain the address of the previous one.


session: S06-39
timestamp: 00:11:46.16
speaker: LOW
utterance:
and I think you probably believe that it doesn't matter how many elements there are if a@l is in the middle.


session: S06-39
timestamp: 00:14:14.06
speaker: LOW
utterance:
one, frequently you traverse the lists with two pointers, one right behind the other, because when p@l finds what you want, q@l is what you need to do the surgery.


session: S06-39
timestamp: 00:14:51.15
speaker: LOW
utterance:
but basically it comes about with a stack of trays in a very fancy ritzy expensive cafeteria where you're only, the spring is so carefully balanced and loaded that you're shown one tray on top and you don't know how many trays are in there.


session: S06-39
timestamp: 00:15:24.05
speaker: LOW
utterance:
push is the insertion, and you say what stack am I pushing on, and you say what value you want to stack push.


session: S06-39
timestamp: 00:16:08.07
speaker: LOW
utterance:
so if I pop this stack I get a q@l, if I pop it again I get a d@l, if I pop it again Im putting a t@l in here.


session: S06-39
timestamp: 00:16:37.29
speaker: LOW
utterance:
I mentioned that because some people use a peak, which returns the top one without changing the stack.


session: S06-39
timestamp: 00:17:01.10
speaker: LOW
utterance:
the other fundamental one we need is this bullion function, empty, that returns of course true or false.


session: S06-39
timestamp: 00:17:21.01
speaker: LOW
utterance:
and you can see the top one you could +// <so a stack you either> [///] everything happens at one end called the top.


session: S06-39
timestamp: 00:17:52.11
speaker: LOW
utterance:
well peak didn't do me any good because it never changes the stack, and we get an infinite loop or whatever.


session: S06-39
timestamp: 00:19:10.01
speaker: LOW
utterance:
it's pretty silly to say I want you to count this for me, and you would say, it used to have four, but it's got zero.


session: S06-39
timestamp: 00:19:25.06
speaker: LOW
utterance:
<*uh, you know we> [//] v@l is equal to q@l, and the next time around, q@l is equal to d@l, and single variable.


session: S06-39
timestamp: 00:23:19.02
speaker: LOW
utterance:
because the five and the eleven should switch, and then the four and seven should switch, yeah right.


session: S06-39
timestamp: 00:23:55.10
speaker: LOW
utterance:
O_K_, so it is a binary search tree, cause these guys are less than five, and these guys are bigger than five, so this nine is less than and bigger than two et cetera.


session: S06-39
timestamp: 00:24:19.20
speaker: LOW
utterance:
<so we're going to do them> [//] I always had to do them in some strange order, but now lets do them straight down through here.


session: S06-39
timestamp: 00:24:30.05
speaker: LOW
utterance:
you got to start here at the root, just like in <a binary> [//] in a link list you have to start at the first node.


session: S06-39
timestamp: 00:24:45.09
speaker: LOW
utterance:
and if this is +// this only has seven nodes, but if this tree had a thousand nodes, and it was balanced pretty well, you're throwing away half the tree.


session: S06-39
timestamp: 00:26:12.00
speaker: LOW
utterance:
O_K_, so that's why I wanted to do search first, cause insertion is search followed by when it fails, then that's the place to put it.


session: S06-39
timestamp: 00:29:27.00
speaker: LOW
utterance:
but it turns out there is one number, there is one node here that can easily move up and take five's place.


session: S06-39
timestamp: 00:29:34.00
speaker: LOW
utterance:
or, or and or whatever, there is exactly one node over here, that can move up and take five's place.


session: S06-39
timestamp: 00:30:04.00
speaker: 239
utterance:
they're at the bottom of the list, and that they are at the most of the small list, and the least of the big list.


session: S06-39
timestamp: 00:30:10.00
speaker: LOW
utterance:
so in the general case here, I got this node I want to replace, it's got two kids, it's got some giant less then tree, and some giant right subtree.


session: S06-39
timestamp: 00:31:27.00
speaker: LOW
utterance:
and again, the reason is, if you move this guy up here, he is bigger than all these, so he sits as the root of this left tree.


session: S06-39
timestamp: 00:31:50.00
speaker: LOW
utterance:
*uh, let me point out to you that it's not quite as simple as this picture shows and that these are both leaves.


session: S06-39
timestamp: 00:32:17.00
speaker: LOW
utterance:
I could put two and a half in, less than five, bigger than two, less than three, two a a quarter, two and three quarters, all kinds of stuff.


session: S06-39
timestamp: 00:33:06.00
speaker: LOW
utterance:
and seven was the smallest one over here so all these guys are bigger than seven, and this thing over here is a binary search tree.


session: S06-39
timestamp: 00:33:45.00
speaker: LOW
utterance:
uh I think what they are trying to show you is that this is not by any means the only binary search trees on those seven nodes.


session: S06-39
timestamp: 00:33:56.00
speaker: LOW
utterance:
and I say the way to do that is to take these numbers, one two three four five six seven eight nine, and give them to me in any order at all.


session: S06-39
timestamp: 00:36:28.00
speaker: LOW
utterance:
and it won't give you the nice search properties because you +// you know throw away the left half of the tree, you're throwing away nothing.


session: S06-39
timestamp: 00:36:38.00
speaker: LOW
utterance:
*uh, so that's the worst case of a tree, and that's when the tree collapses into a linear structure, two dimensional structure.


session: S06-40
timestamp: 00:01:06.00
speaker: LOW
utterance:
first name, last name, campus address, home address, phone number, social security number and bla bla bla.


session: S06-40
timestamp: 00:01:44.00
speaker: LOW
utterance:
so if you go to the first node, you can see it's a c@l, and we can follow this link to the address to the second node.


session: S06-40
timestamp: 00:02:18.00
speaker: LOW
utterance:
the first one may be at the middle of memory and the next one is at the begginning of memory, and the next one is at the end of memory, and the next one is in the middle of memory.


session: S06-40
timestamp: 00:02:39.00
speaker: LOW
utterance:
they want us to describe some operations to insert the new node which contains g@l, after the node which contains b@l.


session: S06-40
timestamp: 00:02:56.00
speaker: LOW
utterance:
and that used to be a four elements list, and now it's a one two three four five element list, O_K_?


session: S06-40
timestamp: 00:03:02.00
speaker: LOW
utterance:
if these were sequential, and you wanted to put a new one in the middle, you would have to move them all over, O_K_?


session: S06-40
timestamp: 00:03:09.00
speaker: LOW
utterance:
if these were sequential and you wanted to have to delete one, you would have to move them all backwards.


session: S06-40
timestamp: 00:03:49.00
speaker: LOW
utterance:
O_K_, and as I should say we want to put this new node in after b@l, and we have to find b@l, because we can't start there, we start here.


session: S06-40
timestamp: 00:04:24.00
speaker: LOW
utterance:
we're looking for the b@l, so we'll say while the info of the node p@l is pointing at is not the b@l.


session: S06-40
timestamp: 00:05:32.00
speaker: LOW
utterance:
and it will give us back a node, and it gives us back the address of the node so we still work in n@l.


session: S06-40
timestamp: 00:08:03.00
speaker: LOW
utterance:
<O_K_, so it's the same thing> [//] start off the same way as before, I'll set a temporary equal to h2@l, I'll say while the info of that node is not a@l, that's not a@l, so advance it.


session: S06-40
timestamp: 00:08:22.00
speaker: LOW
utterance:
so those are the same three statements I did a second ago, except I've started with h2@l instead of h1@l.


session: S06-40
timestamp: 00:10:55.00
speaker: LOW
utterance:
we've only got three elements here, but even if there is three thousand elements, if a@l is in the middle, it's O_K_.


session: S06-40
timestamp: 00:11:00.00
speaker: LOW
utterance:
because what we have done is make the one before the node which contains a@l point to the one after the one that contains a@l.


session: S06-40
timestamp: 00:12:04.00
speaker: LOW
utterance:
alright, a@l is first so whatever happened would be p@l would be initialized, h2@l, and q@l would be initialized to null.


session: S06-40
timestamp: 00:13:32.00
speaker: LOW
utterance:
and the reason we do that is when we get out of the loop, p@l points to some condition, but q@l points to the one before that.


session: S06-40
timestamp: 00:13:44.00
speaker: LOW
utterance:
the other thing this shows you is that you should always draw pictures, but you got to watch out for special cases.


session: S06-40
timestamp: 00:14:40.00
speaker: LOW
utterance:
so if I have a stack over here with a@l and x@l and p@l and q@l on it, then like a link list, you can only see the top element.


session: S06-40
timestamp: 00:17:44.00
speaker: LOW
utterance:
<so while not empty s@l> [//] while s@l isn't empty, here's what we'll do, we'll pop something off of s@l, and put it in the variable v@l, and the q@l that popped off, and of course we'll increment the counter.


session: S06-40
timestamp: 00:18:49.00
speaker: LOW
utterance:
and it returned, you're stack used to have four elements, but now it's got zero # we've clobbered it.


session: S06-40
timestamp: 00:18:54.00
speaker: LOW
utterance:
so we need to save these things, as we pop the q@l off, and then pop the p@l off, and then pop the x@l off, we need to save them.


session: S06-40
timestamp: 00:20:31.00
speaker: LOW
utterance:
but we really shouldn't give them back a different stack, we should give them back the same stack to start with.


session: S06-40
timestamp: 00:21:00.00
speaker: LOW
utterance:
so we'll pop the a@l off and put it back, we'll pop the x@l off and put it back, we'll pop the p@l off and put it back, we'll pop the q@l off and put it back.


session: S06-40
timestamp: 00:21:07.00
speaker: LOW
utterance:
so we'll reverse the order of these, which is the reverse of those, so we're back to the reverse of the reverse, which is the same thing again, right?


session: S06-40
timestamp: 00:22:44.00
speaker: LOW
utterance:
everywhere, things to the left of the node are smaller, and things to the right of the node are bigger.


session: S06-40
timestamp: 00:25:32.00
speaker: LOW
utterance:
alright that is a binary search tree, because these guys are smaller than five, and these guys are bigger than five.


session: S06-40
timestamp: 00:25:43.00
speaker: LOW
utterance:
so they want us to do three things, we're going to search, we're going to insert, and we're going to delete.


session: S06-40
timestamp: 00:26:53.00
speaker: LOW
utterance:
you look for four, so you went this way, you look for four so you went that way, and there is nothing there.


session: S06-40
timestamp: 00:28:09.00
speaker: LOW
utterance:
once again a tree grows upside down, so here is the root and one and three and seven are leaves, they've got no kids.


session: S06-40
timestamp: 00:28:18.00
speaker: LOW
utterance:
so suppose you wanted to delete the seven and you want to keep it a binary search tree, and you just change this to a null.


session: S06-40
timestamp: 00:28:53.00
speaker: LOW
utterance:
the suggestion is to delete the nine, from this binary search tree, with as little work as possible, keep it a binary search tree.


session: S06-40
timestamp: 00:30:02.00
speaker: LOW
utterance:
and it's still a binary search tree, because everything over here was bigger than five, so eight can be the root of this right subtree.


session: S06-40
timestamp: 00:30:11.00
speaker: LOW
utterance:
and I didn't change anything below the eight, so that was a binary search tree, so it still is, okay?


session: S06-40
timestamp: 00:31:08.00
speaker: LOW
utterance:
so there is one node on this side, that can move up there, and there is one node on this side that can move up there.


session: S06-40
timestamp: 00:31:53.00
speaker: LOW
utterance:
now we can't move the nine up here because these guys are smaller than nine, and supposed to be +...


session: S06-40
timestamp: 00:32:08.00
speaker: LOW
utterance:
in the general case, we've got a node Im trying to delete, and I've got a giant right tree here, and I've got a giant left tree here.


session: S06-40
timestamp: 00:32:22.00
speaker: LOW
utterance:
and there's one guy over here that you can put up there, and there is one guy over here that you can put up here.


session: S06-40
timestamp: 00:32:38.00
speaker: LOW
utterance:
it has to be +// this is going to be the left tree, so these guys have to all be smaller than that, so this has to be the +...


session: S06-40
timestamp: 00:33:21.00
speaker: LOW
utterance:
until you can't go, because you're always getting bigger, by going right, so until you can't go right anymore.


session: S06-40
timestamp: 00:33:29.00
speaker: LOW
utterance:
or you go left once, and you go right once, and you go right once, and you get it in the bigger ones, and then you go smaller, smaller, smaller, smaller, as far as you can.


session: S06-40
timestamp: 00:33:51.00
speaker: LOW
utterance:
here if four where in the tree, that would be the biggest one over here, so we would go left once, and we would go right until we can't go right anymore.


session: S06-41
timestamp: 00:00:44.00
speaker: JAC
utterance:
and if we want to put something else into our stack what we do is we put another Lego on top of our previous Lego.


session: S06-41
timestamp: 00:04:11.00
speaker: JAC
utterance:
you have +// you can +// one way of having a binary search tree you can have all yes's one side and all no's on one side.


session: S06-41
timestamp: 00:04:33.00
speaker: JAC
utterance:
or if you hold it up it kind of looks like a tree, that's why they call it +// this is the root # it's just upside down


session: S06-41
timestamp: 00:05:02.00
speaker: JAC
utterance:
if for any reason that's +// it's +// the tree is not designed that way then it's not a binary search tree.


session: S06-41
timestamp: 00:09:07.00
speaker: JAC
utterance:
basically, I'll show you how we insert things when we get to that point and you'll see why we would never, if we make a binary search tree correctly, we would never have anything larger than 11 on this side and anything smaller than eleven on this side.


session: S06-41
timestamp: 00:09:59.00
speaker: JAC
utterance:
I mean, if +// it's conceivable that you can setup a binary search tree where the right children were less and the left children were not.


session: S06-41
timestamp: 00:10:19.00
speaker: JAC
utterance:
because now everyone is expecting it to operate in one fashion and you're operating in a different fashion, okay?


session: S06-41
timestamp: 00:10:28.00
speaker: JAC
utterance:
so continuing our discussion about binary search trees, we're going to use this binary search tree in our discussion and there are a couple of questions.


session: S06-41
timestamp: 00:10:52.00
speaker: JAC
utterance:
so first thing we're going to do is we're going to see how we can find the number eight # in this tree.


session: S06-41
timestamp: 00:10:58.00
speaker: JAC
utterance:
well, first thing we do is we come and +// actually I'm going to redraw # this but I'm not going to redraw the whole thing because we don't need the whole thing.


session: S06-41
timestamp: 00:12:31.00
speaker: JAC
utterance:
eight is greater than five so we would always go to the right because the right is always greater than the left.


session: S06-41
timestamp: 00:14:28.00
speaker: JAC
utterance:
and in this case nine's right child would be, if we look back here, nine's right child would be null.


session: S06-41
timestamp: 00:15:01.00
speaker: JAC
utterance:
we would do the same search but we're looking for +// we're actually looking to see if four is in there or looking for null.


session: S06-41
timestamp: 00:15:46.00
speaker: JAC
utterance:
now, of course, obviously this would become really big and ugly if reported all the nulls but this is just convention.


session: S06-41
timestamp: 00:16:01.00
speaker: JAC
utterance:
and obviously it's not +// it's not logical for you to show everything that doesn't have to be shown.


session: S06-41
timestamp: 00:16:51.00
speaker: JAC
utterance:
well, if we're inserting four then we're comparing four to every node along the path to where the four would be.


session: S06-41
timestamp: 00:17:00.00
speaker: JAC
utterance:
we compared four +// we always start at the root and we start making our way to the most left +// to this spot that four has to be at.


session: S06-41
timestamp: 00:17:29.00
speaker: JAC
utterance:
alright if we could do 3.4 or 3.5 then I might have stuff other than in here but eventually four would be somewhere to the right of the three.


session: S06-41
timestamp: 00:17:40.00
speaker: JAC
utterance:
we're always working +// we're always doing our comparisons until we find the most +// the spot that +// whatever number we're inserting or whatever number we're searching for has to be.


session: S06-41
timestamp: 00:17:50.00
speaker: JAC
utterance:
but there's no +// in this in the way this is setup with integers, there is no other place that four could can be.


session: S06-41
timestamp: 00:18:03.00
speaker: JAC
utterance:
now say for example we found out that it's not in the tree so we want to insert it so we did our search again and inserted it.


session: S06-41
timestamp: 00:18:10.00
speaker: JAC
utterance:
normally if you were doing it really +// once you found it you would probably say, here's the null pointer # I didn't find it # okay.


session: S06-41
timestamp: 00:18:33.00
speaker: JAC
utterance:
now I want to +// I didn't find it now I want to insert but I have to search through a hundred levels.


session: S06-41
timestamp: 00:18:40.00
speaker: JAC
utterance:
that's just +// I could possibly have a tree with 1,000 or 10,000 +// obviously it's not efficient to look that deeply and then have to insert it.


session: S06-41
timestamp: 00:19:28.00
speaker: JAC
utterance:
so we're going to insert six so the first thing we do is come here and we compare six um with the root.


session: S06-41
timestamp: 00:22:08.00
speaker: JAC
utterance:
so what we would do is we would look +// first thing we do is we look at what is five's right child.


session: S06-41
timestamp: 00:23:40.00
speaker: JAC
utterance:
by doing this this way we insure that we maintain that everything to the right is larger and everything to the left is smaller, right?


session: S06-41
timestamp: 00:23:51.00
speaker: JAC
utterance:
if we take +// if we decide to make nine the new +// if we just move nine up now I have the problem that eight and seven are both smaller and they're supposed to be on the left side of the tree.


session: S06-41
timestamp: 00:24:06.00
speaker: JAC
utterance:
and that will always be the case you always go to your right child and go all the way down until you find the left child.


session: S06-41
timestamp: 00:24:15.00
speaker: JAC
utterance:
uh and if we check our left child +// we go to the left child and go as far to the right as possible then that would be the largest number on the right +// I'm sorry on the left, okay?


session: S06-41
timestamp: 00:24:29.00
speaker: 241
utterance:
now for this one does it usually just inherit the next number after the one you deleted like in this case if you have something like this?


session: S06-41
timestamp: 00:24:59.00
speaker: JAC
utterance:
so if this was the case where there was nothing on the right and five was deleted then uh the immediate left child would inherit what would be two, right?


session: S06-41
timestamp: 00:25:31.00
speaker: JAC
utterance:
basically we keep going +// you keep going down the path (un)til someone has +// there's no left child.


session: S06-41
timestamp: 00:25:52.00
speaker: JAC
utterance:
and actually the way I'm going to do it we have the numbers one, two, three, five, seven, eight, and nine.


session: S06-41
timestamp: 00:26:31.00
speaker: JAC
utterance:
so first thing I'm going to do is I'm going to take the top item from the stack so I'm going to call top and it's seven.


session: S06-41
timestamp: 00:28:31.00
speaker: JAC
utterance:
there are special trees that actually try and make sure that it's balanced so that the left side and the right side are all the same depth.


session: S06-41
timestamp: 00:28:43.00
speaker: JAC
utterance:
if I needed to do a search on the right child +// right side I would have to go one, two levels, right?


session: S06-41
timestamp: 00:28:50.00
speaker: JAC
utterance:
but if I have to make a search on the left side I have to go one, two, three, four before I find something.


session: S06-41
timestamp: 00:28:59.00
speaker: JAC
utterance:
or to keep this a little more balanced I might promote three here and have five as the right child, one as the left child, and have two here.


session: S06-41
timestamp: 00:29:31.00
speaker: JAC
utterance:
now the way I like to make my comparisons to real life on a link lists is um the movie theater line.


session: S06-41
timestamp: 00:30:08.00
speaker: JAC
utterance:
now the interesting thing about a link is whoever is in front can basically tell you only the person who is immediately behind them.


session: S06-41
timestamp: 00:31:53.00
speaker: JAC
utterance:
we have to describe a sequence of inserting a new node which contains g@l in the list after the node.


session: S06-41
timestamp: 00:33:01.00
speaker: JAC
utterance:
now what we need to do is, Bob needs to go well O_K_, now that we know that Fred is in front of me and Fred is <in front of me or> [//] behind you, rather, I need to know that you're in front of me.


session: S06-41
timestamp: 00:33:26.00
speaker: JAC
utterance:
so now that I have +// lets see # k@l, b@l, g@l, in my terrible drawing and f@l, and we still put a null here, O_K_?


session: S06-41
timestamp: 00:35:19.00
speaker: JAC
utterance:
<we don't> [//] I mean there are ways, but the way we have this set up, it's simplistic as possible.


session: S06-41
timestamp: 00:37:25.00
speaker: JAC
utterance:
and it still points to a@l and now if we start looking, e@l points to this thing in the space which we don't know.


session: S06-41
timestamp: 00:38:40.00
speaker: JAC
utterance:
the way we can think of this is, here is our head, and we could have e@l, point to a@l, point to m@l, point to null, O_K_?


session: S06-41
timestamp: 00:39:39.00
speaker: JAC
utterance:
now if we want something to add, all we would need to do is, find where this points to null # find the end of the line, okay?


session: S06-41
timestamp: 00:40:07.00
speaker: JAC
utterance:
um what we would do is now we would set <whatever null> [//] whatever is pointing to null, we set that to whatever the first thing h@l two is pointing to.


session: S06-41
timestamp: 00:40:42.00
speaker: JAC
utterance:
so if we think of this as just the one node, inserting this isn't exactly the same way as inserting g@l like we did earlier.


session: S06-41
timestamp: 00:41:10.00
speaker: JAC
utterance:
come here <we would find> [//] we find out what k@l is pointing to, and we find whatever is pointing to null.


session: S06-41
timestamp: 00:41:27.00
speaker: JAC
utterance:
and that's it # so anyway if we think of it as one node we're something is pointing to it, and something is pointing to null.


session: S06-42
timestamp: 00:00:34.00
speaker: JAC
utterance:
it can hold a number or # +// it's just +// the Lego comparison is just a comparison so we can kind of understand how it works.


session: S06-42
timestamp: 00:00:43.00
speaker: JAC
utterance:
well what it does is actually holds +// we'll do numbers +// is that it holds the number seven, okay?


session: S06-42
timestamp: 00:01:54.00
speaker: JAC
utterance:
in the first case there was nothing there so we made a new +// we always make +// put a new Lego, right?


session: S06-42
timestamp: 00:03:03.00
speaker: JAC
utterance:
now ## +// however the way things work with the stack I can't find out +// I can only find out what's on the top.


session: S06-42
timestamp: 00:03:53.00
speaker: JAC
utterance:
top is our way of looking at whatever is on the top +// what is on the top and telling me what it is.


session: S06-42
timestamp: 00:04:06.00
speaker: JAC
utterance:
now we have push so we could obviously keep pushing until the end of the world came but at some point in time we might want to take something off the stack, right?


session: S06-42
timestamp: 00:04:49.00
speaker: JAC
utterance:
okay so this Lego +// basically this Lego no longer exists as much as we care and there's five, okay?


session: S06-42
timestamp: 00:07:29.00
speaker: JAC
utterance:
the children to its right are greater than the parent and the children to the left are less than the parent.


session: S06-42
timestamp: 00:07:47.00
speaker: JAC
utterance:
we don't want so switch it the other way where left is greater and right is less than because people aren't expecting that, right?


session: S06-42
timestamp: 00:08:01.00
speaker: JAC
utterance:
so working with that principle we're going to try and figure out if all of these are binary search trees or not, okay?


session: S06-42
timestamp: 00:13:29.00
speaker: JAC
utterance:
and four +// two is less than four so we go to its left but four doesn't have anything so then we can insert two here.


session: S06-42
timestamp: 00:13:36.00
speaker: JAC
utterance:
since it's always +// the way we make comparisons we always ensure that everything is built correctly, okay?


session: S06-42
timestamp: 00:13:45.00
speaker: JAC
utterance:
no matter what # there was no other way I could have gotten something else # by doing my comparisons.


session: S06-42
timestamp: 00:13:56.00
speaker: JAC
utterance:
if I had inserted one before two though I would have one here and then when they came down I would have two here.


session: S06-42
timestamp: 00:15:24.00
speaker: JAC
utterance:
+< obviously> if we're looking at it we can see it but when we're looking for it with a program or something we can't just look at it.


session: S06-42
timestamp: 00:15:54.00
speaker: JAC
utterance:
it would be very difficult to find just one number or one letter or one word or one anything, right?


session: S06-42
timestamp: 00:16:44.00
speaker: JAC
utterance:
so I come on my third step +// I know I'm going to the left child so I compare on step three +// I compare eight and eight, okay?


session: S06-42
timestamp: 00:20:40.00
speaker: JAC
utterance:
since we found null and we're trying to insert six we know there's nothing else and we can insert six where null is.


session: S06-42
timestamp: 00:21:00.00
speaker: JAC
utterance:
but by convention because each one of these nodes which point to nothing or has no right child maybe it has no right child in the case of nine.


session: S06-42
timestamp: 00:21:12.00
speaker: JAC
utterance:
(be)cause like I said if we have a tree with a thousand levels then we could potentially have several thousand nulls, right?


session: S06-42
timestamp: 00:21:35.00
speaker: JAC
utterance:
since we know that each child that doesn't point to anything has a null we don't consider +// we don't insert null.


session: S06-42
timestamp: 00:21:50.00
speaker: JAC
utterance:
okay null is our stopping point and null is going to come up again in the next subject we'll talk about # after binary search trees.


session: S06-42
timestamp: 00:23:18.00
speaker: JAC
utterance:
so the resulting tree would be ### the left child +// side doesn't change anything but now I've deleted nine.


session: S06-42
timestamp: 00:24:04.00
speaker: JAC
utterance:
um if we want to +// this is problem six +// if we want to delete five +// so we have to find five first.


session: S06-42
timestamp: 00:24:19.00
speaker: JAC
utterance:
now deleting five obviously poses some problems (be)cause it would separate the two halves of the tree.


session: S06-42
timestamp: 00:24:39.00
speaker: JAC
utterance:
so we look at its right child and we start comparing +// since five actually has a right child we start looking for the child +// the left most child.


session: S06-42
timestamp: 00:25:11.00
speaker: JAC
utterance:
what that +// what that's another way of saying left most child is actually a way of saying the child that is smallest on the right side of the tree.


session: S06-42
timestamp: 00:26:40.00
speaker: JAC
utterance:
there are no numbers on the right side smaller than it and it's not larger +// it's obviously +// conversely it's not larger than any numbers on the right side.


session: S06-42
timestamp: 00:28:10.00
speaker: JAC
utterance:
(be)cause we would never find 7.5 and we'd never find null so we would be stuck in what's called an infinite loop.


session: S06-42
timestamp: 00:28:26.00
speaker: JAC
utterance:
in case we might +// we might never look for 7.5 or anything between 7 and eight and this might never happen.


session: S06-42
timestamp: 00:28:40.00
speaker: JAC
utterance:
the difference +// this could mean it could be greater so we could fit even more numbers between seven and eight but if we're using real numbers we can fit an infinite amount of numbers, right?


session: S06-42
timestamp: 00:28:52.00
speaker: JAC
utterance:
(be)cause we can +// between seven and eight there's an infinite number of numbers (be)cause we can just keep getting smaller and smaller and smaller numbers, right?


session: S06-42
timestamp: 00:29:02.00
speaker: JAC
utterance:
uh finally we're asked to rearrange the nodes of the given binary search tree to form another binary search tree.


session: S06-42
timestamp: 00:33:04.00
speaker: JAC
utterance:
<so Carl though, the way>[//] the way the link lists work, Carl only knows who is directly behind him.


session: S06-42
timestamp: 00:33:46.00
speaker: JAC
utterance:
<now if we want to insert> +// if we want to insert [//] if g@l comes along, which I am going to call Greg, okay?


session: S06-42
timestamp: 00:34:06.00
speaker: JAC
utterance:
<he wants to know, him and> [//] Greg and Bob are friends, and he wants to know if he can cut in line.


session: S06-42
timestamp: 00:35:32.00
speaker: JAC
utterance:
so what we need to do is to take Greg and have him point to <whatever> [//] whoever Bob is pointing to, right?


session: S06-42
timestamp: 00:36:53.00
speaker: JAC
utterance:
<so what we're going to do is we are going to go through we're going to try and> [//] we first we have to find m@l.


session: S06-42
timestamp: 00:38:47.00
speaker: JAC
utterance:
now after we do that, we would remove head two because we don't want something pointing to the middle of the line, right?


session: S06-42
timestamp: 00:38:58.00
speaker: JAC
utterance:
<I don't want to be able to I don't want two people> [//] I don't want to be able to think this is the head of the line and this is the head of the line.


session: S06-42
timestamp: 00:39:12.00
speaker: JAC
utterance:
since this is already a line with it's own null, we don't have to worry about adding null or anything.


session: S06-42
timestamp: 00:39:29.00
speaker: JAC
utterance:
if I wanted to insert to list one after the node k@l +// if I wanted to insert this entire list +// I'm too popular today.


session: S06-42
timestamp: 00:40:01.00
speaker: JAC
utterance:
so we come through here, and find null, since we're inserting an entire list and have it point to whatever k@l is pointing to which in this case is Bob.


session: S06-43
timestamp: 00:00:13.00
speaker: JAC
utterance:
um what we're going to do is # +// the way we're going to think of a stack is sort of like Lego blocks.


session: S06-43
timestamp: 00:00:35.00
speaker: JAC
utterance:
every time we want to put another number into the stack what we do is put another Lego down # on top # of the one before.


session: S06-43
timestamp: 00:01:01.00
speaker: JAC
utterance:
now when we remove one we +// well, we remove from the top so we assume we can't take from the bottom.


session: S06-43
timestamp: 00:01:23.00
speaker: JAC
utterance:
if we ever wanted to know which +// what is currently there we can only look at whatever is currently at the top.


session: S06-43
timestamp: 00:01:45.00
speaker: JAC
utterance:
we have an operation just called push # which, in this case, the first thing we would have done is pushed eight.


session: S06-43
timestamp: 00:03:51.00
speaker: JAC
utterance:
but I could keep going +// if I do top right after this it's like giving me eight again (be)cause I haven't done anything to the stack.


session: S06-43
timestamp: 00:05:21.00
speaker: JAC
utterance:
we check to see if things to the right are greater than itself and +// or if things to the left are less than itself.


session: S06-43
timestamp: 00:05:42.00
speaker: JAC
utterance:
(be)cause if you want +// if someone else has a binary search tree and they were to do it where the left was greater and the right was less someone who was expecting it the other way wouldn't understand what was going on.


session: S06-43
timestamp: 00:06:19.00
speaker: JAC
utterance:
mainly I +// mainly I use the +// I refer to this as the root or the parent but you usually refer to these as children.


session: S06-43
timestamp: 00:06:26.00
speaker: JAC
utterance:
the ones to this +// the ones on this side are right children and the ones on this side are left children, okay?


session: S06-43
timestamp: 00:10:33.00
speaker: JAC
utterance:
in fact, everything on this side is less than eight and everything on the left side is greater than eight.


session: S06-43
timestamp: 00:11:21.00
speaker: JAC
utterance:
um # we start at the root because that's our way of getting into the rest of the tree and it's also possible that eight could be the root.


session: S06-43
timestamp: 00:12:25.00
speaker: JAC
utterance:
now if we're looking for four visually we can tell it's not there but if a computer is searching for it it can't look at it and see it.


session: S06-43
timestamp: 00:14:14.00
speaker: JAC
utterance:
I keep saying that we should have a bunch of sheets with this tree drawn (be)cause I found myself drawing quite a bit.


session: S06-43
timestamp: 00:16:05.00
speaker: JAC
utterance:
the next thing we're going to do is we need to look at nine's right child before +// to find who's going to replace nine's position.


session: S06-43
timestamp: 00:17:21.00
speaker: JAC
utterance:
now if we were just to delete five and not make any connections you could see we'd make two separate trees, right?


session: S06-43
timestamp: 00:17:37.00
speaker: JAC
utterance:
now we can't make nine its new +// the new parent because then eight and seven would have to be on the left side and not be on the right side.


session: S06-43
timestamp: 00:18:50.00
speaker: JAC
utterance:
so what we do is when we delete five +// when we +// we have seven come to the root and it would inherit all of five's children.


session: S06-43
timestamp: 00:19:32.00
speaker: JAC
utterance:
nine keeps its children because if we start rearranging everything we could have technically have a um a tree that goes +// if each one if these are levels, level one, level two and so forth and so on.


session: S06-43
timestamp: 00:20:09.00
speaker: JAC
utterance:
well, if it's a thousand levels deep now we have to take a thousand +// more than a thousand because each time it branches out +...


session: S06-43
timestamp: 00:20:17.00
speaker: JAC
utterance:
so we'd have to take all those nodes and we'd have to put them up on the other side that were less then.


session: S06-43
timestamp: 00:20:28.00
speaker: JAC
utterance:
it's better to find the lowest, smallest number on the left side and promote it # to the parent, okay?


session: S06-43
timestamp: 00:20:41.00
speaker: JAC
utterance:
uh # lets see +... next question asks us to rearrange the given binary search tree in a different binary search tree.


session: S06-43
timestamp: 00:25:02.00
speaker: JAC
utterance:
it doesn't matter the order we give everything on this level but we have to give this level before we do another level, okay?


session: S06-43
timestamp: 00:26:48.00
speaker: JAC
utterance:
so if I redraw this first, which this is another one that I need to have nice multiples copies of +...


session: S06-43
timestamp: 00:27:31.00
speaker: JAC
utterance:
kind of like well, if we're looking for Bob, we have to start from the head of the line, and start going through and looking for him.


session: S06-43
timestamp: 00:28:31.00
speaker: JAC
utterance:
now since I'm moving <behind Fred> [//] or in front of Fred, behind Bob, we no longer want Bob to also be in front of Fred.


session: S06-43
timestamp: 00:31:44.00
speaker: JAC
utterance:
in this case since we're talking about nodes and not people but if it was really a person it would just walk away.


session: S06-43
timestamp: 00:34:02.00
speaker: JAC
utterance:
now, since we're at something to the end of the line, if we were just adding one person, we would want to make sure they were pointing to null.


session: S06-43
timestamp: 00:34:09.00
speaker: JAC
utterance:
we're adding an entire line or link list, this is actually called, since it's a link list, it has to end in a null.


session: S06-43
timestamp: 00:34:45.00
speaker: JAC
utterance:
because we don't want, I don't want someone coming in <at and, going this> [//] and thinking that Ed is the front of the line.


session: S06-43
timestamp: 00:34:58.00
speaker: JAC
utterance:
(be)cause, well, when they start letting people look to the movie, we don't want to let these people come in first.


session: S06-43
timestamp: 00:36:32.00
speaker: JAC
utterance:
so just like what we did with the one node <we had to make that> [//] set that equal to <whatever Kim> [//] whatever has been pointed to, which in this case is Bob.


session: S06-43
timestamp: 00:38:00.00
speaker: JAC
utterance:
um for some reason I used to think there were a lot more questions in part one # which of course I never do first.


session: S06-44
timestamp: 00:00:39.00
speaker: JAC
utterance:
so um of course everything +// if this is the parent and these are its children, right children and left children.


session: S06-44
timestamp: 00:04:11.00
speaker: JAC
utterance:
so the resulting tree is +// I'm just going to do the one side because there's no point in drawing the left side because it doesn't change.


session: S06-44
timestamp: 00:05:02.00
speaker: JAC
utterance:
since five does have a right child which is nine we look for the left most child # of the right +// of this right child.


session: S06-44
timestamp: 00:05:54.00
speaker: JAC
utterance:
if we were to +// not if we were to promote nine then we'd have a problem because eight and seven are less than nine and we'd have to rework the entire tree.


session: S06-44
timestamp: 00:07:00.00
speaker: JAC
utterance:
of course, anything in a level has to be done first +// has to be # put into the binary search tree.


session: S06-44
timestamp: 00:07:06.00
speaker: JAC
utterance:
so if we just change the order so if I do seven first followed by a # eight followed by nine followed by # five followed by three # one and two, alright?


session: S06-44
timestamp: 00:09:00.00
speaker: JAC
utterance:
so we, granted that it's not a pretty tree, we changed +// just by changing the order we can get a different tree.


session: S06-44
timestamp: 00:09:10.00
speaker: JAC
utterance:
*uh # and of course if we want to add anything to the stack we can just use the push operation, right?


session: S06-44
timestamp: 00:10:09.00
speaker: JAC
utterance:
<if we want to find> [//] if we want to find a node, we'd have to start at the head, and <keep referencing> [//] keep asking each node who's next to find whichever node we're looking for.


session: S06-44
timestamp: 00:10:20.00
speaker: JAC
utterance:
so if we're looking for b@l, we have to ask c@l, and k@l, and finally k@l tells us where the b@l is.


session: S06-44
timestamp: 00:10:28.00
speaker: JAC
utterance:
<if we want to insert> [//] as we described here we want to insert a node which contains the letter g@l, into the list, after the node containing b@l.


session: S06-44
timestamp: 00:11:15.00
speaker: JAC
utterance:
*uh, if we want to add one less to the other, at the end of another, we want to concatenate them together.


session: S06-44
timestamp: 00:11:27.00
speaker: JAC
utterance:
take whatever the head of the second list is pointing to, set that equal to <where> [//] whatever the node is pointing to, so in this case, f@l.


session: S06-44
timestamp: 00:11:48.00
speaker: JAC
utterance:
so after k@l for example, you have to find k@l, just like we did with inserting one node, we just have to set the end here, and to whatever this is, and set this to whatever the head is pointing to.


session: S06-44
timestamp: 00:12:08.00
speaker: JAC
utterance:
and then have k@l point to whatever the head is pointing to, which is e@l, and then delete the head, right?


session: S06-44
timestamp: 00:12:16.00
speaker: JAC
utterance:
and if we had six and seven, then I could remember what six and seven was and we could go through six and seven.


session: S06-44
timestamp: 00:12:22.00
speaker: JAC
utterance:
um, I think they were switching nodes between each other so you would have to create a temporary node to hold the place.


session: S06-45
timestamp: 00:00:17.14
speaker: JAC
utterance:
so # *uh # I usually use lego blocks because <a lot of kids> [//] a lot of people # usually play with them when they were younger.


session: S06-45
timestamp: 00:00:44.14
speaker: JAC
utterance:
<if we> [//] if we need to take a brick off, we don't take one out of the center because we would ruin our wall.


session: S06-45
timestamp: 00:02:08.13
speaker: JAC
utterance:
what push does is it takes whatever parameter it's past so nine, whatever is in the brackets, and puts it onto the stack.


session: S06-45
timestamp: 00:03:06.04
speaker: JAC
utterance:
if we think of this as like bricks <this looks like I've written them all> [//] I've written the numbers on the side.


session: S06-45
timestamp: 00:03:54.12
speaker: JAC
utterance:
now lets say I pull the six off <and I want to get> [///] I pulled the fact that six had is on top and I want to get whatever is under six.


session: S06-45
timestamp: 00:04:47.23
speaker: JAC
utterance:
and the reason it would do that would be, if there's nothing to pop, you'd want it to return false so that you would think there was nothing else exactly like it.


session: S06-45
timestamp: 00:04:56.10
speaker: JAC
utterance:
<like if you pop nine, if nine was> [//] while this is gone pop nine but then I would try and pop whatever is after nine.


session: S06-45
timestamp: 00:07:19.22
speaker: JAC
utterance:
uh depending on how you want to be able to access the information will depend on how or what data search you use.


session: S06-45
timestamp: 00:07:29.20
speaker: JAC
utterance:
like obviously if I want to find nine in here if I had six seven eight nine, it's not very efficient because I had ot remove everything in order to find nine.


session: S06-45
timestamp: 00:07:51.29
speaker: JAC
utterance:
but um, basically, if you want whatever came in last you want it removed first and then you'd have this.


session: S06-45
timestamp: 00:08:42.14
speaker: JAC
utterance:
<um we either have> [//] like we might have three choices with yes no <with> [/] usually with binary search tree it's comparison.


session: S06-45
timestamp: 00:09:50.13
speaker: JAC
utterance:
so since everything to the right has to be greater, and everything to the left has to be less than, we can use that to try to determine if this is a binary search tree.


session: S06-45
timestamp: 00:11:25.17
speaker: JAC
utterance:
we didn't find anything that contradicted the right child having to be greater and the left child having to be less than the parent.


session: S06-45
timestamp: 00:13:13.19
speaker: 245
utterance:
+< shouldn't you, you should also, when you go to the right you check ten, and it's greater than seven.


session: S06-45
timestamp: 00:13:50.07
speaker: JAC
utterance:
I can look <when we're doing a normal> [//] when your doing a visual comparison that would be right.


session: S06-45
timestamp: 00:14:24.12
speaker: JAC
utterance:
however, when we're normally doing comparison, assuming it's built correctly, we would never have this case.


session: S06-45
timestamp: 00:14:38.16
speaker: JAC
utterance:
if we're checking to see if it's correct or not, we would want to make sure that this is larger than this, and also smaller than this.


session: S06-45
timestamp: 00:15:02.25
speaker: JAC
utterance:
we'd come back up, check its left child, which is five, smaller than seven, four, which is smaller than five.


session: S06-45
timestamp: 00:15:52.26
speaker: 245
utterance:
umm # I think if you asked me to do the last two or one of them, the last one I would have done better.


session: S06-45
timestamp: 00:16:06.29
speaker: JAC
utterance:
yeah, I'm just trying to go over, so you can understand if you have questions or if you want we can xxx/xx.


session: S06-45
timestamp: 00:16:30.10
speaker: JAC
utterance:
so we have this, this is going to be our binary search tree that we're going to use to answer the remaining questions.


session: S06-45
timestamp: 00:17:27.09
speaker: JAC
utterance:
now if you ask me to try and find a particular number, it's going to be quite difficult by looking at it.


session: S06-45
timestamp: 00:18:06.00
speaker: JAC
utterance:
assuming that we've had equal number of children on both sides, we've already eliminated half the tree.


session: S06-45
timestamp: 00:19:44.05
speaker: JAC
utterance:
that's true but if you, if everything is done correctly> [//] if everything is built correctly, then you should never have that problem.


session: S06-45
timestamp: 00:21:26.01
speaker: JAC
utterance:
but it does, even though these don't seem to be pointing at anything, they are actually pointing at something.


session: S06-45
timestamp: 00:21:52.09
speaker: JAC
utterance:
so in this case we would +// this would be out path # and the actual function would most likely turn false.


session: S06-45
timestamp: 00:22:36.00
speaker: JAC
utterance:
if I had a, like again if I had a node that was a thousand levels deep, in the worst case scenario, I would have to go a thousand levels before I can insert it.


session: S06-45
timestamp: 00:23:40.06
speaker: JAC
utterance:
we always follow the rule that the right child has to be greater, and the left child has to be less.


session: S06-45
timestamp: 00:24:30.26
speaker: JAC
utterance:
since seven is pointing to null, and six is less than seven, null is its left, than the left child is what it is, point xxx.


session: S06-45
timestamp: 00:24:58.05
speaker: JAC
utterance:
and then six just points to # six left child is null # right child is null # and left child is null.


session: S06-45
timestamp: 00:25:05.21
speaker: JAC
utterance:
so if, when we get to the point where we need to insert something, the six, say six point five, I mean we're using integers here # there's no reason we can't be using real numbers.


session: S06-45
timestamp: 00:28:18.03
speaker: JAC
utterance:
so then we have to get +// since it has a right child we will look at its right child, left most child.


session: S06-45
timestamp: 00:28:27.26
speaker: JAC
utterance:
what the left most child means is we're going to keep going down all the left children <until there are no> [//] until we find the last left child.


session: S06-45
timestamp: 00:30:40.04
speaker: JAC
utterance:
granted # we might be searching a thousand levels before we find the leftmost child, but we don't have to do manipulation to change who's who's child and who's, you know, on multiple levels.


session: S06-45
timestamp: 00:31:01.05
speaker: JAC
utterance:
or if we had done it if nine had something, if nine had ten and we deleted nine, ten would be promoted here +...


session: S06-45
timestamp: 00:31:35.25
speaker: JAC
utterance:
it doesn't matter <how big> [>] how many things are underneath the tree, it still will work in that way.


session: S06-45
timestamp: 00:32:07.26
speaker: JAC
utterance:
if you have a way of comparing something, then you have a binary search tree, or any of these data structure, a lot of these data structures.


session: S06-45
timestamp: 00:32:20.10
speaker: JAC
utterance:
so if you have people, you have to have a way to compare people you might just compare based on their name, right?


session: S06-45
timestamp: 00:33:07.25
speaker: JAC
utterance:
when you're making your binary search tree # everything in this level +// in the zero level, had to be first.


session: S06-45
timestamp: 00:33:18.15
speaker: JAC
utterance:
and our first level # the order between these two didn't matter, but they had to come before anything in the level below it.


session: S06-45
timestamp: 00:33:38.06
speaker: JAC
utterance:
and this level here # it doesn't matter the order that they come in # amongst this level, but these have to come in before whatevers in level three.


session: S06-45
timestamp: 00:33:40.04
speaker: JAC
utterance:
so obviously if we change the order of the level, if we do the trees levels, so if I did seven first for example, I would start making a totally different tree.


session: S06-45
timestamp: 00:34:00.06
speaker: JAC
utterance:
so if I make seven and um eight, and nine and eight, and three and five and two and one, make it to the end, right?


session: S06-45
timestamp: 00:35:15.01
speaker: JAC
utterance:
eight is greater than seven, eight is less than nine, so it's kind of the same tree, but not exactly (be)cause seven is here, right?


session: S06-45
timestamp: 00:35:49.22
speaker: JAC
utterance:
two is less than seven, two is less than three, three has no left child, so two becomes the left child.


session: S06-45
timestamp: 00:36:01.28
speaker: JAC
utterance:
one is less than seven, one is less than three, one is less than two, there is no left child, so it inherits one.


session: S06-45
timestamp: 00:36:21.22
speaker: JAC
utterance:
and I can change the order again, and again, and I can come up with several different binary search trees.


session: S06-45
timestamp: 00:36:34.11
speaker: JAC
utterance:
when we say balanced, we refer to the fact that the left side and the right side have the same number of nodes.


session: S06-45
timestamp: 00:38:38.03
speaker: JAC
utterance:
so that being the case ## if we want to insert a new node, or a person, for example, if I give this b@l a name, if I call it Bob, and I call this Greg <and Greg wants to> [//] Greg is looking for bob, they're friends, and he wants to get cut in line.


session: S06-45
timestamp: 00:39:50.04
speaker: JAC
utterance:
so I start at the front of the line, because hey, he might be the first person at the front of the line.


session: S06-45
timestamp: 00:41:43.04
speaker: JAC
utterance:
the way we would think about it is here is Adam, and he has been waiting in line too long and he has given up, right?


session: S06-45
timestamp: 00:43:00.07
speaker: JAC
utterance:
<we couldn't just> [///] and we don't delete him first, we have to let Ed know who # Adam is poiting to.


session: S06-45
timestamp: 00:44:06.19
speaker: JAC
utterance:
if I did, if I went about and constantly skipped over, if I did this with a whole bunch of people I xxx less than a thousand.


session: S06-45
timestamp: 00:44:19.22
speaker: JAC
utterance:
well, if each one of these is just one megabite, and the others is a thousand megabites, not a lot of computers have a gigaram, right?


session: S06-45
timestamp: 00:44:28.29
speaker: JAC
utterance:
so # if I kept doing that I kept adding people to the linked list as well, I'd start going over what ever memory I have available.


session: S06-45
timestamp: 00:45:43.19
speaker: JAC
utterance:
turns out that <both these people> [//] both these lines are waiting for the same movie and this line was formed second so we're going to add it to the end of this line.


session: S06-45
timestamp: 00:47:15.29
speaker: JAC
utterance:
okay # so we find out what the head is pointing to # we find out it's pointing to the front of the node.


session: S06-45
timestamp: 00:47:28.23
speaker: JAC
utterance:
now normally # since this is a problem, for out link list, we don't have to worry about the fact that the end of the node is pointing to null.


session: S06-45
timestamp: 00:47:48.19
speaker: JAC
utterance:
I guess your getting a link list form somebody you don't know, you want to make sure you have null, right?


session: S06-45
timestamp: 00:48:13.15
speaker: JAC
utterance:
um # well # we're basing it on the directions which is describe a sequence of operations to add list tow to the end of list one.


session: S06-45
timestamp: 00:48:24.19
speaker: JAC
utterance:
<so we> [//] if we were to do that we would say we would search through the list and find out who is pointing to null.


session: S06-45
timestamp: 00:48:39.19
speaker: JAC
utterance:
and you could say assume that *uh, link list two was built correct, it shows that it's built correct.


session: S06-45
timestamp: 00:48:47.12
speaker: JAC
utterance:
but if it was, they didn't even show you the list and they asked you to do that, you say you find out what pointing to null and set it to whatever the other head is pointing to.


session: S06-45
timestamp: 00:51:14.11
speaker: JAC
utterance:
now if we're asked as a question, we would say we'd find Kim, or find k@l, find what that's pointing to.


session: S06-45
timestamp: 00:52:25.09
speaker: JAC
utterance:
but the way everything, the way convention is done, we always check the right children first before we check the left children.


session: S06-45
timestamp: 00:52:33.06
speaker: JAC
utterance:
so if this was a thousand nodes deep, we would check everyone's right child first, before we check the single left child.


session: S06-45
timestamp: 00:52:45.25
speaker: JAC
utterance:
so if we were <that's if we're looking for, if we're looking for a *uh> [///] if we're checking to see if it's a binary search tree or not.


session: S06-45
timestamp: 00:53:14.25
speaker: JAC
utterance:
because think about it # each time we look at this tree # um # if this is level zero # this is one to the zero, right?


session: S06-45
timestamp: 00:54:20.16
speaker: JAC
utterance:
but worst case would be # if your trying to figure it out, you'd have sixty eight or sixty four, a hundred and twenty eight, and keep going.


session: S06-45
timestamp: 00:54:53.08
speaker: JAC
utterance:
so the total +// and that's just this one +// this is just the one level, that's not including everything that's here.


session: S06-45
timestamp: 00:55:17.08
speaker: JAC
utterance:
I mean, I know professors that could potentially do it, but they are rational enough to be like, I have to grade this.


session: S06-45
timestamp: 00:55:30.20
speaker: JAC
utterance:
you know, if I made something ten nodes and I'm trying to figure out if it's a binary search tree or not that could take all the whole exam period.


session: S06-45
timestamp: 00:55:44.03
speaker: JAC
utterance:
so um +// yeah but right off, which I have to write, and that five tells us right away that this is not a binary search tree, okay?


session: S06-45
timestamp: 00:56:05.01
speaker: JAC
utterance:
or if this would have to be like a twenty four, and then this would have to be a *uh, this could never be seven.


session: S06-45
timestamp: 00:56:17.24
speaker: JAC
utterance:
it just +// I mean it's even, just looking at this, trying to make it some what accurate wouldn't work.


session: S06-45
timestamp: 00:56:24.10
speaker: JAC
utterance:
so but basically what happened was that the left child +// they decided that the, everything on the left would be greater, and everything on the left would be less than that.


session: S06-45
timestamp: 00:56:38.00
speaker: JAC
utterance:
every +// all the right children are either greater than the parent, all the left children are less than the parent.


session: S06-45
timestamp: 00:57:09.28
speaker: JAC
utterance:
um # and of course, following this then <well what if I try> [//] what if my left child is equal to the parent, right?


session: S06-45
timestamp: 00:58:02.03
speaker: JAC
utterance:
so if I try to insert eight three times, the value would still be eight, but the counter would be three.


session: S06-45
timestamp: 00:58:14.16
speaker: JAC
utterance:
there's no point in me trying to add eight here, anywhere in the tree, because it's not going to fit anywhere else.


session: S06-45
timestamp: 00:58:41.22
speaker: JAC
utterance:
so # at some point, I can go through the whole tree and say okay, how many sets, I +// starting at the root find out how many sevens I have.


session: S06-45
timestamp: 00:59:36.13
speaker: JAC
utterance:
<you can do it, you can put> [///] anyway you set it up you can just have it hold whatever you want.


session: S06-45
timestamp: 01:00:13.05
speaker: JAC
utterance:
and I might decide instead to use everyone's U@l_I@l_N@l, because U@l_I@l_N@l's are different, right?


session: S06-45
timestamp: 01:00:18.24
speaker: JAC
utterance:
so # when your actually designing this you might figure out, okay, U@l_I@l_N@l's, or maybe in order to distinguish someone.


session: S06-45
timestamp: 01:00:41.27
speaker: JAC
utterance:
<and then you could find> [//] once you find the U@l_I@l_N@l, you could say, okay, whats this informaoitn about this person?


session: S06-45
timestamp: 01:00:48.25
speaker: JAC
utterance:
well, you can find their name, their year in school +// you could have all their information stored, their year in school, *uh, you know +...


session: S06-45
timestamp: 01:00:57.06
speaker: 245
utterance:
so that's kind of like how a computer is like, how a program would be to work like for a student at U@l_I@l_C@l?


session: S06-45
timestamp: 01:01:06.14
speaker: JAC
utterance:
<I mean that's one> [///] usually they use database, but if they wanted to make something simple they could xxx a binary search tree, and search quickly.


session: S06-46
timestamp: 00:00:34.00
speaker: JAC
utterance:
with a stack if I want to look and see what a particular brick +// like lets say that each one of these bricks are numbered.


session: S06-46
timestamp: 00:00:46.00
speaker: JAC
utterance:
if I want to find out what the number of this brick +// what the number of a brick is I can only find out what the number is on top.


session: S06-46
timestamp: 00:03:36.00
speaker: JAC
utterance:
but if it executes unsuccessfully, say if there was nothing left in the stack to pop off it might return +// it probably would return false.


session: S06-46
timestamp: 00:05:24.00
speaker: JAC
utterance:
um you could be doing it in um memory or certain operations may be put into memory and you'd have to perform them in order.


session: S06-46
timestamp: 00:05:50.00
speaker: JAC
utterance:
so and then in that case whatever was last is +// whatever was put in first is the last thing to come out.


session: S06-46
timestamp: 00:05:58.00
speaker: JAC
utterance:
um so certain operations are put in the stack or if you have a line you might use a stack to create a queue, right?


session: S06-46
timestamp: 00:06:27.00
speaker: JAC
utterance:
you know but if it's uh +// but in this case we're using numbers (be)cause numbers are usually the simplest thing to look at or refer to, right?


session: S06-46
timestamp: 00:10:32.00
speaker: JAC
utterance:
the right child is always greater than the parent and the left child is always less than the parent.


session: S06-46
timestamp: 00:10:37.00
speaker: JAC
utterance:
so 11 +// if we want to find if this is a binary search tree or not we look at the right child first.


session: S06-46
timestamp: 00:11:06.00
speaker: JAC
utterance:
if it pointed to something we would keep going down and checking it until there were no more right childs.


session: S06-46
timestamp: 00:12:03.00
speaker: JAC
utterance:
I'll show you when we get to building a tree that if the tree is built correctly the way this is setup will always be the case.


session: S06-46
timestamp: 00:12:14.00
speaker: JAC
utterance:
you can never +// the rule of left child being less and right child being greater will never be violated.


session: S06-46
timestamp: 00:15:00.00
speaker: JAC
utterance:
now always remember that when we check we check right child first and then left child so you don't get them confused.


session: S06-46
timestamp: 00:16:24.00
speaker: JAC
utterance:
right away, (be)cause like I said the right always has to be greater and the left always has to be less.


session: S06-46
timestamp: 00:16:59.00
speaker: JAC
utterance:
so first thing I'm going to do is I'm going to rebuild it # just so I can show +// so I can write on it and not distort this any further for the next questions, right?


session: S06-46
timestamp: 00:17:44.00
speaker: JAC
utterance:
so if eight does exist in this tree then it has to be to the right # because eight is greater than five.


session: S06-46
timestamp: 00:17:57.00
speaker: JAC
utterance:
eight is less than nine so since this tree is built correctly eight has to be to the left +// be the left child of nine.


session: S06-46
timestamp: 00:19:39.00
speaker: JAC
utterance:
(be)cause there's +// based on the way we're looking at it four has to be here or further down the line if there were more nodes, right?


session: S06-46
timestamp: 00:20:25.00
speaker: JAC
utterance:
well, there's no point in me trying to search for where to insert four if I need to insert it, right?


session: S06-46
timestamp: 00:20:42.00
speaker: JAC
utterance:
so I could return this null, this dead end and set this point to four and have this xx four and then have that have its null.


session: S06-46
timestamp: 00:20:53.00
speaker: JAC
utterance:
well, you would just come here and I would say, four and have it point +// this should be here but +// just going to overlap a little.


session: S06-46
timestamp: 00:21:18.00
speaker: JAC
utterance:
if everything +// if we came here everything that pointed to null +// I have a null here, a null here, two nulls here, two nulls here, there's too much, right?


session: S06-46
timestamp: 00:23:33.00
speaker: JAC
utterance:
you can +// basically you would say, search for six and once you found null you insert six wherever null is.


session: S06-46
timestamp: 00:23:48.00
speaker: JAC
utterance:
each node has the property of a value and it has a pointer to the left child and a pointer to the right child.


session: S06-46
timestamp: 00:24:03.00
speaker: JAC
utterance:
initially, each of these are set to null and if +// we just keep searching and we check, okay what is its left child.


session: S06-46
timestamp: 00:24:15.00
speaker: JAC
utterance:
if it's +// if you ever find that it equaled null then you would insert +// you would set this equal to six.


session: S06-46
timestamp: 00:25:29.00
speaker: JAC
utterance:
we check its left +// we take its left child and we promote +// we make its left child take the place of nine.


session: S06-46
timestamp: 00:26:53.00
speaker: JAC
utterance:
what that means is we keep finding +// keep going until we can't find any more children on the left, okay?


session: S06-46
timestamp: 00:29:47.00
speaker: JAC
utterance:
we don't want to move everything up here because then that's going to completely change the structure of the tree.


session: S06-46
timestamp: 00:30:26.00
speaker: JAC
utterance:
so lets move on and the final question asks us to rearrange the nodes to give us a new binary search tree.


session: S06-46
timestamp: 00:30:56.00
speaker: JAC
utterance:
I can insert it with five first and then I could have inserted nine and then two or I could have inserted two then nine.


session: S06-46
timestamp: 00:31:34.00
speaker: JAC
utterance:
so if I build this to make a different tree I can make seven then eight then nine then three, five, two and one.


session: S06-46
timestamp: 00:33:42.00
speaker: JAC
utterance:
now I have a completely different binary search tree than the one that I had before it still uses the same numbers.


session: S06-46
timestamp: 00:35:17.00
speaker: JAC
utterance:
so if I'm looking for the number 1,000 I have to look through a thousand blocks before I find 1,000, right?


session: S06-46
timestamp: 00:35:27.00
speaker: JAC
utterance:
but in this case here if I have my tree built every time I make a decision I cut out half of my choices, right?


session: S06-46
timestamp: 00:35:55.00
speaker: JAC
utterance:
five, # six +// and this isn't a balanced tree but if it was balanced it would make more of a difference.


session: S06-46
timestamp: 00:36:32.00
speaker: JAC
utterance:
I've limited it to one, two, three, four, five, six of your choices that you would have made +// six of your comparisons that you would have made with your array.


session: S06-46
timestamp: 00:36:52.00
speaker: 246
utterance:
hmm but is there a way to write it out to, you know, xxx or just xxx xxx and the position you want to find it?


session: S06-46
timestamp: 00:37:05.00
speaker: JAC
utterance:
you always have to do +// you always do a search in a tree because you don't know exactly where something is.


session: S06-46
timestamp: 00:37:50.00
speaker: JAC
utterance:
and if you're +// if you're looking +// if you're doing a lot of searching for certain values but you don't know exactly where it's stored then you can do this.


session: S06-46
timestamp: 00:38:40.00
speaker: JAC
utterance:
each person, or in case these are referred to as nodes, each node only knows who's directly behind it.


session: S06-46
timestamp: 00:39:30.00
speaker: JAC
utterance:
now, in that case, if we want to insert a new node, containing g@l, if we give these people names we can call them Carl, Kim, and Bob, and Fred.


session: S06-46
timestamp: 00:39:43.00
speaker: JAC
utterance:
if Greg wants to get in the line <first thing Greg has> [//] first thing we have to do is <go to the head and find out> [//] go to the front of the line, right?


session: S06-46
timestamp: 00:42:31.00
speaker: JAC
utterance:
<but this is just straight> [//] this is actually kind of the one way to make it look like an array.


session: S06-46
timestamp: 00:42:46.00
speaker: JAC
utterance:
<if everything is> [//] if I have an array from zero to ten, or zero to nine rather, if I fill from zero to seven, and I want to add something, I can't add without overwriting, right?


session: S06-47
timestamp: 00:00:23.00
speaker: JAC
utterance:
so with our Lego blocks uh the way stack works is we lay one Lego block down or one item in the stack down.


session: S06-47
timestamp: 00:00:39.00
speaker: JAC
utterance:
so um and then if we want to add another value or anything else to the stack we have to add it on top.


session: S06-47
timestamp: 00:02:57.00
speaker: JAC
utterance:
I could have done +// I could have mixed it up with a few of these but I'm not going to confuse you.


session: S06-47
timestamp: 00:03:04.00
speaker: JAC
utterance:
I don't know +// lets say I leave if for a couple minutes and I come back I'm sure I have very bad memory and I can't remember what I did, okay?


session: S06-47
timestamp: 00:03:17.00
speaker: JAC
utterance:
if I call top what it's going to return is whatever the value on top is so it's going to give me six.


session: S06-47
timestamp: 00:04:34.00
speaker: JAC
utterance:
if there's no stack +// if there's nothing in the stack and I try and pop, pop may +// could do uh what it most likely does.


session: S06-47
timestamp: 00:06:50.00
speaker: JAC
utterance:
so we can compare numbers and we can see that the value seven is less than 11 +// or 11 is greater than seven, right?


session: S06-47
timestamp: 00:07:25.00
speaker: JAC
utterance:
but the rule always has to imply that the right child is greater than the parent and the left child is less than the parent.


session: S06-47
timestamp: 00:07:48.00
speaker: 247
utterance:
make sure everything going to the right is greater and make sure everything to the left is less than.


session: S06-47
timestamp: 00:08:25.00
speaker: JAC
utterance:
if 12 +// if for some reason 12 was less than seven but +// this would have to be our first mistake.


session: S06-47
timestamp: 00:09:06.00
speaker: JAC
utterance:
we don't +// when we're doing our comparisons we would go back because we wouldn't want to keep going back and forth back and forth to check everything.


session: S06-47
timestamp: 00:10:03.00
speaker: JAC
utterance:
but we would go +// if we did it +// obviously we can see it but if a computer was checking it it wouldn't be able to see it.


session: S06-47
timestamp: 00:11:36.00
speaker: JAC
utterance:
this is what happens +// if someone tries to violate the rules and change them around we end up with something like this.


session: S06-47
timestamp: 00:11:44.00
speaker: JAC
utterance:
obviously that's why we follow these rules so it's always the same and everyone knows what's going on.


session: S06-47
timestamp: 00:11:50.00
speaker: JAC
utterance:
if we decided to make our binary search tree anyway we want then someone else tries to use it then it'll work the way we don't expect it.


session: S06-47
timestamp: 00:13:37.00
speaker: JAC
utterance:
probably more than would fit on a sheet of paper or even it wasn't on a sheet of paper it would be really xxx.


session: S06-47
timestamp: 00:18:20.00
speaker: JAC
utterance:
if nine had a right child we would start looking at everyone's left child until there were no more left children.


session: S06-47
timestamp: 00:18:29.00
speaker: JAC
utterance:
no we would actually +// what we would actually do is take that left child up and promote it to where nine is.


session: S06-47
timestamp: 00:18:56.00
speaker: JAC
utterance:
since eight +// since nine has a left child this left child will get promoted to the position that nine is in.


session: S06-47
timestamp: 00:19:04.00
speaker: JAC
utterance:
if there was no left child and no right child we could delete nine and have no problem and set five's pointer to null.


session: S06-47
timestamp: 00:20:06.00
speaker: JAC
utterance:
+< each child will only know +// each parent knows who its children are but we don't know who its parents are.


session: S06-47
timestamp: 00:20:12.00
speaker: JAC
utterance:
there are +// there are trees or you may design trees that do know who their parents are # which in that case we call it a doubly linked.


session: S06-47
timestamp: 00:22:18.00
speaker: 247
utterance:
now what if it wasn't seven but what if seven had that left side keep going down so it was less than two?


session: S06-47
timestamp: 00:22:35.00
speaker: JAC
utterance:
every time I make an insertion +// if I make +// assuming that everything is built correctly if I insert four four has to come here.


session: S06-47
timestamp: 00:22:58.00
speaker: 247
utterance:
well if you just look at it individually it just has to be less than seven, less than seven, less than seven but if you take it so you can go six, five, four, three, two, one +...


session: S06-47
timestamp: 00:23:19.00
speaker: JAC
utterance:
so while seven is promoted we didn't do anything to this side so we're just going to redraw it, right?


session: S06-47
timestamp: 00:24:56.00
speaker: JAC
utterance:
and vice versa the right most +// if we come here to the left and find the right most child it's the largest number on this side, right?


session: S06-47
timestamp: 00:25:18.00
speaker: JAC
utterance:
so now our final question about binary search tree is to rearrange the nodes # given this binary search tree to form another binary search tree.


session: S06-47
timestamp: 00:25:37.00
speaker: 247
utterance:
you basically +// it doesn't really matter what number you start with you just follow the rules and assemble it?


session: S06-47
timestamp: 00:25:43.00
speaker: JAC
utterance:
now we could start with five but right away if we start with five then we're already kind of mimicking the tree.


session: S06-47
timestamp: 00:26:29.00
speaker: JAC
utterance:
so I could build this a couple of different ways and still come up with the same binary search trees, right?


session: S06-47
timestamp: 00:26:54.00
speaker: 247
utterance:
we can just go nine, eight, seven, five, three, two, one and just draw in all on the right side +...


session: S06-47
timestamp: 00:29:26.00
speaker: JAC
utterance:
so c@l only knows that k@l is behind it, k@l only knows that b@l is behind it, b@l only knows that f@l is behind it, f@l knows that there's nothing behind it.


session: S06-47
timestamp: 00:29:55.00
speaker: JAC
utterance:
so if this is the case, and we want to insert a person or a node, and we'll give them names, this is Carl, this is Kim, this is Bob, this is Fred.


session: S06-47
timestamp: 00:34:22.00
speaker: JAC
utterance:
now if I have a thousand, if I delete it and I have another one, then a thousand more megabytes doesn't fit the memory anymore.


session: S06-47
timestamp: 00:35:07.00
speaker: JAC
utterance:
so # we're going to describe a sequence of opperations to add a list two to list one at the end of the list.


session: S06-47
timestamp: 00:39:36.00
speaker: JAC
utterance:
you could check to see how many children are out, how many children are on the left and children on the right, and balance it every time you insert something.


session: S06-47
timestamp: 00:39:47.00
speaker: JAC
utterance:
so what I can do is promote have eight some up here, so if I have five, have eight come here, and have nine be it's right child, and seven it's left child.


session: S06-47
timestamp: 00:40:03.00
speaker: JAC
utterance:
the xx +// another type of tree would allow us, every time you search for something you bring it to the top.


session: S06-47
timestamp: 00:40:30.00
speaker: JAC
utterance:
obviously if you want it to be efficient for searching, you would want to have everything that you search for most frequently on top.


session: S06-47
timestamp: 00:40:50.00
speaker: 247
utterance:
if you know you're looking for it and you just accessed it a couple days ago or whatever, go down one.


session: S06-48
timestamp: 00:00:27.23
speaker: JAC
utterance:
if you want to add something else onto the stack, you have to put it on top of the previous block, okay?


session: S06-48
timestamp: 00:00:39.29
speaker: JAC
utterance:
now anytime you want to take one off, you can't take one out from the middle, because that destroys everything, right?


session: S06-48
timestamp: 00:01:14.17
speaker: JAC
utterance:
what push does is take whatever value it's past, so it's given nine, so what it does is it puts nine onto the stack.


session: S06-48
timestamp: 00:01:56.16
speaker: JAC
utterance:
now one of the key things with the stack is, you can't just pull information anywhere out of the stack.


session: S06-48
timestamp: 00:02:15.29
speaker: JAC
utterance:
basically if you think about it, if we look down a bunch of Lego blocks, right, you can only look right down on the top one.


session: S06-48
timestamp: 00:04:20.27
speaker: JAC
utterance:
<you have *uh> [//] you always make a comparison, you call this our parent, out parent node, or the root.


session: S06-48
timestamp: 00:07:48.13
speaker: JAC
utterance:
so now # the next questions we're going to use this binary search tree in order to answer the xxx following questions.


session: S06-48
timestamp: 00:10:06.19
speaker: JAC
utterance:
we ever don't +// basically if we ever come across, we would find null to not four, then if not the tree.


session: S06-48
timestamp: 00:10:29.01
speaker: JAC
utterance:
<so we're comparing, we would have to> [//] it's less than five, so it has to be, it has to be on the side of the tree, right?


session: S06-48
timestamp: 00:10:38.20
speaker: JAC
utterance:
we come here, and it's greater than two, so it's, we've eliminated here, we've eliminated all this, right?


session: S06-48
timestamp: 00:11:02.12
speaker: JAC
utterance:
we could have three point five here  <and then we could have had> [//] keep going until we eventually got to a point where four had to be there.


session: S06-48
timestamp: 00:11:58.21
speaker: JAC
utterance:
so (be)cause if I want to add it, if I want to add four, then I'm going to have to follow that same path to insert it.


session: S06-48
timestamp: 00:12:03.19
speaker: JAC
utterance:
<now if I have tree, if I have tree that's> [//] if I call each of these levels, level zero, level one, level two, level three, your tree could be a thousand levels deep or even more right?


session: S06-48
timestamp: 00:15:38.22
speaker: JAC
utterance:
but the advantage to having null is if you ever find it, your looking for something, one, you know it's not there, two you can return that, and you can set that null, that null value to something else.


session: S06-48
timestamp: 00:18:42.02
speaker: JAC
utterance:
if I was to take nine, <and make it the xxx> [//] and take the place of five, than eight and seven are now on the wrong side of the tree.


session: S06-48
timestamp: 00:18:59.13
speaker: JAC
utterance:
so what we need to do is find a way to have an appropriate value up here, that doesn't destroy the prior structure of the tree to do a lot of excessive work.


session: S06-48
timestamp: 00:20:27.28
speaker: JAC
utterance:
otherwise, is I was looking for seven and a half, seven and a half is greater than seven, if they were like still linked, right?


session: S06-48
timestamp: 00:20:35.09
speaker: JAC
utterance:
seven and a half is greater than nine, seven and a half, I'm sorry seven and a half is greater than seven, seven and a half is less than nine, seven and a half is less than eight, seven and a half is greater than seven, so we, we'd end up in an infinite loop, right?


session: S06-48
timestamp: 00:21:32.23
speaker: JAC
utterance:
now the left most child, which hasn't become apparent, is the smallest number on the side of the tree.


session: S06-48
timestamp: 00:22:16.19
speaker: JAC
utterance:
<anything in this level, when we look at the levels> [/] anything in this level, level zero, had to be put into the tree before anything else.


session: S06-48
timestamp: 00:22:26.23
speaker: JAC
utterance:
<anything in level one though> [/] anything in level one, had to come before the following levels, level two and level three.


session: S06-48
timestamp: 00:25:01.22
speaker: JAC
utterance:
now, so whatever was in this level, two had to come before one and three, nine had to come before eight, and seven, if we're looking at this one.


session: S06-48
timestamp: 00:25:48.03
speaker: JAC
utterance:
a comparison I like to make with link lists is a movie theater line, or a caffeteria line, or any kind of line.


session: S06-48
timestamp: 00:25:55.29
speaker: JAC
utterance:
we have a head, which tells us where the front of the line is, and we have nodes, which we can think of as people in line.


session: S06-48
timestamp: 00:26:12.26
speaker: JAC
utterance:
okay basically, they can turn the head, look around, and see the face of the person directly behind them.


session: S06-48
timestamp: 00:26:18.13
speaker: JAC
utterance:
but they can't see the person behind the map, because they can't see their face, so they don't know who they are.


session: S06-48
timestamp: 00:27:42.03
speaker: JAC
utterance:
since nobody, you can't just go up and find, just look, in the middle of y@l # he has start in the front, okay?


session: S06-48
timestamp: 00:32:27.25
speaker: JAC
utterance:
so we look through the line, and we look through so we go to start at the head so we look here, look here, which.


session: S06-48
timestamp: 00:33:19.23
speaker: JAC
utterance:
now # since we're just adding to the end of the line, and this is already a correctly formed line or link list, right?


session: S06-48
timestamp: 00:33:40.16
speaker: JAC
utterance:
<but since we made everything> [//] we made these lines and everything, we know there's a null, okay?


session: S06-48
timestamp: 00:33:51.09
speaker: JAC
utterance:
we have a head that points to the front of the line, and a head that points to the end, to the middle of the line, right?


session: S06-48
timestamp: 00:35:36.06
speaker: JAC
utterance:
so we go to the head first, and we go all the way through until we find whoever is pointing to the head of the line.


session: S06-48
timestamp: 00:35:45.11
speaker: JAC
utterance:
if it was just one big, thought of as one person, there was the entrance to the person, and there was the exit.


session: S06-48
timestamp: 00:36:59.11
speaker: JAC
utterance:
okay, um # so if I remember right, one of the questions asked us to take Adam or Amanda as I circle here, and Kim, and have them switch places.


session: S06-48
timestamp: 00:37:20.28
speaker: JAC
utterance:
<because we can't just take Amanda> [//] we can't just take her out of the line because we don't know here she was.


session: S06-48
timestamp: 00:37:54.28
speaker: JAC
utterance:
now that that +// whatever +// whichever node you're trying to switch is free, you look for your temporary node.


session: S06-48
timestamp: 00:38:15.12
speaker: JAC
utterance:
so here's a temporary, find out what Amanda's pointing to +// Amanda's pointing to, find out who's pointing to Amanda, change those, now this is three.


session: S06-48
timestamp: 00:38:42.02
speaker: JAC
utterance:
set this equal to which ever one it's pointing to, set this equal to whatever that's pointing to, now this is free, right?


session: S06-49
timestamp: 00:00:11.00
speaker: JAC
utterance:
the way I like to make my comparison to the stack is to Legos, and just like Legos, every time you want to put them in something on the stack you put down a Lego.


session: S06-49
timestamp: 00:00:38.19
speaker: JAC
utterance:
now when we want to remove one of our items from the stack, or one of our Legos, we can't take something out of the center.


session: S06-49
timestamp: 00:01:26.27
speaker: JAC
utterance:
I'm numbering these here so that you know there is information in them, but you can't actually see it.


session: S06-49
timestamp: 00:03:43.05
speaker: JAC
utterance:
so I find, this would be on top here, but obviously I don't have an erasable pen so I can't do anything.


session: S06-49
timestamp: 00:04:18.04
speaker: JAC
utterance:
in life we have to guess between choices, in a binary search tree what we have is a, you can think of it as a family tree.


session: S06-49
timestamp: 00:07:15.01
speaker: JAC
utterance:
it has no children, we have to go check four's left child, it has no left child, go back up to seven.


session: S06-49
timestamp: 00:07:44.18
speaker: JAC
utterance:
twelve has no children, we go back up to eleven, check its left child, it's ten, which is less than eleven.


session: S06-49
timestamp: 00:08:03.19
speaker: JAC
utterance:
but since eight is over here, and the right child has to be greater, than the parent, this can't be a binary search tree.


session: S06-49
timestamp: 00:08:30.01
speaker: JAC
utterance:
ten greater then seven, we check its left child eight, eight is less than ten, and greater than seven.


session: S06-49
timestamp: 00:08:44.16
speaker: JAC
utterance:
it has no right child, its left child is four, four is less than five, four has no children, it would return to five, trying to seven, turn into eleven.


session: S06-49
timestamp: 00:10:36.10
speaker: JAC
utterance:
so we have to find, we have to develop a way that is very methodical and um an algorithm in order to find anything without having any problems.


session: S06-49
timestamp: 00:11:00.07
speaker: JAC
utterance:
step one, always start at the root, and we make our comparison to what we're searching for, and whatever the value is at the root, O_K_?


session: S06-49
timestamp: 00:13:29.27
speaker: JAC
utterance:
O_K_, now obviously we can't, if we put null every time there is no children, we're going to have a whole bunch of nulls in the tree, so it's going to get very ugly.


session: S06-49
timestamp: 00:13:49.23
speaker: JAC
utterance:
but since null is here, and four had to be here, further down the path, if there is anything else, four is not in the tree.


session: S06-49
timestamp: 00:15:50.17
speaker: JAC
utterance:
so when we found the null, there is nothing else to be trying to see if six is to the left child or to the right, right?


session: S06-49
timestamp: 00:17:59.26
speaker: JAC
utterance:
I'm going to show you a case where something has the right child, I'm going to show you how to do that as well.


session: S06-49
timestamp: 00:19:45.22
speaker: JAC
utterance:
so we obviously can't make two inherit, because if that was the case, three needs to be the right child.


session: S06-49
timestamp: 00:20:12.27
speaker: JAC
utterance:
if it had no right children, then this would get deleted, and then two would become the new parent, right?


session: S06-49
timestamp: 00:20:57.06
speaker: JAC
utterance:
O_K_, so we're looking for the left most great great great great grandchild or something in between.


session: S06-49
timestamp: 00:21:34.17
speaker: JAC
utterance:
if I had six we would insert four, it would have been the left most child, and it would have been the smallest number.


session: S06-49
timestamp: 00:22:42.04
speaker: JAC
utterance:
seven point five would be less than eight, less than nine, seven point five would be less than eight, this is its left child, right?


session: S06-49
timestamp: 00:23:00.12
speaker: JAC
utterance:
because obviously if we look for seven point five, or anything between seven and eight, any value, we'll get stuck in an infinite loop.


session: S06-49
timestamp: 00:23:15.15
speaker: JAC
utterance:
so we would have to delete this connection here between eight and seven, so that eight has no left children, it would just point to null.


session: S06-49
timestamp: 00:23:50.28
speaker: JAC
utterance:
we are asked to rearrange the nodes and give a binary search tree to form a different binary search tree.


session: S06-49
timestamp: 00:25:29.07
speaker: JAC
utterance:
so obviously if I make seven, instead of it being at the very root of the tree, it's at the very top, O_K_?


session: S06-49
timestamp: 00:25:59.18
speaker: JAC
utterance:
five is less than seven, five is greater than three, three has no children, five becomes the right child of three.


session: S06-49
timestamp: 00:26:48.13
speaker: JAC
utterance:
and we could have +// it doesn't matter as much as the order does, to an extent make some difference, and also at some point doesn't make a difference.


session: S06-49
timestamp: 00:26:58.20
speaker: JAC
utterance:
since whatever, if we look here, whatever is on the right had to come before, nine had to come before eight, eight had to come before seven.


session: S06-49
timestamp: 00:27:10.08
speaker: JAC
utterance:
however, nine could have come in, could have been inserted anytime before or after this site, right?


session: S06-49
timestamp: 00:27:28.24
speaker: JAC
utterance:
O_K_, so we're going to try and reorder the tree, we can use the fact that these facts to build the tree.


session: S06-49
timestamp: 00:28:15.10
speaker: JAC
utterance:
granted with the numbers that we have pretty much stuck with the fact that one side is going to have one or two nodes and the other side will always be very heavy.


session: S06-49
timestamp: 00:29:40.10
speaker: JAC
utterance:
so imagine that <they can only turn around> [//] they can look back, but they can only see the face of the person behind them.


session: S06-49
timestamp: 00:30:52.05
speaker: JAC
utterance:
so we're gonna, out analagy will be that Greg knows Bob, and is going to cut behind Bob in line, O_K_?


session: S06-49
timestamp: 00:31:45.29
speaker: JAC
utterance:
so the first thing we have to do is find, go to the head, and find out who the first person in line is.


session: S06-49
timestamp: 00:32:44.07
speaker: JAC
utterance:
even though people are cutting, they are still keeping a similar order making sure the line is single file.


session: S06-49
timestamp: 00:32:56.26
speaker: JAC
utterance:
now we couldn't just delete our connection to Fred, and then point to Greg, and then try and point to Fred.


session: S06-49
timestamp: 00:34:13.03
speaker: JAC
utterance:
so we start with the head, reference the first person in line, which is Ed, and we ask Ed who's next.


session: S06-49
timestamp: 00:35:12.23
speaker: JAC
utterance:
now obviously we had to make this connection first because if Amanda deletes her connection to Mary, now Ed doesn't know who's behind Amanda, O_K_?


session: S06-49
timestamp: 00:37:11.18
speaker: JAC
utterance:
and the movie theater finds out that both these lines are waiting for the same movie, and that this line was here first.


session: S06-49
timestamp: 00:38:10.03
speaker: JAC
utterance:
now if we wanted to insert this in the middle, behind somebody, we could have thought of this just as one node.


session: S06-49
timestamp: 00:38:27.24
speaker: JAC
utterance:
we connect it with Bob, so we insert Kim, and have Kim insert, point to Ed, and then delete the head, right?


session: S06-50
timestamp: 00:00:21.21
speaker: JAC
utterance:
there is *uh, we lay a brick down, and every time we put something else on the stack we always lay on top of the previous one.


session: S06-50
timestamp: 00:01:05.07
speaker: JAC
utterance:
we're using numbers just because it's easy to make comparisons, you know I don't want to use names or something long that takes a long time to write.


session: S06-50
timestamp: 00:02:05.10
speaker: JAC
utterance:
i don't, I can put anything in any order, it doesn't have to matter, I just use numbers in sequential order.


session: S06-50
timestamp: 00:02:11.26
speaker: JAC
utterance:
now, now that I've put these items, if I want to find out any information about them, the only information that I can find out, is by calling a method called top.


session: S06-50
timestamp: 00:03:12.09
speaker: JAC
utterance:
we can put it, we could have pushed it on, we could have pushed all the stuff on, left it, come back, a week later, a few hours later, we don't know whats on the stack.


session: S06-50
timestamp: 00:04:18.22
speaker: JAC
utterance:
but once it's, once I remove everything on the stack, if I try and pop, it's not going to do anything.


session: S06-50
timestamp: 00:05:08.17
speaker: JAC
utterance:
but um, just trying to be concerned with the general way of  the data structure, and conceptually how it works.


session: S06-50
timestamp: 00:05:15.25
speaker: JAC
utterance:
i might go into a little detail from time to time but I will try not to be overly excessive with detail.


session: S06-50
timestamp: 00:05:44.20
speaker: 250
utterance:
why is that called a binary search tree, because you see, a null, this is the binary, but this is not binary, right?


session: S06-50
timestamp: 00:05:53.10
speaker: JAC
utterance:
<we don't have to have> [//] we don't have to have, each, if we call this a parent, these are it's children.


session: S06-50
timestamp: 00:07:17.12
speaker: JAC
utterance:
i might have the value, and I also might keep track of the number of times that that number is entered.


session: S06-50
timestamp: 00:07:58.08
speaker: JAC
utterance:
any time we're checking to see if this is a binary search tree, or we're doing any insertions or deletions, these two rules have to hold true all the time.


session: S06-50
timestamp: 00:09:18.06
speaker: JAC
utterance:
ten is less than twelve, but it can't be it's child because then ten would have had to go, ten is not greater than eleven.


session: S06-50
timestamp: 00:09:24.07
speaker: JAC
utterance:
what I would have come to, when ten is going to be inserted, it would have followed the path, and it would have checked against eleven, ten would have been less than eleven.


session: S06-50
timestamp: 00:12:26.09
speaker: JAC
utterance:
this is the way it always has to be, because we don't want to make it this way, if someone might expect it this way.


session: S06-50
timestamp: 00:12:39.16
speaker: JAC
utterance:
so we're going to use this binary search tree, why don't you answer some of the questions that we have here.


session: S06-50
timestamp: 00:13:14.21
speaker: JAC
utterance:
it could be, you could use negative numbers, but then if nine was negative, it could be here it would be to the left of five.


session: S06-50
timestamp: 00:13:38.23
speaker: JAC
utterance:
whatever I can make a comparison on, or I can determine which one is greater than the parent, one is less than the parent, then eight can be used in it's binary search tree, O_K_?


session: S06-50
timestamp: 00:14:32.04
speaker: 250
utterance:
because in this way, you see this is nine, and this has to be eight, seven, and six, and then it can't be five, right?


session: S06-50
timestamp: 00:14:54.19
speaker: JAC
utterance:
now if I had a thousand levels, and each time Im doubling, I can be actually doubling the number of children on each level, right?


session: S06-50
timestamp: 00:15:04.05
speaker: JAC
utterance:
so at some point you're going to have some huge amount, where I'm not going to be able to see eight, right?


session: S06-50
timestamp: 00:18:14.29
speaker: JAC
utterance:
by convention we don't show it, because if I showed it on everything it's that whole extra set, that it might show.


session: S06-50
timestamp: 00:18:48.05
speaker: JAC
utterance:
if we ever get to, if we are ever looking for something and we find null, then it means its not there.


session: S06-50
timestamp: 00:20:00.17
speaker: JAC
utterance:
and since this is null, this tells us that there is nothing else past this, so I can set this equal to six.


session: S06-50
timestamp: 00:20:50.05
speaker: JAC
utterance:
so that's the other, null tells me there is nothing else in the tree, so I can either, either whatever I'm searching for is not in the tree, or I'm trying to insert something and this is the very last spot.


session: S06-50
timestamp: 00:21:51.17
speaker: JAC
utterance:
if I want to insert four, I could have done the same things I search, and I would have inserted four right here, right?


session: S06-50
timestamp: 00:24:25.07
speaker: JAC
utterance:
if I make nine take the place of five, then now eight and seven would have to be on this side of the tree.


session: S06-50
timestamp: 00:24:35.03
speaker: JAC
utterance:
so eight and seven are on the wrong side, and I'd have to put them here, and I'd have to do a lot of moving.


session: S06-50
timestamp: 00:26:49.00
speaker: JAC
utterance:
seven point five is less than nine, so we would go to it's left child, seven point five is less than eight.


session: S06-50
timestamp: 00:27:12.29
speaker: JAC
utterance:
we should never be pointing back up, we should only be pointing, everything should be pointing to someone at a level below them.


session: S06-50
timestamp: 00:28:13.03
speaker: JAC
utterance:
but if this wasn't the case, and this was the case, seven would still go up, but seven point five would get inherited by eight.


session: S06-50
timestamp: 00:28:29.07
speaker: JAC
utterance:
if there is no left most, if there is no immediate right child with the node we're deleting, then we immediately promote the left one.


session: S06-50
timestamp: 00:29:08.14
speaker: JAC
utterance:
we look for, we always look to the right, the right child, and then we start looking for the left most child.


session: S06-50
timestamp: 00:29:51.14
speaker: JAC
utterance:
now if I went, if they were going to delete nine, it had a right child, whatever the left most child over here was.


session: S06-50
timestamp: 00:30:00.15
speaker: JAC
utterance:
if there wasn't a left child, if there were no children, then this one would come take the place of nine.


session: S06-50
timestamp: 00:30:30.00
speaker: JAC
utterance:
alright, so, now we're asked to rearrange the nodes to get a binary search tree, to perform a different binary search tree.


session: S06-50
timestamp: 00:33:46.08
speaker: JAC
utterance:
if I inserted seven before the eight, seven would be here, and then eight would be it's right child.


session: S06-50
timestamp: 00:35:04.03
speaker: JAC
utterance:
O_K_, I purposely chose seven because I knew that there are values in here that are greater than seven.


session: S06-50
timestamp: 00:35:32.28
speaker: JAC
utterance:
i chose seven so that I could show you with some things on the right, and some things on the left, O_K_?


session: S06-50
timestamp: 00:37:09.25
speaker: JAC
utterance:
and then I could have said, insert nine, insert five, insert seven, insert three, insert one, insert two, right?


session: S06-50
timestamp: 00:38:50.26
speaker: JAC
utterance:
in order for c@l to find out <in order> [//] if we were at c@l, and wanted to know that information, we would have to ask k@l, and ask b@l.


session: S06-50
timestamp: 00:39:12.23
speaker: JAC
utterance:
since you can see the <person> [//] the face of the person behind you, you can identify who they are.


session: S06-50
timestamp: 00:39:21.12
speaker: JAC
utterance:
this person can't identify the person in front of you, because you can only see the back of their head.


session: S06-50
timestamp: 00:40:53.08
speaker: JAC
utterance:
c@l, we find out c@l is first, ask him who is next, tells us k@l is next, we ask k@l, k@l tells us b@l is next.


session: S06-52
timestamp: 00:00:23.01
speaker: JAC
utterance:
so the first one, obviously you just lay it down and if we put another one down, we just put another lego on top the bottom one.


session: S06-52
timestamp: 00:01:02.13
speaker: JAC
utterance:
if we want, now that we kind of have the concept down of what it does, let me explain in a little more detail.


session: S06-52
timestamp: 00:02:16.05
speaker: JAC
utterance:
now, if i want to get information out of here, i have a method which is called, or a function which is called top.


session: S06-52
timestamp: 00:04:15.00
speaker: JAC
utterance:
since i can't, it doesn't pull from anywhere else in the stack, it pull sin the same spot, i don't have to delete any parameters.


session: S06-52
timestamp: 00:04:23.15
speaker: JAC
utterance:
cause like an array, if i wanted to get the value of whatever is in the position of five, an array of five, right?


session: S06-52
timestamp: 00:07:00.23
speaker: JAC
utterance:
and then we're going to look a some of these, trying to figure out if they are binary search trees or not.


session: S06-52
timestamp: 00:09:30.20
speaker: JAC
utterance:
so we're going to try and figure out, based on these two rules whether this is a binary search tree or not.


session: S06-52
timestamp: 00:10:39.01
speaker: JAC
utterance:
well, when we, when we this tree was made, if it was made correctly, this value should always be greater than this.


session: S06-52
timestamp: 00:11:15.02
speaker: JAC
utterance:
so we come to twelve, and we look at twelve and it has no right child, but it has no left child, right?


session: S06-52
timestamp: 00:12:22.23
speaker: JAC
utterance:
we check five's children it has none, we check four's left children it has none, we come back to seven.


session: S06-52
timestamp: 00:14:30.15
speaker: JAC
utterance:
O_K_, now that we understand what a binary search tree is, we're going to use this binary search tree here, to answer some questions, O_K_?


session: S06-52
timestamp: 00:15:28.26
speaker: JAC
utterance:
so this is, theres two here, there is four here, there is eight here, sixteen, thirty two, and on and on until i got to a thousand.


session: S06-52
timestamp: 00:17:57.22
speaker: JAC
utterance:
just to explain, you say you check five to see if it's equal to eight, it's not, eight is greater than five, and you checked here, or you can show arrows or something, you know.


session: S06-52
timestamp: 00:18:12.29
speaker: JAC
utterance:
i would say I check, I compare eight and five, eight is greater than five, i go to five's right child, i compare eight and nine, eight is less than nine, so i go to nine's left child, i compare eight and eight, they are equal, i found eight.


session: S06-52
timestamp: 00:18:59.08
speaker: JAC
utterance:
but like i said before we could have a huge tree, and the computer can't look at the same thing all the time.


session: S06-52
timestamp: 00:20:03.04
speaker: JAC
utterance:
if we're looking, or if the computer is looking, and it find null, and it's searching for something, it knows that what it's looking for is not there.


session: S06-52
timestamp: 00:20:26.12
speaker: JAC
utterance:
since we found our dead end, or four had to be where this dead end is, somewhere past it, than four can't be in this tree.


session: S06-52
timestamp: 00:20:46.15
speaker: JAC
utterance:
we could return, if we were writing a function we might return false, so we would know that was in the tree, we would know what was not in the tree.


session: S06-52
timestamp: 00:21:02.06
speaker: JAC
utterance:
imagine I'm looking for something on level one thousand, i don't want to do a search that goes through ll one thousand levels.


session: S06-52
timestamp: 00:21:19.18
speaker: JAC
utterance:
a little beyond what we need to talk about, but sometimes it's a little interesting to know something beyond.


session: S06-52
timestamp: 00:21:29.00
speaker: JAC
utterance:
so now i will redraw it again, i keep wishing everytime i do this that i had pregenerated trees for me.


session: S06-52
timestamp: 00:23:59.21
speaker: JAC
utterance:
so we're asked to delete the node, or we prefer these as nodes, or parents, or children, there's so many different names for them, right?


session: S06-52
timestamp: 00:24:18.08
speaker: JAC
utterance:
we're going to delete this node, but the same node, if we're talking about these, if they say a child, then +...


session: S06-52
timestamp: 00:24:51.24
speaker: JAC
utterance:
we start at five, compare nine and five, nine is greater than five, so we compare nine and nine, we find nine.


session: S06-52
timestamp: 00:25:57.23
speaker: JAC
utterance:
so i deleted the connection to nine, but since it had no children, i didn't have to worry about anything on this side.


session: S06-52
timestamp: 00:27:12.09
speaker: JAC
utterance:
what the left most child means, is that we're going to keep checking everyone's left child until we can't find anymore left children.


session: S06-52
timestamp: 00:27:36.05
speaker: JAC
utterance:
what that, what the left most child is, it is the value that is closest to the one that we're deleting.


session: S06-52
timestamp: 00:28:18.12
speaker: JAC
utterance:
so if i try and find, for example, seven and a half, i compare seven and a half to seven, it's greater than seven, i compare seven and a half to nine, and less than nine, i compare seven and a half to eight, it's less than eight.


session: S06-52
timestamp: 00:28:37.04
speaker: JAC
utterance:
now i start at the beggining again, and i would keep searching over and over and over, and i would never find a null pointer that tells me that seen and a half isn't in there.


session: S06-52
timestamp: 00:29:53.21
speaker: JAC
utterance:
if seven is seven was, if seven had a, if seven had a right child, eight would just inherit seven point five as its left child.


session: S06-52
timestamp: 00:30:10.15
speaker: JAC
utterance:
it inherits that left child, and then if it has a  children, it doens't matter, because it just matters that this gets inherited.


session: S06-52
timestamp: 00:30:35.13
speaker: JAC
utterance:
so I'm going to try, and going to say seven, eight, and then five, and then nine, and then three, and then one and then two.


session: S06-52
timestamp: 00:31:08.29
speaker: JAC
utterance:
so I'm going to call, I'm going to call pop or, I'm going to call top, and then pop, and then repeat.


session: S06-52
timestamp: 00:32:20.11
speaker: JAC
utterance:
i just rearranged the order in which they were, i just rearranged the order somewhere and they become a binary search tree.


session: S06-52
timestamp: 00:32:29.26
speaker: JAC
utterance:
notice though, whatever is on this level, this zero level, had to come before everything else, right?


session: S06-52
timestamp: 00:34:05.04
speaker: JAC
utterance:
so in making our tree, we have to take that into effect, we could just make another one, I could say eight, nine, seven, five, three, two, one, and that would be a completely different tree.


session: S06-52
timestamp: 00:34:37.26
speaker: JAC
utterance:
the problem with this tree is though, you have one, and everything is greater than one, the whole tree is on this one side, right?


session: S06-52
timestamp: 00:35:18.28
speaker: JAC
utterance:
I usually like to use movie lines, because people like to wait in movie lines, and people wait in movie lines a lot.


session: S06-52
timestamp: 00:36:38.21
speaker: JAC
utterance:
and we could assume, when Carls turns around to look at her, she is scratching her nose or something.


session: S06-52
timestamp: 00:37:12.09
speaker: JAC
utterance:
so Carl knows that Kim's behind him, Kim knows that Bob is behind her, Bob knows that Fred is behind him and Fred can turn around and tell us that there is our null, there's nobody there,  there is the end of the line.


session: S06-52
timestamp: 00:38:38.21
speaker: JAC
utterance:
he tells Greg Fred is after him so he comes in, so we tell Fred that, or Greg that, and Greg will now point to Fred.


session: S06-52
timestamp: 00:39:02.02
speaker: JAC
utterance:
if we had Bob no longer point to Fred, and then had Greg try and point to Fred, we can't do that because we have to ask Bob what he's behind so we lost Fred.


session: S06-53
timestamp: 00:01:00.16
speaker: LOW
utterance:
so four has only one child, a right child, but somewhere here we could find an example of here of one that could have only a left child.


session: S06-53
timestamp: 00:01:13.25
speaker: LOW
utterance:
um, alright, so thats a binary tree, with at most two children, what makes it a binary search tree, is the following fact.


session: S06-53
timestamp: 00:01:21.15
speaker: LOW
utterance:
every node, not just at the root, but at every node, things to the left are smaller, and things to the right are larger.


session: S06-53
timestamp: 00:01:48.17
speaker: LOW
utterance:
so there is a little pointer to the left, a little pointer to the right, and there is a big storage area here.


session: S06-53
timestamp: 00:03:33.20
speaker: LOW
utterance:
so this is a tree t@l, and a binary search tree t@l, and we can keep track of it by pointing to the first node.


session: S06-53
timestamp: 00:04:19.02
speaker: LOW
utterance:
alright, so I've told you this we can verify, this is a binary search tree, so this binary search tree is, and this is one.


session: S06-53
timestamp: 00:06:37.13
speaker: LOW
utterance:
O_K_, so we just did the search, but now we're going, there's a problem here where we insert something in the tree, so this is going to show us sort of how to build the tree.


session: S06-53
timestamp: 00:08:16.02
speaker: LOW
utterance:
so this is kind of a structure like a link list, except the link list, we will look at those in a minute.


session: S06-53
timestamp: 00:08:44.06
speaker: LOW
utterance:
so thats how you construct a tree, the first node becomes a root, and then the second node either goes left or right.


session: S06-53
timestamp: 00:11:24.11
speaker: LOW
utterance:
if one wasn't here, you know we would do the same thing on this side, if we were just deleting a two, we would just make five point to his grandchild.


session: S06-53
timestamp: 00:13:08.17
speaker: LOW
utterance:
to move two up we would have to do the same thing, because two has two kids, and maybe, yeah, right.


session: S06-53
timestamp: 00:13:11.19
speaker: LOW
utterance:
but if you're ignoring that problem, two still can't come up because three is bigger than two and three can't be on the left side.


session: S06-53
timestamp: 00:13:45.20
speaker: LOW
utterance:
it could be three, because if we bring three up, these guys are smaller than three, so they're on the left side, is O_K_.


session: S06-53
timestamp: 00:14:43.01
speaker: LOW
utterance:
which node would we pick from this side to bring up, which node would we pick from this side to bring up?


session: S06-53
timestamp: 00:15:10.12
speaker: LOW
utterance:
it has to be, since I am on the left side, and this is a binary search tree, all of these are smaller than that one.


session: S06-53
timestamp: 00:15:32.07
speaker: LOW
utterance:
because remember the binary search tree property says, if you're bigger than five, you have to be on the right side.


session: S06-53
timestamp: 00:16:25.15
speaker: LOW
utterance:
so we put the biggest one here, and it's less than these guys, because all of these guys are bigger than that one.


session: S06-53
timestamp: 00:16:41.05
speaker: LOW
utterance:
maybe we can see, in this case, if you want the smallest one over here, clearly you have to go right to get into this subtree, alright?


session: S06-53
timestamp: 00:17:15.13
speaker: LOW
utterance:
so you go right once, and then you go left as many times as you can, that would be the smallest one.


session: S06-53
timestamp: 00:17:55.15
speaker: LOW
utterance:
i have to go to fractions, but for example if I put two and a half in the tree, it would be right here, right?


session: S06-53
timestamp: 00:18:26.16
speaker: LOW
utterance:
and then of course, i could put six and a quarter, six and three quarters, i could put whole trees in here.


session: S06-53
timestamp: 00:19:45.11
speaker: LOW
utterance:
alright, so these nodes we find, in either case, if you find the smallest one here, it can't have a left child.


session: S06-53
timestamp: 00:20:53.22
speaker: LOW
utterance:
and if they, they want you to delete a node with two kids, then you find either the biggest one on the left hand side, or the smallest one on the left hand side.


session: S06-53
timestamp: 00:21:19.10
speaker: LOW
utterance:
*uh, the last problem they have here is just to show us the last different binary search trees we have on these nodes.


session: S06-53
timestamp: 00:23:19.24
speaker: LOW
utterance:
but just picking an order of these nodes, just picking them, you can then make it a binary search tree.


session: S06-53
timestamp: 00:23:35.09
speaker: LOW
utterance:
yeah, not every order will give you a different tree for example, if you put the five over here, you'll have the same tree, right?


session: S06-53
timestamp: 00:25:23.15
speaker: LOW
utterance:
it gives you +// it takes it off, it would take it off, and this is a function that returns that value.


session: S06-53
timestamp: 00:28:34.00
speaker: LOW
utterance:
it is empty, so when we're done, this is a function, so with the bottom here, there is something missing, so we'll return count.


session: S06-53
timestamp: 00:29:00.08
speaker: LOW
utterance:
so by counting the stack you have destroyed it, which is probably the people who call your function aren't going to be happy to know that four was what used to be in there.


session: S06-53
timestamp: 00:29:16.29
speaker: LOW
utterance:
this is basically the right idea, you got to pop them off, you can't use top, because top will just say q@l, q@l, q@l, q@l, q@l.


session: S06-53
timestamp: 00:29:51.12
speaker: LOW
utterance:
you're right, we could put them in a link list, but I think it would be easier to put them in another stack.


session: S06-53
timestamp: 00:30:56.29
speaker: LOW
utterance:
s@l is empty , so we get out, and you return the count, we still say four is correct, and lets see, we're going to restore s@l.


session: S06-53
timestamp: 00:32:07.29
speaker: LOW
utterance:
so the a@l would get pushed back, and then the b@l would get pushed back, and then this g@l would get pushed back, and then q@l would get pushed back.


session: S06-53
timestamp: 00:32:54.14
speaker: LOW
utterance:
we weren't worried with the size of the elements, we were just counting how many elements there were.


session: S06-53
timestamp: 00:33:19.01
speaker: LOW
utterance:
alright, because the stack may be stored like a link list, so you don't have, you don't know how much the total storage is for the stack.


session: S06-53
timestamp: 00:33:48.22
speaker: LOW
utterance:
alright, so lets talk about link lists for a minute, I'm not sure when they are going to come and interrupt us, but +...


session: S06-53
timestamp: 00:34:28.04
speaker: LOW
utterance:
so if you want to push x@l on the stack, then we can get a new node, put x@l in it, and just a change couple links.


session: S06-53
timestamp: 00:34:50.09
speaker: LOW
utterance:
so there is no way to sort of say its got this much storage space, and therefore if I divide by the size I know it's got four nodes because I know how much storage space it has.


session: S06-53
timestamp: 00:35:15.25
speaker: LOW
utterance:
and they say describe a sequence of operations to consider a new node, which contains g@l, after the node that contains b@l.


session: S06-53
timestamp: 00:35:23.14
speaker: LOW
utterance:
well, it turns out that i have a b@l in mine in the third place, and they have a b@l in theirs in the third place, so lets do it this, les go with this way.


session: S06-53
timestamp: 00:35:32.04
speaker: LOW
utterance:
so here is this link list, q@l g@l b@l a@l, and it's not a stack anymore it's just a plain link list, you can insert and delete anywhere.


session: S06-53
timestamp: 00:37:54.23
speaker: LOW
utterance:
I don't know if you have seen that word before, we're going to traverse, travel across the list and find b@l.


session: S06-53
timestamp: 00:38:15.21
speaker: LOW
utterance:
the link trees have three pieces, these guys have two pieces, lets call this the info and less call this the next.


session: S06-54
timestamp: 00:00:45.12
speaker: LOW
utterance:
it's got an I@l D@L number, it's got a name, it's got an address, it's got a zip code, and some other things, names, all that kind of stuff now.


session: S06-54
timestamp: 00:01:06.29
speaker: LOW
utterance:
and then k@l is the next information, it has the address to the third node, and then f@l is the fourth node, and then there is a special pointer that doesn't point anywhere.


session: S06-54
timestamp: 00:01:45.07
speaker: LOW
utterance:
and the point is, I've drawn these, like this, but in reality, there is the computer memory, the first node may be in the middle of memory, and the second node is actually in the early part of memory, and the third node is way at the other end of memory.


session: S06-54
timestamp: 00:02:41.24
speaker: LOW
utterance:
so if you had these four elements in an array, its difficult to put one in the middle, you got to move a couple guys out of the way.


session: S06-54
timestamp: 00:02:53.13
speaker: LOW
utterance:
in this first exercise, describe a sequence of operations to insert a new node with g@l in it, after the node that contains b@l.


session: S06-54
timestamp: 00:03:34.22
speaker: LOW
utterance:
alright, so it's easy to draw the after picture, but we're supposed to describe a sequence of operations.


session: S06-54
timestamp: 00:04:52.17
speaker: LOW
utterance:
alright, so there is the picture, and as you see, thats about the only way you could start it, because thats all you know, is where the first one lives.


session: S06-54
timestamp: 00:07:15.12
speaker: LOW
utterance:
so lets call this one and call this two, just to give them, and I'll put circles around so that you can see it better.


session: S06-54
timestamp: 00:08:36.14
speaker: LOW
utterance:
so the point I'm trying to make is that the order of these is critical, and we have to do the second one first.


session: S06-54
timestamp: 00:09:17.22
speaker: LOW
utterance:
so the point it, that I'm making here, is the order of these things is sometimes very very critical.


session: S06-54
timestamp: 00:09:22.08
speaker: LOW
utterance:
so if we do that first, then we can say, alright, next of t@l one, we'll change you can make you point to next of t@l two, O_K_?


session: S06-54
timestamp: 00:09:49.04
speaker: LOW
utterance:
describe a sequence of operations, to delete the node which contains a@l in list two so real quickly I'll draw the second list.


session: S06-54
timestamp: 00:11:12.21
speaker: LOW
utterance:
I've got this pointer to a@l, so basically I guess what we're doing is we find the a@l, it's step one.


session: S06-54
timestamp: 00:12:08.02
speaker: LOW
utterance:
e@l knows where a@l lives, a@l knows where m@l lives, but a@l has no idea where its previous one lived.


session: S06-54
timestamp: 00:13:38.07
speaker: LOW
utterance:
because now what we're interested in is t@l two, we want to change this value right here, which is # next of t@l two.


session: S06-54
timestamp: 00:14:07.11
speaker: LOW
utterance:
great, so that's +// we found really the node before a@l, and then in this case we have one link to modify.


session: S06-54
timestamp: 00:14:26.09
speaker: LOW
utterance:
*uh, hopefully, +// well, it's only a list with three elements, but hopefully you see what we have done if a@l is going to work anywhere in the middle.


session: S06-54
timestamp: 00:14:33.14
speaker: LOW
utterance:
if there is forty-seven elements, and a@l is anywhere from the second to the forty-sixth, then it will work.


session: S06-54
timestamp: 00:15:42.05
speaker: LOW
utterance:
*uh oh, because there is no +// you can't do this next of t@l two, there is no, +// t@l two is null.


session: S06-54
timestamp: 00:16:56.15
speaker: LOW
utterance:
so that +// that was a little bit subtle, but I guess when emphasizing these things, always draw pictures, because they help.


session: S06-54
timestamp: 00:17:50.00
speaker: LOW
utterance:
so what you're supposed to do in a fancy cafeteria is take the top tray, you can't get the green one you like when there's these ugly one blue ones on top.


session: S06-54
timestamp: 00:17:58.27
speaker: LOW
utterance:
alright, so you take the top one off, and when the guy comes out of the kitchen and puts the clean trays on, one at a time, and the spring just compresses a little bit, and you still see one.


session: S06-54
timestamp: 00:18:10.01
speaker: LOW
utterance:
so you want to this thing, you can't tell if there is one tray in there, or a thousand trays in there.


session: S06-54
timestamp: 00:19:32.20
speaker: LOW
utterance:
and if I push something now I would have five elements, if I pushed a p@l, I'd have five elements with p@l at the top.


session: S06-54
timestamp: 00:19:39.01
speaker: LOW
utterance:
i think in the notes they sometimes use a top sack method, which is really not fundamental, but they use it.


session: S06-54
timestamp: 00:20:51.06
speaker: LOW
utterance:
and top will never get you there, because you say top, top, top, top, top you're in an infinite loop, it's r@l, r@l, r@l, r@l, r@l to pop.


session: S06-54
timestamp: 00:22:09.20
speaker: LOW
utterance:
probably people who destroyed this function aren't going to be too happy to know that there used to be four elements in this valuable stack, but now that I ask you how many there were, I got the answer four, but in fact they are actually now zero.


session: S06-54
timestamp: 00:23:53.13
speaker: LOW
utterance:
so there is a simple example of using your deletion operation, and your insertion operation to do something with the stack.


session: S06-54
timestamp: 00:24:30.24
speaker: LOW
utterance:
so there really weren't any exercises here on stacks for some reason, but we have plenty on binary search trees.


session: S06-54
timestamp: 00:24:50.21
speaker: LOW
utterance:
it can't have three or ten, and in fact we call this the left child and we call that the right child.


session: S06-54
timestamp: 00:25:05.26
speaker: LOW
utterance:
to be a binary search tree, you have the additional property, that at every node, everything on the left is smaller, and everything on the right is larger.


session: S06-54
timestamp: 00:25:32.06
speaker: LOW
utterance:
alright, so they're asking which if these is a binary search tree, and I sort of argued this one is.


session: S06-54
timestamp: 00:26:04.16
speaker: LOW
utterance:
seven is smaller than all these are smaller than eleven, and you know this is bigger than eleven, and everywhere is smaller than seven, bigger than seven, alright.


session: S06-54
timestamp: 00:26:22.18
speaker: LOW
utterance:
these are in fact bigger than eight, and these are in fact smaller than eight, and these are bigger than five, and thats whatever, this one is just totally flipped.


session: S06-54
timestamp: 00:26:31.26
speaker: LOW
utterance:
*uh they give us this binary search tree, we quickly verify, yeah, this is a binary search tree, thee are less than five,  are bigger than five, these are bigger than two and less than two, and this one is O_K_.


session: S06-54
timestamp: 00:26:57.03
speaker: LOW
utterance:
so here is five, which has a left child, and two, and a right child nine, and two has a left child one, and a right child three, and nine has a left child eight.


session: S06-54
timestamp: 00:27:20.04
speaker: LOW
utterance:
well, they don't show it, and I didn't say it, but just like a link list, you keep track of the tree, by a pointer to the root.


session: S06-54
timestamp: 00:27:39.06
speaker: LOW
utterance:
there is no reason looking over here, and these guys are smaller than five, therefore, they can't be it.


session: S06-54
timestamp: 00:30:02.01
speaker: LOW
utterance:
if you want to delete three, you just change the pointer +// you got to find a parent so the same sort of thing is deleting in a link list, you really got to have a parent that but we're not writing the code here so we just say easy.


session: S06-54
timestamp: 00:31:12.26
speaker: LOW
utterance:
and if two only had one kid, which was a right kid, you would just make five point to its grandchild here.


session: S06-54
timestamp: 00:31:45.04
speaker: LOW
utterance:
and it's not really harder because it's the root, this tree is really small and really five and two are the only nodes with two kids.


session: S06-54
timestamp: 00:32:11.23
speaker: LOW
utterance:
it's not what that means because in this case two has two kids of its own, so it's going to recursively, you know, cause this problem.


session: S06-54
timestamp: 00:32:21.07
speaker: LOW
utterance:
well, I'm not quite sure what it means, but one in three would stay over here somehow, but two can't be the parent of three.


session: S06-54
timestamp: 00:32:38.04
speaker: LOW
utterance:
there is one node over here, one node on this side, that will easily go up for five, and is exactly one node on this side that can easily go for five.


session: S06-54
timestamp: 00:33:40.19
speaker: LOW
utterance:
if you want the biggest one over here, well, of course you go left to get in this tree, and then you go # right as many times.


session: S06-54
timestamp: 00:33:56.05
speaker: LOW
utterance:
I got to go to fractures because of these stupid numbers but if six and a half is in this tree, I claim to be right here.


session: S06-54
timestamp: 00:34:06.12
speaker: LOW
utterance:
and if six and a quarter was in the tree, and if six and three quarters, I mean, they could be giant trees underneath six on the right but there is no left tree here.


session: S06-54
timestamp: 00:34:28.23
speaker: LOW
utterance:
and of course two and a quarter, two and a quarter, we could have a giant tree if we went to fractions and decimals.


session: S06-54
timestamp: 00:34:48.01
speaker: LOW
utterance:
three is less than five, because it is on this side already, so three is going to be less than these guys.


session: S06-54
timestamp: 00:35:49.00
speaker: LOW
utterance:
this last problem we had here, I think they are simply pointing out that there are many, many, many binary search trees on these nodes, you don't have to have that one.


session: S06-54
timestamp: 00:36:00.03
speaker: LOW
utterance:
so the say rearrange the nodes in a given binary search tree to form a different binary search tree.


session: S06-54
timestamp: 00:37:42.25
speaker: LOW
utterance:
so, not every permutation can give you a different tree, for example if you change the order of, lets see, if you change the order of three and nine, you will have the same tree.


session: S06-55
timestamp: 00:00:18.06
speaker: LOW
utterance:
and you really can't see how many things there are on the list, because the only way you can get to the second node is to follow this link to the second node, and follow this link to the third node, and follow this link to the fourth node.


session: S06-55
timestamp: 00:01:01.25
speaker: LOW
utterance:
alright, so here they want us to describe a sequence of operations to insert a new node which contains g@l in that first list after the node that contains b@l.


session: S06-55
timestamp: 00:01:14.05
speaker: LOW
utterance:
so with these things you always draw pictures, there's the before picture, and the after picture is really easy.


session: S06-55
timestamp: 00:03:55.23
speaker: LOW
utterance:
without b@l, I'll get a new node, and we did that, and did that, and now we have to link in the list.


session: S06-55
timestamp: 00:07:04.05
speaker: LOW
utterance:
so it's such a simple list you should imagine there forty seven elements here, and say, somewhere in the middle, and we had to go this much time until we finally found the a@l.


session: S06-55
timestamp: 00:07:14.28
speaker: LOW
utterance:
over here, this previous problem, once we had found the node that contains b@l, we made the changes to that node.


session: S06-55
timestamp: 00:09:51.20
speaker: LOW
utterance:
copy the value out of there, over here, and copy this out and put it over there would make this guy point to that one.


session: S06-55
timestamp: 00:10:02.27
speaker: LOW
utterance:
and then in some languages you have to physically remove a@l, but in Java, you're correct, this thing had to come suitable for garbage collection.


session: S06-55
timestamp: 00:10:14.09
speaker: LOW
utterance:
alright, another thing important is to always draw pictures, but another thing to do is always watch for special cases.


session: S06-55
timestamp: 00:10:41.18
speaker: LOW
utterance:
so we would have to worry about what would happen if a@l is last, and what would happen if a@l is first.


session: S06-55
timestamp: 00:11:33.11
speaker: LOW
utterance:
*uh oh, because what we did , was we made the one before point to the one after, but there is no one before.


session: S06-55
timestamp: 00:12:22.14
speaker: LOW
utterance:
*uh, if *uh, if it's the first element, then we're going to set h@l two equal to this value right here.


session: S06-55
timestamp: 00:13:13.27
speaker: LOW
utterance:
so that's a good example, *uh of link lists, but the important thing is, draw pictures, and then think about special cases.


session: S06-55
timestamp: 00:13:28.09
speaker: LOW
utterance:
there aren't any problems there about stacks, they ask you a question or two about stacks, lets talk about them.


session: S06-55
timestamp: 00:14:02.08
speaker: LOW
utterance:
and you say what stack you want to pop, and of course, a couple things to point about this, it's destructive, namely it changes the stack, it was a stack of four elements, now it's a stack of three elements.


session: S06-55
timestamp: 00:15:39.20
speaker: LOW
utterance:
and, *uh, so lets trace this example here, of course we want to return the answer four, *uh, top doesn't do us any good.


session: S06-55
timestamp: 00:17:05.21
speaker: LOW
utterance:
so the people who call this function are probably not going to be happy to learn that there used to be four in a stack, so we got to restore s@l.


session: S06-55
timestamp: 00:17:21.15
speaker: LOW
utterance:
cause these are the only things we could use, and we got to pop it until it's empty, and then count it.


session: S06-55
timestamp: 00:19:17.04
speaker: LOW
utterance:
and then, like I said, top is not really fundamental, because we can write the top by doing a pop followed by the push.


session: S06-55
timestamp: 00:20:15.27
speaker: LOW
utterance:
to make it a binary search tree, you have to have this extra property, that in every node, the things to the left are smaller, and the things to the right are bigger.


session: S06-55
timestamp: 00:20:59.15
speaker: LOW
utterance:
this left is supposed to be less, and here right is less, and left is more, and everywhere it is messed up.


session: S06-55
timestamp: 00:21:17.05
speaker: LOW
utterance:
O_K_, *uh, so here they give us a binary search tree, yeah, these are smaller than five, these are bigger than five.


session: S06-55
timestamp: 00:21:28.00
speaker: LOW
utterance:
you got a root five, oh by the way, just like a the link list, the one node you can keep track of is the root.


session: S06-55
timestamp: 00:21:40.11
speaker: LOW
utterance:
and then these guys have three parts to the node, there is the left pointer, the right pointer, and the info.


session: S06-55
timestamp: 00:22:31.16
speaker: LOW
utterance:
alright, we're going to search, not too surprisingly, in binary search trees, search is very easy, and very efficient.


session: S06-55
timestamp: 00:22:40.12
speaker: LOW
utterance:
and we're going to show how to insert things, so the tree can grow, and we're going to show you how to delete things.


session: S06-55
timestamp: 00:22:46.27
speaker: LOW
utterance:
so you can put a lot of data in here, and if you were searching for things this would be a very efficient search.


session: S06-55
timestamp: 00:23:27.14
speaker: LOW
utterance:
O_K_, very full explaination, yeah, we look at the info, compare it to our eight, and we go to the right.


session: S06-55
timestamp: 00:23:36.19
speaker: LOW
utterance:
if I've got a thousand nodes in this tree, and it is balanced pretty well, you just threw away five hundred nodes.


session: S06-55
timestamp: 00:24:18.08
speaker: LOW
utterance:
no but I mean the search succeeded and found the eight, but the search very efficantly failed because there is no four in the tree.


session: S06-55
timestamp: 00:24:24.24
speaker: LOW
utterance:
and but it didn't look through the whole tree, it threw away the right half, we can look for something smaller than five.


session: S06-55
timestamp: 00:25:35.06
speaker: LOW
utterance:
so insertion is real simple, insertion, search, you look like you have got down, and insertion is real simple then, because when you search, and you fail, you put it there.


session: S06-55
timestamp: 00:26:59.20
speaker: LOW
utterance:
delete the node it takes nine to give it a binary search tree, move things around as  little as possible


session: S06-55
timestamp: 00:27:19.13
speaker: LOW
utterance:
so you would *uh, you would go to the right, and *uh, I would also have *uh, another pointer pointing to the one before.


session: S06-55
timestamp: 00:27:55.24
speaker: LOW
utterance:
so I'm going to summarize that, it's pretty easy, namely the grandparent is just going to be linked to the grandchild.


session: S06-55
timestamp: 00:28:14.12
speaker: LOW
utterance:
if one wasn't in the tree, you were deleting two, and two would have one kid, and a grandparent, we'll just point to the grandchild and that's that.


session: S06-55
timestamp: 00:28:27.18
speaker: LOW
utterance:
and yeah, you moved very little around, you just basically changed one pointer, and you made this guy available for garbage collection.


session: S06-55
timestamp: 00:28:48.05
speaker: LOW
utterance:
and there aren't any more cases because it's a binary search tree, so two one and zero are the only possibilities.


session: S06-55
timestamp: 00:29:56.28
speaker: LOW
utterance:
and nine can't come up here, cause these guys can't be the right tree of nine, because these guys are smaller than nine.


session: S06-55
timestamp: 00:30:05.17
speaker: LOW
utterance:
but it turns out that there is exactly one node on this side, and there is exactly one node on this side.


session: S06-55
timestamp: 00:30:12.20
speaker: LOW
utterance:
there is exactly one node over here, and exactly one node over here that can easily move up and take five's place.


session: S06-55
timestamp: 00:32:42.10
speaker: LOW
utterance:
O_K_, because yeah, we bring the biggest up, suppose we have a general tree here, we'll bring the biggest up.


session: S06-55
timestamp: 00:33:07.22
speaker: LOW
utterance:
and it's going to be bigger than all these on the left hand side because it's bigger than that to begin with.


session: S06-55
timestamp: 00:34:13.14
speaker: LOW
utterance:
and then two and a quarter would go here, and two and three quarters would go here, and they would have giant trees off of the left hand side of this stack.


session: S06-55
timestamp: 00:35:40.19
speaker: LOW
utterance:
they want us to, I think they simply are showing us that there are many different binary search trees that can be built on these nodes.


session: S06-55
timestamp: 00:37:16.18
speaker: LOW
utterance:
so you've got +// you don't really throw out, you know, you throw away an empty tree each time, and then you gain xxx.


session: S06-55
timestamp: 00:38:04.26
speaker: LOW
utterance:
so I think that's all they are showing you there, is that you can have many binary search trees on those nodes.


session: S06-55
timestamp: 00:38:26.25
speaker: LOW
utterance:
a hard problem is to count how many trees there are on those seven nodes, how many binary search trees there are on those seven nodes.


session: S06-55
timestamp: 00:38:49.01
speaker: LOW
utterance:
*uh, alright, um, I'm not quite sure what time we started but I'm going to check with Davide quickly.


session: S06-56
timestamp: 00:00:15.07
speaker: LOW
utterance:
*uh, it's a list that's means it has a first element, a second element, a third element, and a last element.


session: S06-56
timestamp: 00:00:46.22
speaker: LOW
utterance:
now the info should really be a record with the person's address and number and zip code and social security number and mother's maiden name and phone number and all that stuff.


session: S06-56
timestamp: 00:01:16.14
speaker: LOW
utterance:
and then the second one has a link to the third one, and then the third one has a link to the fourth one.


session: S06-56
timestamp: 00:01:34.17
speaker: LOW
utterance:
you have to go to the first element to find the second one, you have to go there to find a third, and you have to go there to find a fourth.


session: S06-56
timestamp: 00:01:40.08
speaker: LOW
utterance:
and my picture makes them look like they are kind of consecutive, it's just to keep the picture simple.


session: S06-56
timestamp: 00:02:12.26
speaker: LOW
utterance:
so with the array, you have the physical order, first second, third, fourth, five, but there are logical +...


session: S06-56
timestamp: 00:02:17.17
speaker: LOW
utterance:
oops, you got the logical order there, first, second, third, fourth but they're also physical order.


session: S06-56
timestamp: 00:02:28.29
speaker: LOW
utterance:
in fact they want us to describe a sequence of operations to insert a new node which contains g@l in this list.


session: S06-56
timestamp: 00:02:44.10
speaker: LOW
utterance:
there is the before picture, and presto you get a new node with g@l in it, and link it in, there is the after picture.


session: S06-56
timestamp: 00:02:55.11
speaker: LOW
utterance:
and in point, we didn't have to move things around, we're able to insert this because these guys weren't in the physical order, they were just in logical order.


session: S06-56
timestamp: 00:03:03.23
speaker: LOW
utterance:
*uh, alright, so yeah, always draw the pictures, but they want us to describe a sequence of opertations.


session: S06-56
timestamp: 00:04:01.00
speaker: LOW
utterance:
h@l one has the first one, the first one has the second one, and the second one you can leave that alone.


session: S06-56
timestamp: 00:05:11.07
speaker: LOW
utterance:
so I'm going to just assume that there is a constructor here, and say give me a new node with g@l in it.


session: S06-56
timestamp: 00:05:23.25
speaker: LOW
utterance:
by the way it doens't matter if you point to the front or the top or the bottom, it would just +// the address of this node.


session: S06-56
timestamp: 00:05:41.12
speaker: LOW
utterance:
we need to break this link, which is basically by changing what is stored here, we're just going to break what's stored over there and make it point there, alright.


session: S06-56
timestamp: 00:07:25.03
speaker: LOW
utterance:
alright, so not much code, and important thing is we didn't have to, you know, suppose there was a hundred elements and we had to put something in the middle, we didn't have to move fifty elements.


session: S06-56
timestamp: 00:07:43.12
speaker: LOW
utterance:
once again, if you delete an array, you either have to have some special way of marking it or you have to move a whole bunch of things up.


session: S06-56
timestamp: 00:09:34.09
speaker: LOW
utterance:
so the easiest way to solve that problem is, and this is a common sort of thing, is to use two temporaries.


session: S06-56
timestamp: 00:10:41.05
speaker: LOW
utterance:
but there is the example of here we had two pointers, because now when you find the a@l, you've got pointer to the one before it.


session: S06-56
timestamp: 00:10:54.12
speaker: LOW
utterance:
and you basically I think said that a minute ago, we want to make +// this is what we want to change.


session: S06-56
timestamp: 00:11:06.26
speaker: LOW
utterance:
and it doesn't really matter whether you set next of t@l one equals null, or leave it alone or whatever.


session: S06-56
timestamp: 00:11:14.26
speaker: LOW
utterance:
and then nothing +// this has been broken, nothing points at that and the garbage collector will get it.


session: S06-56
timestamp: 00:11:44.02
speaker: LOW
utterance:
if there is a hundred elements, and a@l anywhere between the second and the ninety ninth, this will work, because we made the one before point to the one after.


session: S06-56
timestamp: 00:11:55.17
speaker: LOW
utterance:
we, of course, we could have to worry, will it be a special case if a@l is last, will it be a special case if a@l is first?


session: S06-56
timestamp: 00:12:42.18
speaker: LOW
utterance:
if we got to figure out how to say it, if it's the first element, we got to do something special, else we do what we wrote.


session: S06-56
timestamp: 00:13:34.00
speaker: LOW
utterance:
alright, so draw the before picture to get it, draw the after picture, and then watch for special cases.


session: S06-56
timestamp: 00:13:48.12
speaker: LOW
utterance:
and I guess I will assume that if you haven't studied link lists you probably haven't also studied stacks.


session: S06-56
timestamp: 00:14:18.14
speaker: LOW
utterance:
in fact, it's a fancy cafeteria where you can't take the top plate, you can't dig around for the blue plate down below.


session: S06-56
timestamp: 00:14:26.15
speaker: LOW
utterance:
*um, and whats so fancy about this is the spring is so carefully loaded, you can only see one plate.


session: S06-56
timestamp: 00:14:32.00
speaker: LOW
utterance:
*uh, you can't tell if there's one plate or a thousand plates in here, you can only see the top one.


session: S06-56
timestamp: 00:15:20.13
speaker: LOW
utterance:
and by that I mean that if you pop the stack, f@l is gone from the stack, and it also, it gives you back that value, so it returns the top element.


session: S06-56
timestamp: 00:15:39.08
speaker: LOW
utterance:
the other one is push, and push the spring down, it's a function with two parameters, you say what stack you want to push on and what value you want to push.


session: S06-56
timestamp: 00:17:28.15
speaker: LOW
utterance:
so we popped off the f@l, and got one, and we popped off the d@l, and incremented, popped off the z@l and incremented.


session: S06-56
timestamp: 00:17:41.18
speaker: LOW
utterance:
now we got some problems, so I'm going to put the return count down here, and it works, it returns four.


session: S06-56
timestamp: 00:18:18.09
speaker: LOW
utterance:
but I think it is basically the simplest way to do this, because these are the only things we can use, and we said top doesn't get us anywhere, and so we go to pop it until it's empty, and alright.


session: S06-56
timestamp: 00:18:37.16
speaker: LOW
utterance:
we can store them in an array, which you know about or we can store them in a link list but the easiest thing is to store them into the stack.


session: S06-56
timestamp: 00:19:45.06
speaker: LOW
utterance:
alright, but that's the whole story about stacks, you basically have just these operations, every takes place at the top.


session: S06-56
timestamp: 00:20:14.14
speaker: LOW
utterance:
alright, so I have to explain what a binary tree is, and I'll make that a special binary search tree.


session: S06-56
timestamp: 00:20:51.26
speaker: LOW
utterance:
at every node, as I point to the root, but at every node, stuff to the left is smaller, stuff to the right is larger.


session: S06-56
timestamp: 00:21:14.26
speaker: LOW
utterance:
so the actual question is which of the following are binary search trees, and I argue this one is, because that property holds everywhere.


session: S06-56
timestamp: 00:21:29.04
speaker: LOW
utterance:
yeah, so this one is because that's bigger and these are all smaller, and that's bigger than seven, and that's less than seven, and yeah.


session: S06-56
timestamp: 00:21:49.09
speaker: LOW
utterance:
alright, now that we know what a binary search tree is, now we're going to find out that searching is very efficient, and xxx binary search tree.


session: S06-56
timestamp: 00:22:04.12
speaker: LOW
utterance:
first of all it is, because these guys are smaller than five, these guys are bigger than five, and these are smaller than two and bigger than two, and yeah.


session: S06-56
timestamp: 00:22:11.05
speaker: LOW
utterance:
by the way, they never said it, but, the way you keep track of a binary search is with a pointer to the root.


session: S06-56
timestamp: 00:22:20.15
speaker: LOW
utterance:
sort of like a link list, except it's a two-dimensional kind of thing instead of a one-dimensional thing.


session: S06-56
timestamp: 00:24:02.06
speaker: LOW
utterance:
imagine you got a thousand nodes here, the tree is pretty well balanced, you just threw away half of the nodes, five hundred.


session: S06-56
timestamp: 00:24:20.27
speaker: LOW
utterance:
well you +// there is only one node at this level, but you look at the five, and it was bigger, so you went this way.


session: S06-56
timestamp: 00:24:30.13
speaker: LOW
utterance:
and then there is sort of four nodes at this level, so this tree was full out here, and if you were looking for something else you would go right or left from eight.


session: S06-56
timestamp: 00:25:06.25
speaker: LOW
utterance:
here you efficiently found the eight, here you efficiently found that there isn't a four in this tree.


session: S06-56
timestamp: 00:25:55.00
speaker: LOW
utterance:
suppose we're putting eight in the tree suppose eight wasn't there, we'd go right there, right, because it's less than eleven, bigger than seven, less than ten.


session: S06-56
timestamp: 00:26:20.15
speaker: 256
utterance:
I mean, is the general rule like this where everything in this right half of the tree will be bigger than the root?


session: S06-56
timestamp: 00:26:33.25
speaker: LOW
utterance:
okay, so that's why the search works because if you're looking for something bigger than five you throw this half away (be)cause these guys are all smaller.


session: S06-56
timestamp: 00:29:52.04
speaker: LOW
utterance:
so I'm going to keep the nine in the tree so I'm just going to draw a dot dot dot xxx in a minute so yeah.


session: S06-56
timestamp: 00:30:50.00
speaker: LOW
utterance:
and they want us to delete the node that contains five from the tree, move as few nodes as possible and keep it a binary search tree.


session: S06-56
timestamp: 00:31:00.13
speaker: LOW
utterance:
it doesn't make it any harder but the tree is so small so lets stay with the five and keep it as far up as we can.


session: S06-56
timestamp: 00:31:24.10
speaker: LOW
utterance:
well, let me start with the two and it's even worse because two had two kids itself so that would be a two kid one becoming a two kid one which suggests that this method is also +...


session: S06-56
timestamp: 00:31:38.15
speaker: LOW
utterance:
but here I can't move two up because I'm keeping this on the right side of the tree +// I'm sorry, I'm keeping this on the left side of the tree.


session: S06-56
timestamp: 00:32:16.00
speaker: LOW
utterance:
so if we move six up then the right side is happy because as you pointed out these guys are bigger than six.


session: S06-56
timestamp: 00:32:40.09
speaker: LOW
utterance:
alright, so if you move up three then this side is happy (be)cause three is bigger than this side and of course the right side is happy because three is less than five therefore, three is less than all these guys.


session: S06-56
timestamp: 00:32:49.24
speaker: LOW
utterance:
so in general, you picked the three and the six, but in general what property does the three have and what property does the six have?


session: S06-56
timestamp: 00:33:00.00
speaker: 256
utterance:
well, if you move up the six I don't think it mattered but if you move the six there's three on each side of it.


session: S06-56
timestamp: 00:33:40.16
speaker: LOW
utterance:
alright, so in general, suppose I had this binary search tree and I have this humongous left subtree and this humongous right subtree.


session: S06-56
timestamp: 00:34:27.11
speaker: LOW
utterance:
so this has to be null because there can't be a left tree here (be)cause if there is a left tree there'd be a smaller one.


session: S06-56
timestamp: 00:34:41.17
speaker: LOW
utterance:
yeah, so whoosh, at least when you're moving up the three or the six you're not moving up another one with two kids.


session: S06-56
timestamp: 00:35:00.15
speaker: LOW
utterance:
as a matter of fact, I can throw in six and a quarter, six and three quarters, I could make a giant tree on the right of six.


session: S06-56
timestamp: 00:35:22.01
speaker: LOW
utterance:
so these guys don't have to be leaves as they were in the simple example but they at least don't have two kids.


session: S06-56
timestamp: 00:36:49.14
speaker: LOW
utterance:
anyways, it's less than eleven so it's over here, less than seven so it's here, less than five it's over here, less than four so it's over here.


session: S06-56
timestamp: 00:36:55.19
speaker: LOW
utterance:
but now if we want to delete eleven from this tree then what are the two possibilities for replacing it?


session: S06-56
timestamp: 00:37:13.12
speaker: LOW
utterance:
and then everybody would be happy because ten is bigger than these guys and ten is less than twelve.


session: S06-56
timestamp: 00:37:29.04
speaker: LOW
utterance:
in fact, that gets us into the last problem they have here rearrange the nodes of this tree to form a different binary search tree.


session: S06-56
timestamp: 00:37:37.00
speaker: LOW
utterance:
I think they're simply pointing out to you that there are many, many, many trees you could build from these nodes.


session: S06-56
timestamp: 00:37:47.00
speaker: LOW
utterance:
and to show you how to get another tree just pick these +// give me your favorite numbers and give these things in any random order.


session: S06-56
timestamp: 00:38:11.18
speaker: LOW
utterance:
I didn't want to say that but the tree is empty to start with and the first thing you insert is the root.


session: S06-56
timestamp: 00:38:39.06
speaker: 256
utterance:
like when you're making it like this, they don't have to go like two connected to eight connected to seven then +// they don't have to be connected in this order?


session: S06-56
timestamp: 00:38:49.12
speaker: 256
utterance:
like the two has to be connected to five, has to be connected to seven, and has to connect to eight, has to connect to three, has to connect to one, and has to connect to nine.


session: S06-56
timestamp: 00:39:07.04
speaker: LOW
utterance:
that's right, there's no branch between them because, yeah, because the three was less than five so we shown it this way.


session: S06-56
timestamp: 00:39:41.00
speaker: LOW
utterance:
and I think you mentioned this a minute ago suppose somebody was nice and friendly and sorted the numbers for you.


session: S06-56
timestamp: 00:40:27.22
speaker: LOW
utterance:
there is a subject called balanced trees which tries to keep the tree in a certain kind of balance but yeah so if you get them in just random order it's usually a pretty good balanced but not always.


session: S06-57
timestamp: 00:00:09.14
speaker: LOW
utterance:
*uh, in a particular implementation # the reason it's called a link list is that each node contains a link to the next one.


session: S06-57
timestamp: 00:01:07.08
speaker: LOW
utterance:
you have to go there to find the second, you have to go there to find the third, and go there to find the fourth.


session: S06-57
timestamp: 00:01:14.16
speaker: LOW
utterance:
and I have them kind of conveniently drawn like they're next to each other, in fact, that's just the convenience of the drawing, the first one may be in the middle of the memory, and then the second one may be in the beginning of the memory, and the third one may be at the end of the memory, and the fourth ones back at the middle of the memory.


session: S06-57
timestamp: 00:01:53.21
speaker: LOW
utterance:
this should be a guy's name, and his address, and his zip code, and his mother's maiden name, and his social security number, and all.


session: S06-57
timestamp: 00:02:02.08
speaker: LOW
utterance:
all right, the nice thing about link lists is it's easy to insert things in the middle, or delete things from the link list without xxx/xx very much.


session: S06-57
timestamp: 00:02:13.08
speaker: LOW
utterance:
they want us to describe a sequence of operations to insert a new node, which contains g@l in this list, after the node that contains b@l.


session: S06-57
timestamp: 00:02:26.24
speaker: LOW
utterance:
I'm gonna have a new node with g@l in it, and it's going to be after the node that has b@l, so we're gonna break this link and put a couple new links in.


session: S06-57
timestamp: 00:02:38.09
speaker: LOW
utterance:
*uh, unfortunately, thats not the end of the question, they want us to sort of describe how we would do that.


session: S06-57
timestamp: 00:03:23.00
speaker: LOW
utterance:
and in the picture you put t@l one up here and basically h@l one is the address to this node, so Im making t@l one equal h@l one, and this is the address of this node.


session: S06-57
timestamp: 00:04:58.00
speaker: LOW
utterance:
so we're going to imagine that this is just a simple step, just a process that gives you a new node, and you can say what you want to put in it, of course you can put g@l in it.


session: S06-57
timestamp: 00:06:06.01
speaker: LOW
utterance:
<we have> [//] before we made this change, we have this node pointing at this node that has f@l in it.


session: S06-57
timestamp: 00:07:37.28
speaker: LOW
utterance:
so yeah, you gotta be able to draw the after picture, or you won't stand a chance, but now we gotta describe how to do that.


session: S06-57
timestamp: 00:07:44.11
speaker: LOW
utterance:
well once again the only thing you have is a pointer to the first node, so if you want to delete a@l, you gotta find it.


session: S06-57
timestamp: 00:07:49.08
speaker: LOW
utterance:
so same thing as before, t@l one is going to be h@l two, while the info of t@l one is <not equal to e@l, I'm sorry> [//] not equal to a@l, and a@l is what we're looking for.


session: S06-57
timestamp: 00:10:19.08
speaker: LOW
utterance:
<so when you get down to this loop> [/] you get down to this loop and t@l one is pointing at the a@l, and t@l two is pointing at whatever comes before it.


session: S06-57
timestamp: 00:11:15.26
speaker: LOW
utterance:
we've got three elements which is a terribly small list, but suppose there's a hundred elements here, and a@l is anywhere between the second and the ninety ninth.


session: S06-57
timestamp: 00:12:49.26
speaker: LOW
utterance:
if +// and this is gonna be the case, it's the first element, and we decide what we're going to do, else, we're going to do this.


session: S06-57
timestamp: 00:12:58.20
speaker: LOW
utterance:
if it's not the first element, then there's one before it, and we'll make the one after it point after it.


session: S06-57
timestamp: 00:14:27.21
speaker: LOW
utterance:
in fact if it's a very precisely loaded spring there, you can't tell how many plates there are in a stack.


session: S06-57
timestamp: 00:14:44.23
speaker: LOW
utterance:
and when the guy comes to the kitchen with his clean plates, he puts them on one at a time, and the spring is so precisely loaded that the extra weight pushed them back down.


session: S06-57
timestamp: 00:18:07.28
speaker: LOW
utterance:
*uh, obviously, we're going to use a temporary variable count, which we're going to set to zero, okay?


session: S06-57
timestamp: 00:18:41.03
speaker: LOW
utterance:
*uh, pop, something off the s@l, it's the function, so lets just store it in v@l for a value for a minute.


session: S06-57
timestamp: 00:19:11.10
speaker: LOW
utterance:
there is a body of our little function that sets count at zero, pops and then counts them, until it's empty, and returns the count.


session: S06-57
timestamp: 00:19:41.03
speaker: LOW
utterance:
so people are probably not to happy to call this function and learn that four is what used to be in the stack and now it's now it's been destroyed.


session: S06-57
timestamp: 00:20:34.04
speaker: LOW
utterance:
so t@l is popped and put there, r@l is popped and put there, b@l is popped and put there, z@l is popped and put there, <and you increment> [//] you count and increment to four, and great this is a stack of four elements.


session: S06-57
timestamp: 00:20:44.28
speaker: LOW
utterance:
so lets just say s@l is equal to t@l, move them back over, and return four, and there's a stack, of four elements.


session: S06-57
timestamp: 00:20:56.24
speaker: LOW
utterance:
well they at least have a stack of four elements, but is it the same, exactly the same stack we started with?


session: S06-57
timestamp: 00:22:06.21
speaker: LOW
utterance:
but basically it's the opposite of this, *uh and that will put the z@l back and that will put the p@l back and that will put the r@l back.


session: S06-57
timestamp: 00:22:19.00
speaker: LOW
utterance:
again, with a stack, these are the only things you can do, and they don't really need top cause you can get that at the bottom push.


session: S06-57
timestamp: 00:23:16.15
speaker: LOW
utterance:
to be a binary search tree you also have the property that every level, that every node left is always smaller and right is always bigger.


session: S06-57
timestamp: 00:23:32.17
speaker: LOW
utterance:
nothing over here less bigger than four, but right is bigger than nothing less than four, but these guys are bigger than four.


session: S06-57
timestamp: 00:24:33.04
speaker: LOW
utterance:
yeah, five and eleven are reversed, and then ten is on the right, and twelve is on the left, and four is on the right, everything is flipped.


session: S06-57
timestamp: 00:24:41.01
speaker: LOW
utterance:
so that's what a binary search tree is, and now they give us one and they ask us to do some things with it.


session: S06-57
timestamp: 00:25:05.20
speaker: LOW
utterance:
oh they didn't mention it, and I haven't said anything, but the way you keep track of a binary search tree is through a pointer into the root.


session: S06-57
timestamp: 00:25:19.00
speaker: LOW
utterance:
alright, so five has a left kid two, which has a left kid one, which has a right kid three, five has a left kid nine, which has a right child eight, has a left child eight, and a right child seven.


session: S06-57
timestamp: 00:26:38.05
speaker: LOW
utterance:
but then you only looked at one node at this level, mainly the one larger than five, and you only looked at one node at this level, which would happen to be the one you wanted.


session: S06-57
timestamp: 00:27:23.11
speaker: LOW
utterance:
(be)cause you looked at that node at that level, and that node at that level, that node at that lever, and then you xxx.


session: S06-57
timestamp: 00:28:00.25
speaker: LOW
utterance:
so, basically, you searched for six and it wasn't there, and when the search failed, when you put it there.


session: S06-57
timestamp: 00:29:41.23
speaker: LOW
utterance:
so do you see an easy way to delete nine from this binary search tree, and keep it a binary search tree?


session: S06-57
timestamp: 00:30:09.00
speaker: LOW
utterance:
here we know the parent of nine, and we're going to make, Im going to call it the grandparent, point to the grandchild, okay?


session: S06-57
timestamp: 00:31:21.04
speaker: LOW
utterance:
they want to make it harder than it's five and two and this is such a small tree, we'd better stay with what they have and stay as high as possible in the tree so we can see whats going on.


session: S06-57
timestamp: 00:31:36.15
speaker: LOW
utterance:
*uh, and I think that's what everybody starts with, is they're going to try and either put two or nine up here in five's place.


session: S06-57
timestamp: 00:31:47.06
speaker: LOW
utterance:
*uh, I'm not quite sure what that means yet, because two is in fact, as you pointed out, has two kids.


session: S06-57
timestamp: 00:31:53.26
speaker: LOW
utterance:
so that will cause one two-kid thing and another two kid thing which might cause another two kid thing, which is a nightmare.


session: S06-57
timestamp: 00:31:59.11
speaker: LOW
utterance:
but ignoring that for a minute, Im gonna show you that two can't come up here, because three can't be on the left side of two, okay?


session: S06-57
timestamp: 00:32:43.07
speaker: LOW
utterance:
[be]cause we put the three up there, then these guys are smaller than the three, so they could be on the left.


session: S06-57
timestamp: 00:32:52.07
speaker: LOW
utterance:
<yep, so three is one possibility> [/] so three is a possibility on this side, and who could move up on this side?


session: S06-57
timestamp: 00:33:20.24
speaker: LOW
utterance:
well, if you put the eight up, then you got seven and six over here, but they're smaller than eight.


session: S06-57
timestamp: 00:34:18.12
speaker: LOW
utterance:
and the reason that works, is that three can be the parent of these guys because it's bigger than them.


session: S06-57
timestamp: 00:34:25.25
speaker: LOW
utterance:
and three is already smaller than that guy, so it could be the parent of these guys because they're bigger than them.


session: S06-57
timestamp: 00:34:37.20
speaker: LOW
utterance:
but six, okay all these are bigger than five, so six is bigger than five so it's bigger than all these guys.


session: S06-57
timestamp: 00:34:55.20
speaker: LOW
utterance:
well, you know, if you want the biggest one on the left you clearly go left once to get in the left subtree.


session: S06-57
timestamp: 00:35:12.24
speaker: LOW
utterance:
yeah, you keep going right, because if a four is in the tree, and a four and a half is in the tree, and a four points at nine +...


session: S06-57
timestamp: 00:35:20.14
speaker: LOW
utterance:
you've got the smallest one over here, you clearly go right once to get into that tree, and then smaller, smaller, smaller, you go down as far as you can.


session: S06-57
timestamp: 00:36:15.00
speaker: LOW
utterance:
I could put six and a half here, bigger than five, smaller, smaller, smaller, bigger than six and then six quarters, six and three quarters +...


session: S06-57
timestamp: 00:37:12.12
speaker: LOW
utterance:
and that works, cause it's the smallest over here and therefore this tree is okay, cause these guys are all bigger than six.


session: S06-57
timestamp: 00:37:52.27
speaker: LOW
utterance:
so to show you how there are many many many other trees, I will show you how a tree can be built from nothing.


session: S06-57
timestamp: 00:39:28.16
speaker: LOW
utterance:
it's not the case that every permutation gives you a different tree, but it's easy to get bigger trees.


session: S06-58
timestamp: 00:00:10.19
speaker: JAC
utterance:
um in the stack every time you put something +// a piece of information down you always put it on the stack on top, right?


session: S06-58
timestamp: 00:01:37.28
speaker: JAC
utterance:
what pop is it's destructive and it removes whatever value top would give us so in this case it would remove four.


session: S06-58
timestamp: 00:01:57.18
speaker: JAC
utterance:
if I want to get a value +// if I wanted say +// if I wanted to set a@l equal to whatever is on the top of the stack and then remove it I would say a@l equals top and then I would call pop.


session: S06-58
timestamp: 00:02:14.00
speaker: JAC
utterance:
then I would have gotten a@l would now equal four and then the top if I call top now would +// b@l would equal five.


session: S06-58
timestamp: 00:03:26.24
speaker: 258
utterance:
um I think like stacks are normally used in like in returning a value and calling  functions, right?


session: S06-58
timestamp: 00:03:34.26
speaker: JAC
utterance:
right # in memory um you can use the stack um for anything operationalized so you can um you can do +// it's been a while since I've done stuff like this.


session: S06-58
timestamp: 00:03:49.13
speaker: JAC
utterance:
um # uh right so you could call top and get three um pop it off and call the next and then you could have +// you'd end up getting that, right?


session: S06-58
timestamp: 00:04:21.01
speaker: JAC
utterance:
you can do that when +// you can do that with +// memory deals with that um when you run a program you do everything thrown on the stack so xxx xxx.


session: S06-58
timestamp: 00:04:53.04
speaker: JAC
utterance:
each parent has children and the way we decide where a child goes is based on the parent and its child +// its right child has to be greater in value than itself and its left child has to be less in value.


session: S06-58
timestamp: 00:05:16.24
speaker: JAC
utterance:
so we're going to go through this one here and determine whether +// these four here and determine whether they're binary search trees or not, okay?


session: S06-58
timestamp: 00:05:27.20
speaker: JAC
utterance:
we always go by convention and we always check the right child first before checking the left children, okay?


session: S06-58
timestamp: 00:05:41.29
speaker: JAC
utterance:
twelve has no right child # twelve has no left child so then we would come back to eleven and start checking its left children.


session: S06-58
timestamp: 00:06:21.09
speaker: JAC
utterance:
+< no it's a +// every time +// the relationship between seven and eleven # eleven is greater than seven.


session: S06-58
timestamp: 00:06:51.00
speaker: JAC
utterance:
the first major thing you have to know is that whatever you put in here you have to be able to compare.


session: S06-58
timestamp: 00:07:06.08
speaker: JAC
utterance:
I can't compare apples and oranges because they're too different but I can compare maybe the number of apples and the number of oranges, right?


session: S06-58
timestamp: 00:07:36.03
speaker: JAC
utterance:
if the parent was zero and the right child +// the right child could be anything greater than zero so I'm going to use one.


session: S06-58
timestamp: 00:08:23.17
speaker: JAC
utterance:
or can be a parent so the relationship between its right child and its left child has to be the same as would this parent so in this case if we have one this can be um two and then this could be a half.


session: S06-58
timestamp: 00:08:41.12
speaker: JAC
utterance:
now the reason I picked a half instead of like negative one or negative two is because when I came in here we had to also check which side we were going, right?


session: S06-58
timestamp: 00:09:00.27
speaker: JAC
utterance:
uh but with a half I would have gone this way +// would have come here and compared half to one # one is less than half so it would be here.


session: S06-58
timestamp: 00:09:10.13
speaker: JAC
utterance:
so that's the relationship we'll always have # the right child will always have greater value than its parent and the left child will always have a smaller value.


session: S06-58
timestamp: 00:09:50.25
speaker: JAC
utterance:
if this eight was here instead and this is fine this has no violations then it would be a binary search tree but since eight is on the right child it's not a binary search tree.


session: S06-58
timestamp: 00:10:53.21
speaker: JAC
utterance:
matter of fact our two rules of the right child always being greater and the left child always being less is always violated in this case # it's exactly opposite.


session: S06-58
timestamp: 00:11:33.12
speaker: JAC
utterance:
so the first question asks us to show the path to search for eight in a given binary search tree, okay?


session: S06-58
timestamp: 00:11:52.09
speaker: JAC
utterance:
so we compare the value we're looking for # just eight with the value in the node we're looking at and we make our decision whether to go left or right or say we found it, right?


session: S06-58
timestamp: 00:12:25.00
speaker: JAC
utterance:
so if eight is in the tree # it is going to be the left child of nine or some child down the line, right?


session: S06-58
timestamp: 00:12:45.28
speaker: JAC
utterance:
um depending on how we were to write this we might return a value of true because we found it or you might return this child +// this node or a node as it's also referred to.


session: S06-58
timestamp: 00:14:22.15
speaker: JAC
utterance:
by convention we don't show it because we'd be adding an extra +// these are called levels +// we'd be adding an extra level to every tree, right?


session: S06-58
timestamp: 00:14:37.11
speaker: JAC
utterance:
if it's not there we know it's there +// if it's not shown we know there's null but when we're searching is what we'd do is we'd find this null.


session: S06-58
timestamp: 00:15:00.11
speaker: JAC
utterance:
um the reason we might return null is because I'm looking for four to see if four is in there but four is not in there so I'm going to insert it.


session: S06-58
timestamp: 00:15:08.05
speaker: JAC
utterance:
well, instead of me searching # again for where four goes I just insert it right here where we found it, okay?


session: S06-58
timestamp: 00:15:16.08
speaker: JAC
utterance:
(be)cause it could have +// like I said these are all levels +// I could have a tree with a thousand levels, right?


session: S06-58
timestamp: 00:15:24.04
speaker: JAC
utterance:
and I would have to search through all one thousand levels assuming this was on the thousandth level to insert it.


session: S06-58
timestamp: 00:16:28.14
speaker: JAC
utterance:
seven has no left child, it's null so since we found null we know we can insert it in its left child, here.


session: S06-58
timestamp: 00:17:21.05
speaker: JAC
utterance:
well, problem is if we delete this +// we can't just delete this node and be like okay we're done because we'll leave everything here hanging, right?


session: S06-58
timestamp: 00:17:49.28
speaker: JAC
utterance:
what will happen is nine +// I'm sorry +// five wherever nine's parent is will inherit nine's left child.


session: S06-58
timestamp: 00:18:03.28
speaker: JAC
utterance:
nine will disinherit eight # it's already disinherited by five then we delete it so the resulting tree +// that will be our resulting tree.


session: S06-58
timestamp: 00:19:20.08
speaker: JAC
utterance:
we can't do what we did before and just make nine the new node to take the place +// excuse me +// because what happens is eight and seven are now less than nine and they'd have to be in the left side of the tree.


session: S06-58
timestamp: 00:19:41.05
speaker: JAC
utterance:
what we do instead is we look at the right child # we find out that the node we're deleting has a right child then we start looking for the left most child.


session: S06-58
timestamp: 00:19:54.18
speaker: JAC
utterance:
the left most child means we're going to keep going down the line until we find the child that +// the child that's on the left and then we check its child on the left and we check its child on the left and until there are no more left children.


session: S06-58
timestamp: 00:20:17.09
speaker: JAC
utterance:
the reason we do that is because this number here is the number that is err this value, if we're using anything else, this value is the closest to this.


session: S06-58
timestamp: 00:20:31.17
speaker: JAC
utterance:
this will always be larger but the number or the value that is closest to this independent value, okay?


session: S06-58
timestamp: 00:20:45.04
speaker: JAC
utterance:
if we go to the left most everything +// if we keep going to the left everything will keep getting smaller than what it's parent was, right?


session: S06-58
timestamp: 00:21:00.16
speaker: JAC
utterance:
but they keep getting smaller until I'm at five point zero zero zero zero zero one or something, right?


session: S06-58
timestamp: 00:21:21.19
speaker: JAC
utterance:
so what happens is seven will take the place of five so seven inherits # nine and it inherits three and one.


session: S06-58
timestamp: 00:22:15.08
speaker: JAC
utterance:
seven point five is less than eight which would be the left child while its left child is seven so I came back to seven, right?


session: S06-58
timestamp: 00:22:22.05
speaker: JAC
utterance:
I'm stuck in a circle so that's why you want to make sure to delete this connection otherwise we'd get stuck in an infinite +// infinite loop here.


session: S06-58
timestamp: 00:23:02.08
speaker: JAC
utterance:
also by looking at this we know nine had to be inserted before eight # eight had to be inserted before seven.


session: S06-58
timestamp: 00:24:28.03
speaker: JAC
utterance:
pop it off, call top again # one is less than seven, one is less than five, one is less than two # one would go here, right?


session: S06-58
timestamp: 00:25:10.29
speaker: JAC
utterance:
order makes a difference however if I did in here where I have one and three, if I did three here and one here I would have still gotten the same tree.


session: S06-58
timestamp: 00:25:48.26
speaker: JAC
utterance:
um probably the easiest way to think of a linked list is like a line or like a movie +// you go to a line, you go to a movie theater, you go to the cafeteria you wait in line, right?


session: S06-58
timestamp: 00:26:29.25
speaker: JAC
utterance:
each person in line or in this case each node # they're called nodes but if we think of it +// use an analogy and think of it as people.


session: S06-58
timestamp: 00:26:44.19
speaker: JAC
utterance:
each person, however, can look over their shoulder and see the person in front of them or behind them rather, okay?


session: S06-58
timestamp: 00:27:17.27
speaker: JAC
utterance:
so # if +// here it's asking us to describe the sequence of operations to insert a new node which contains g@l in uh list one after the node containing b@l.


session: S06-58
timestamp: 00:27:38.10
speaker: JAC
utterance:
somewhere +// if we want to use our line analogy um Bob if I call this Bob and I call this Greg um Bob knows Greg and wants to cut in behind him in line.


session: S06-58
timestamp: 00:28:04.11
speaker: JAC
utterance:
we have to find the front of the line and go through more so the next thing we do is the head tells us who's first in line.


session: S06-58
timestamp: 00:29:04.25
speaker: JAC
utterance:
he's currently pointing to Fred so the first thing we have to do is we have to tell +// we tell g@l that we're pointing to Fred and we point to Fred.


session: S06-58
timestamp: 00:29:27.29
speaker: JAC
utterance:
the reason why I have +// tell g@l where I'm pointing to first is because I don't want to lose Fred.


session: S06-58
timestamp: 00:29:32.05
speaker: JAC
utterance:
if I remove my connection +// if Bob points to g@l first Greg then there's no more +// I don't know who is behind +// behind him anymore.


session: S06-58
timestamp: 00:29:45.18
speaker: JAC
utterance:
(be)cause all I know is that g@l was behind him and g@l doesn't know who was behind him at all # he doesn't have anyone set so we set it first.


session: S06-58
timestamp: 00:30:45.26
speaker: JAC
utterance:
and he tells me a@l and I go to a@l and I can still be at e@l and go +// I can go +// e@l goes who's next and asks them who's next?


session: S06-58
timestamp: 00:31:34.26
speaker: JAC
utterance:
now if we want to add +// take two lists and compile +// merge them together +// we have list one which is +...


session: S06-58
timestamp: 00:32:38.01
speaker: JAC
utterance:
so I come through and I look at the first list and I have to find where the end of the line is (be)cause I'm just merging them together so I get all the way down to Fred and Fred tells me or f@l that's the end of the line, right?


session: S06-58
timestamp: 00:32:51.29
speaker: JAC
utterance:
so now I need to look at this one here # the head of the other line and I find out what it's pointing to.


session: S06-58
timestamp: 00:32:59.25
speaker: JAC
utterance:
whatever it's pointing to f@l is going to point to that now so we reference the head and find out what it's pointing to and it's pointing to e@l, right?


session: S06-58
timestamp: 00:33:18.20
speaker: JAC
utterance:
if it didn't have a null then we would have a problem but because it is a properly formed linked list it's not a problem.


session: S06-58
timestamp: 00:33:31.23
speaker: JAC
utterance:
we don't want to be able to point +// someone to think this is the beginning of a list (be)cause we want only this to be the beginning of the list.


session: S06-58
timestamp: 00:34:52.11
speaker: JAC
utterance:
so the first thing we have to do is find k@l so we go through +// reference the head and keep going through until we find k@l.


session: S06-58
timestamp: 00:35:25.04
speaker: JAC
utterance:
now instead of k@l pointing to b@l # k@l is going to reference the head again and point to whatever it's first pointing to # so it points to that.


session: S06-59
timestamp: 00:00:08.24
speaker: JAC
utterance:
uh when we think of the stack you can think of it as um either like laying bricks or like Legos # anything you can stack on top of each other.


session: S06-59
timestamp: 00:01:08.08
speaker: JAC
utterance:
push always takes a value so in our case we would first push nine followed by push eight, followed by push seven


session: S06-59
timestamp: 00:01:26.26
speaker: JAC
utterance:
now if I ever want to get the value of something on the stack I only have one way to do that and that's called top.


session: S06-59
timestamp: 00:01:58.23
speaker: JAC
utterance:
think of it as if you look down on a stack of bricks if we wrote numbers on each one and only if we wrote them on the top, right?


session: S06-59
timestamp: 00:02:16.13
speaker: JAC
utterance:
well, that's exactly what we have to do in this case if we want to see what's on the next brick we have to remove this one.


session: S06-59
timestamp: 00:03:23.07
speaker: JAC
utterance:
um I don't want you to think I have to do all my pushing first and then all my popping after # you can mix (th)em up in any way, shape or form.


session: S06-59
timestamp: 00:03:59.03
speaker: JAC
utterance:
I'm going to go over the concept of what a binary search tree is and we're going to try and figure out if these are binary search trees or not.


session: S06-59
timestamp: 00:04:37.11
speaker: JAC
utterance:
each child can also have a parent or I'm sorry, each child can also be a parent and have its own children.


session: S06-59
timestamp: 00:04:49.19
speaker: JAC
utterance:
what we have is a relationship between a parent and children # we have a right child and we have a left child.


session: S06-59
timestamp: 00:04:59.19
speaker: JAC
utterance:
the value of a right child is always greater than the parent and the value of a left child is always less than the parent, okay?


session: S06-59
timestamp: 00:05:24.20
speaker: JAC
utterance:
we're at a right child but the right child is also a parent so its right child should be greater and its left child should also be less, right?


session: S06-59
timestamp: 00:05:33.11
speaker: JAC
utterance:
so now we're going to try and figure out if this is a binary search tree we're just going to use those two rules.


session: S06-59
timestamp: 00:05:38.22
speaker: JAC
utterance:
so by convention we always start at the root +// at the parent and the first parent is oftentimes referred to as the root, okay?


session: S06-59
timestamp: 00:05:49.23
speaker: JAC
utterance:
so we look at the root and we look at its right child and we look at it and we compare and eleven is greater than seven so so far this is fine.


session: S06-59
timestamp: 00:06:08.24
speaker: JAC
utterance:
we would check twelve's right child and it doesn't have one and we would check its left child following that but it doesn't have one so we go back up to eleven and check its left child.


session: S06-59
timestamp: 00:06:42.24
speaker: JAC
utterance:
five has no children, four has no left child and we come back to seven since we can check both left and right children of seven and we had no um nothing violating the rules then this would be a binary search tree, okay?


session: S06-59
timestamp: 00:07:01.10
speaker: JAC
utterance:
just so you notice, five, even though it's less than seven and twelve +// or eight even though it's less than eleven, it's still greater than seven.


session: S06-59
timestamp: 00:07:15.04
speaker: JAC
utterance:
in order for it to be on this side it would also have to be less +// it also has to be +// not violate this rule here where it's right +// everything on this right side has to be greater than the parent.


session: S06-59
timestamp: 00:08:24.12
speaker: JAC
utterance:
we check its left child which is eight (be)cause we didn't have a right child so we went straight to the left # that's fine.


session: S06-59
timestamp: 00:09:14.14
speaker: JAC
utterance:
we're going to be asked questions about it and do things with it and # I don't like the order they do these in so # we're going to jump around a little bit.


session: S06-59
timestamp: 00:09:30.29
speaker: JAC
utterance:
so first thing I'm going to deal with is I'm going to deal with searching for something so I'm going to start here with five and six.


session: S06-59
timestamp: 00:09:59.28
speaker: JAC
utterance:
so what we always do first is we come to the root and we compare +// step one # we compare whatever we're searching for with the root to determine whether we look at the right side of the tree or the left side of the tree.


session: S06-59
timestamp: 00:10:16.02
speaker: JAC
utterance:
each time, assuming that +// let's assume that the tree +// each side of the tree has the same number of nodes or same number of children.


session: S06-59
timestamp: 00:10:43.11
speaker: JAC
utterance:
so that's what I'm doing here # I'm trying to narrow everything down so first thing I'm going to do is compare eight and five.


session: S06-59
timestamp: 00:10:50.18
speaker: JAC
utterance:
eight is greater than five so if it is in the binary search tree it has to be somewhere to the right children of five.


session: S06-59
timestamp: 00:11:14.21
speaker: JAC
utterance:
so there's our xx so depending on how we'd be writing this we might say, true # we found it, it's here.


session: S06-59
timestamp: 00:11:21.27
speaker: JAC
utterance:
uh or you might actually return this child to whoever is asking for it um but we're only asked in this case to show the path so this would be the path to search for eight.


session: S06-59
timestamp: 00:11:36.05
speaker: JAC
utterance:
now if we're asked to search +// the following question # the search question asks us to search for four so just like we did before +// I'm just going to use the same one (be)cause we're using the other branch.


session: S06-59
timestamp: 00:11:55.12
speaker: JAC
utterance:
step two we compare four and two # four is greater than two so we go to the right +// we go to its right child.


session: S06-59
timestamp: 00:12:21.18
speaker: JAC
utterance:
that's important because when we're doing a search if we ever find null we know we're not going any further, right?


session: S06-59
timestamp: 00:12:36.20
speaker: JAC
utterance:
now we might return false because we didn't find it or we might return null or a null pointer, the null node because okay I didn't find four in the tree well I want to put four in the tree.


session: S06-59
timestamp: 00:12:52.13
speaker: JAC
utterance:
so instead of me doing a search again to try and insert it I already have where it goes so I can just put four in there, okay?


session: S06-59
timestamp: 00:13:08.06
speaker: JAC
utterance:
um now I'm going to work on insertion # I'll show you how insertion works which works exactly like search.


session: S06-59
timestamp: 00:13:28.15
speaker: JAC
utterance:
you'll see that the search algorithm +// how we search for things is used for almost everything when you're doing something with a binary search tree.


session: S06-59
timestamp: 00:14:40.16
speaker: JAC
utterance:
if the tree was built differently there would be another +// we'd have another option but we only have the one option for that tree, okay?


session: S06-59
timestamp: 00:14:51.12
speaker: JAC
utterance:
so this is the only place six can go and if we were searching for six before we would have gotten here.


session: S06-59
timestamp: 00:15:04.09
speaker: JAC
utterance:
(be)cause we're always using the same search pattern and the reason that is +// the reason why it always works is because we're always following the rules, okay?


session: S06-59
timestamp: 00:16:10.25
speaker: JAC
utterance:
nine has no right child so what we do then is we take its left child and we have uh nine's parent inherit eight as its child.


session: S06-59
timestamp: 00:16:26.04
speaker: JAC
utterance:
nine disinherits eight and gets deleted so our resulting tree and I'm just going to draw one side +// I'll draw the other side.


session: S06-59
timestamp: 00:16:46.15
speaker: JAC
utterance:
so I deleted nine and I kept the structure +// I kept the structure essentially the same so I didn't violate any rules, alright?


session: S06-59
timestamp: 00:17:01.22
speaker: JAC
utterance:
now I'm going to show you a more complicated deletion and it's not more complicated +// it's more complicated because it has a right child but it's not overly difficult.


session: S06-59
timestamp: 00:17:43.29
speaker: JAC
utterance:
I can't make um two the new parent +// the new root because now I have three that's needs to go over here and everything needs to be rearranged # it's going to require a lot of work.


session: S06-59
timestamp: 00:18:18.02
speaker: JAC
utterance:
since we have a right child what we want to do is we want to look at every left child of this right child until we have no more left children.


session: S06-59
timestamp: 00:18:54.13
speaker: JAC
utterance:
what the relationship between the node that's being deleted and the left most child, this value is greater than the node that's being deleted but is closest in value to it.


session: S06-59
timestamp: 00:19:10.12
speaker: JAC
utterance:
I want to put something as close as possible to this value because then it's not going to damage the tree, right?


session: S06-59
timestamp: 00:19:27.23
speaker: JAC
utterance:
if I put seven here we're not going to have a problem so what happens is seven inherits all the children of five so it inherits nine and two.


session: S06-59
timestamp: 00:20:09.02
speaker: JAC
utterance:
if I look for value 7.5 # 7.5 is greater than seven, less than nine, less than eight and seven is still the left child of seven # I'll just come back to where I started and I'll keep searching, right?


session: S06-59
timestamp: 00:20:26.14
speaker: JAC
utterance:
so I'm stuck in an infinite loop so it's important that we also delete this connection so we don't have this as our resulting tree.


session: S06-59
timestamp: 00:21:03.18
speaker: JAC
utterance:
now five had to be the very first number that was put into the binary search tree so I'm going to make sure I don't start with five.


session: S06-59
timestamp: 00:21:20.18
speaker: JAC
utterance:
uh at this point anything else I choose will make a different binary search tree, however, I can choose it in such a way it's almost exactly the same or I can try to make it somewhat different.


session: S06-59
timestamp: 00:22:56.10
speaker: JAC
utterance:
so totally different binary search tree but using the same numbers so order makes somewhat of a difference.


session: S06-59
timestamp: 00:23:03.01
speaker: JAC
utterance:
however, if I put, for example I had nine and five # if I had five and nine instead in that order I still would have ended up with the same tree.


session: S06-59
timestamp: 00:23:16.07
speaker: JAC
utterance:
the reason that is because while order makes a difference # order only makes a difference on the nodes below it, right?


session: S06-59
timestamp: 00:23:27.26
speaker: JAC
utterance:
if one came before three it would be +// make a different tree but it doesn't matter what order one and five and nine come in.


session: S06-59
timestamp: 00:23:37.24
speaker: JAC
utterance:
also I could have built this entire side of the tree before I did this side # that wouldn't make a difference.


session: S06-59
timestamp: 00:24:03.06
speaker: JAC
utterance:
alright the easiest way to think of a linked list is to think of it as a line # a movie line, a line in a cafeteria, wherever you can wait.


session: S06-59
timestamp: 00:24:22.02
speaker: JAC
utterance:
the way we find the beginning of a line is through the head # the head points to the beginning of a line and we have null which tells us where's the end of the line.


session: S06-59
timestamp: 00:24:37.00
speaker: JAC
utterance:
the head tells us who points to the front and shows us who the first person is, however, each person tells us who's next # who's behind them so if you think of it this way Carl can turn around and look at Kim, can see Kim and tell us Kim is next.


session: S06-59
timestamp: 00:25:11.00
speaker: JAC
utterance:
Bob, however, can't see the end of the line is after Fred, but Fred can tell us the end of the line is after him, okay?


session: S06-59
timestamp: 00:25:21.17
speaker: JAC
utterance:
alright, following that concept if we're asked um to insert a node or insert a person if we use our analogy uh we're asked to insert Greg after Bob, okay?


session: S06-59
timestamp: 00:26:11.26
speaker: JAC
utterance:
so the first thing we do is we look for and call the head and we start looking for Bob so we go to Carl and we ask Carl who's next and it's Kim, well, Kim is not who we're looking for so we ask Kim who's next and she says Bob.


session: S06-59
timestamp: 00:26:29.05
speaker: JAC
utterance:
so we want to insert Greg after Bob so what we do is we find out who Bob is pointing to which is Fred.


session: S06-59
timestamp: 00:27:03.23
speaker: JAC
utterance:
the reason we couldn't have Bob point to Greg first and then Greg point to Fred is because we lose Fred.


session: S06-59
timestamp: 00:28:07.23
speaker: JAC
utterance:
so the first thing we have to do is find a@l so we come through and we find e@l and e@l points to a@l.


session: S06-59
timestamp: 00:28:26.13
speaker: JAC
utterance:
and a@l will tell e@l that m@l is after a@l so e@l goes okay we go to +// keep a finger here and we move to a@l and we tell e@l to point to m@l.


session: S06-59
timestamp: 00:29:15.05
speaker: JAC
utterance:
if I just deleted a@l without telling e@l now we lost m@l and if there were anyone past m@l we lost them too.


session: S06-59
timestamp: 00:29:27.12
speaker: JAC
utterance:
so now we're going to +// we're asked to describe the sequence of operations to add the two lists together so I got to take e@l basically and put if after f@l.


session: S06-59
timestamp: 00:30:20.02
speaker: JAC
utterance:
so we want to add list two to the end of list one so what we do is we come to list one and we go and look for null.


session: S06-59
timestamp: 00:30:44.00
speaker: JAC
utterance:
we come to f@l and we find that f@l is pointing to null so what we need to do is instead of f@l pointing to null we need it to point to whatever the head of list two is, right?


session: S06-59
timestamp: 00:30:56.10
speaker: JAC
utterance:
so since we can reference this we find out what it's pointing to # it's pointing to e@l so we can instead of point to null we can point to e@l # and since this is a correctly formed linked list this points to null, right?


session: S06-59
timestamp: 00:31:12.25
speaker: JAC
utterance:
so we have an end of the line, however, we can't have two beginnings so what we end up doing is deleting the head, right?


session: S06-59
timestamp: 00:31:24.07
speaker: JAC
utterance:
(be)cause we don't want it to be able to point to the middle of the line and think it's the beginning.


session: S06-59
timestamp: 00:31:45.15
speaker: JAC
utterance:
describe the sequence of operations to invert the nodes in list two +// invert means to change the order of the nodes +// that contain c@l, m@l, e@l, and a@l.


session: S06-59
timestamp: 00:32:47.05
speaker: JAC
utterance:
alright, well, the first thing we can do is we can go through the list and we can find what's the last node.


session: S06-59
timestamp: 00:33:02.09
speaker: JAC
utterance:
alright so we'll find the last one and we say +// we create a new list h@l two prime or whatever that's equal, you set that.


session: S06-59
timestamp: 00:33:32.25
speaker: JAC
utterance:
then I can come through again and find a@l and then delete this and then do the same thing with e@l and do it that way.


session: S06-59
timestamp: 00:34:49.11
speaker: JAC
utterance:
um we could # find out what a@l is pointing to which is m@l and make sure that m@l is pointing to null and have m@l point to a@l, right?


session: S06-59
timestamp: 00:35:15.28
speaker: JAC
utterance:
uh we delete this connection and we find +// we kind of keep track of everything +// keep our finger and keep asking who's pointing to who.


session: S06-59
timestamp: 00:35:36.16
speaker: JAC
utterance:
since e@l points to the head e@l can point to null # and since the head was pointing to e@l we change the head to point to m@l.


session: S06-60
timestamp: 00:00:05.00
speaker: JAC
utterance:
and um when we think of the stack best way to think about it is to think about uh like bricks or like Legos.


session: S06-60
timestamp: 00:01:03.00
speaker: JAC
utterance:
in order for us to lay down our brick or put something into the stack we have this operation just called push.


session: S06-60
timestamp: 00:01:50.00
speaker: JAC
utterance:
and the way we can think of the reason why that is assume that if we look down on the brick, you know, we're looking down.


session: S06-60
timestamp: 00:03:41.00
speaker: JAC
utterance:
so I can do these things in any order but once I have nothing in the stack when I try and pop it doesn't remove anything.


session: S06-60
timestamp: 00:05:01.00
speaker: JAC
utterance:
if I have a +// if you have an array you need to search through the entire thing to find a particular, right?


session: S06-60
timestamp: 00:05:07.00
speaker: JAC
utterance:
this is sorted in such a way where every time we make a choice you cut through the number of choices in half.


session: S06-60
timestamp: 00:05:15.00
speaker: JAC
utterance:
so if I have a hundred choices I make my first decision and I remove 50 choices and there are 50 left.


session: S06-60
timestamp: 00:05:41.00
speaker: JAC
utterance:
the relationship between the parent and its right child is that the right child is always greater in value than the parent.


session: S06-60
timestamp: 00:06:09.00
speaker: JAC
utterance:
if anything ever +// if we ever deviate in any way from any of those rules then we're making a mistake.


session: S06-60
timestamp: 00:07:11.00
speaker: JAC
utterance:
ten has no children and eight has no left child so we'd come back to 11 and we come back up to seven.


session: S06-60
timestamp: 00:08:00.00
speaker: JAC
utterance:
and when we +// when I show you how to insert something the reasoning behind that will become apparent.


session: S06-60
timestamp: 00:09:20.00
speaker: 260
utterance:
okay only question I have is when you're going +// the procedure you use you seem like you're going all the way to one way before you get stopped.


session: S06-60
timestamp: 00:09:56.00
speaker: JAC
utterance:
and then since everything here and below it have been done I can come back up and start checking everything on its left side.


session: S06-60
timestamp: 00:10:10.00
speaker: JAC
utterance:
I get everything done and then when I come back up to seven I would start checking everything on its left side.


session: S06-60
timestamp: 00:10:33.00
speaker: JAC
utterance:
xxx I mean you could +// you could go through and go, +// I mean once you get it down this is fine (x3) and this is a violation, right?


session: S06-60
timestamp: 00:10:42.15
speaker: JAC
utterance:
I mean when you um +// the algorithm basically is how the computer does it and once you understand that you can go and say, I can look at this and say here's my violation here, right?


session: S06-60
timestamp: 00:12:30.23
speaker: JAC
utterance:
if it was +// if the value we were searching for was less than whatever is in the root we go to the left.


session: S06-60
timestamp: 00:12:45.05
speaker: JAC
utterance:
eight is less than nine so if eight is in the tree it has to be somewhere along the left children of nine.


session: S06-60
timestamp: 00:12:54.05
speaker: JAC
utterance:
I mean I could have eight point five next and then I could have eight but we're dealing with just whole numbers right now.


session: S06-60
timestamp: 00:13:20.14
speaker: JAC
utterance:
depending on how someone was writing this they might return the value or sometimes it's referred to as the node, okay?


session: S06-60
timestamp: 00:13:44.16
speaker: JAC
utterance:
this +// suppose we could have the number is one thing but it might have additional information in it that we might want to get out of it, right?


session: S06-60
timestamp: 00:13:55.03
speaker: JAC
utterance:
okay we have a number like a studnent I@l D@l but we want to get the student's name and the student's phone number or their address.


session: S06-60
timestamp: 00:15:11.01
speaker: JAC
utterance:
it's a node +// it's an actual node +// it's an actual child but it's a child that tells us there's nothing here.


session: S06-60
timestamp: 00:15:32.11
speaker: JAC
utterance:
when we hit null when we're searching for something we know it's not there # because the only place that four could possibly be in this tree was here.


session: S06-60
timestamp: 00:15:52.10
speaker: JAC
utterance:
I mean I could have put five here but then I would have checked three point five and it would have null.


session: S06-60
timestamp: 00:16:03.08
speaker: JAC
utterance:
now you might return false (be)cause it's not in the tree or you might return null because you want to insert it and you know it has to go here.


session: S06-60
timestamp: 00:16:47.04
speaker: JAC
utterance:
better to +// it's best to search just the one time and be like, okay here's where it should go do I need to insert it or not?


session: S06-60
timestamp: 00:17:04.03
speaker: JAC
utterance:
for this next problem we're asked to insert something and this will kind of explain why we can't have something +// everything is in relation to everything else but basically +...


session: S06-60
timestamp: 00:17:42.13
speaker: JAC
utterance:
so anything that's greater than five +// since we're inserting it we have to make this comparison first.


session: S06-60
timestamp: 00:17:52.03
speaker: JAC
utterance:
so assuming it's always built right we never have to worry about something on this side being less than five.


session: S06-60
timestamp: 00:18:37.25
speaker: JAC
utterance:
so basically if you were asked to draw the resulting tree this is where +// you would just draw six here.


session: S06-60
timestamp: 00:21:30.29
speaker: JAC
utterance:
since it has a right child what we're going to do is start checking every left child until we can't find a left child.


session: S06-60
timestamp: 00:21:38.23
speaker: JAC
utterance:
so basically we're going to +// we found nine at its right child and we're going to its left child which is eight.


session: S06-60
timestamp: 00:21:51.21
speaker: JAC
utterance:
the relationship between the node we're deleting and this left most child is that it is the number +// the value closest to the value that we're deleting.


session: S06-60
timestamp: 00:22:13.23
speaker: JAC
utterance:
they still would have kept going in here on the left and that would have been closer to five, right?


session: S06-60
timestamp: 00:22:21.07
speaker: JAC
utterance:
the reason we want to do that is because if we had promoted nine here now eight and seven are on the wrong side of the tree.


session: S06-60
timestamp: 00:23:05.20
speaker: JAC
utterance:
this would be the resulting tree, however, we have to remember currently seven is the left child of eight, right?


session: S06-60
timestamp: 00:23:25.22
speaker: JAC
utterance:
seven's left child is back here so I'd be stuck in an infinite loop trying to find seven point five, right?


session: S06-60
timestamp: 00:24:15.22
speaker: JAC
utterance:
however because of the relationship between one and +// between one and two and three and two the order between these two doesn't matter as long as they come after two.


session: S06-60
timestamp: 00:24:44.02
speaker: JAC
utterance:
so really if I want to make a different binary search tree all I have to do  +// and I'm going to use our stack +// all I have to do is change the first node really, right?


session: S06-60
timestamp: 00:25:18.10
speaker: JAC
utterance:
either way, I'm starting with something different as the root and it's going to be a different binary search tree, right?


session: S06-60
timestamp: 00:25:33.09
speaker: JAC
utterance:
um I'm using the stack to build a binary search tree but I could use a binary search tree for anything you can compare.


session: S06-60
timestamp: 00:25:47.24
speaker: JAC
utterance:
if I want to search like I said if we took the university student list and put everyone's U@l I@l N@l number because it's distinct, right?


session: S06-60
timestamp: 00:25:59.22
speaker: JAC
utterance:
and I +// somebody's U@l I@l N@l number is on the top I can say I'm looking for this particular U@l I@l N@l number and I can go through the tree and keep cutting it in half, right?


session: S06-60
timestamp: 00:26:14.11
speaker: JAC
utterance:
so if there's 10,000 people on my first decision I can go from 10,000 people I have to pick to 5,000.


session: S06-60
timestamp: 00:26:38.09
speaker: JAC
utterance:
and that's, you know, we can assume that it takes so much time to search through each node and to check it, right?


session: S06-60
timestamp: 00:26:49.18
speaker: JAC
utterance:
you know, a long time versus +// I only have to check maybe eight or nine times before I figure out whether this person is in there or not?


session: S06-60
timestamp: 00:27:07.27
speaker: JAC
utterance:
I mean there are more efficient designs than this I mean there are many different binary search trees or search trees in general.


session: S06-60
timestamp: 00:27:17.22
speaker: JAC
utterance:
um there's one where any time you search for something it rotates it up towards the top to the root.


session: S06-60
timestamp: 00:27:25.03
speaker: JAC
utterance:
and the root +// the reason that is is because anything you search for it's thought you're going to be searching for it again and it'll be towards the top.


session: S06-60
timestamp: 00:27:47.05
speaker: JAC
utterance:
so in this case that we're going to rearrange seven is our root so I call top and then pop it, right?


session: S06-60
timestamp: 00:28:39.25
speaker: JAC
utterance:
try and keep everything balanced so no matter whether I search on the left branch or right branch I always know I have a certain numbers of decisions.


session: S06-60
timestamp: 00:29:01.08
speaker: JAC
utterance:
I mean you could have done it so that two was here and then three's here and one is there and so on.


session: S06-60
timestamp: 00:29:54.05
speaker: JAC
utterance:
however, they can't see who's behind the person that's behind them because either that person is in the way or they're obscured in some way.


session: S06-60
timestamp: 00:32:40.22
speaker: JAC
utterance:
now the reason why we had +// we found out who Bob was pointing for +// pointing to Fred and then told Greg that +// to point to Fred is because if Bob pointed to Greg first now how we know who Bob was pointing to?


session: S06-60
timestamp: 00:33:00.00
speaker: JAC
utterance:
I have to save that so I have to tell Greg first so he can point there otherwise I'd lose Fred and the end of the line.


session: S06-60
timestamp: 00:33:10.15
speaker: JAC
utterance:
poor Fred won't be in line anymore so that's a problem and we might lose, you know, a hundred other people.


session: S06-60
timestamp: 00:33:32.13
speaker: JAC
utterance:
granted this line is really short and he didn't actually want to leave but hey maybe it's the wrong movie.


session: S06-60
timestamp: 00:34:26.10
speaker: JAC
utterance:
technically I can go who is behind +// I can ask them to ask them to ask them and so on so I could get to a certain point, right?


session: S06-60
timestamp: 00:35:12.12
speaker: JAC
utterance:
uh problem three is asking us to describe the sequence of operations to add list two to the end of list one.


session: S06-60
timestamp: 00:36:03.16
speaker: JAC
utterance:
so the first thing we're going to do is we need to find who is pointing to the end of the line in our first list.


session: S06-60
timestamp: 00:36:43.13
speaker: JAC
utterance:
(be)cause this is a correctly formed linked list we don't have to worry whether this is null or not because this should be null.


session: S06-60
timestamp: 00:36:59.15
speaker: JAC
utterance:
the head always points to the beginning of the line while this head is pointing to the middle of the line, right?


session: S06-60
timestamp: 00:37:18.10
speaker: JAC
utterance:
you could always we could have copied this entire link list and made a new link list and put it on there, right?


session: S06-60
timestamp: 00:37:33.00
speaker: JAC
utterance:
I'd rather this point to this and then this points to that and then just delete that formation, right?


session: S06-60
timestamp: 00:38:05.13
speaker: JAC
utterance:
so we search through this list here and find where it points to null and then have it point to b@l, right?


session: S06-60
timestamp: 00:38:21.16
speaker: JAC
utterance:
the only difference is that I have to keep going +// looking through each of these smaller internal nodes to find null, right?


session: S06-60
timestamp: 00:39:00.24
speaker: JAC
utterance:
I mean it's not too different from inserting just one node it's just that we have to go seaching through the entire link list to find # who's pointing to null.


