[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:07.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:07.00,0:00:12.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:12.00,0:00:15.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional
Dialogue: 0,0:00:15.00,0:00:25.00,Default,,0000,0000,0000,,Development.
Dialogue: 0,0:00:25.00,0:00:27.00,Default,,0000,0000,0000,,How are we doing?
Dialogue: 0,0:00:27.00,0:00:28.00,Default,,0000,0000,0000,,Spring apparently is here;
Dialogue: 0,0:00:28.00,0:00:33.00,Default,,0000,0000,0000,,just like California, one day it's winter, one day it's spring. Hopefully it's here to say.
Dialogue: 0,0:00:33.00,0:00:38.00,Default,,0000,0000,0000,,So we had talked about doing it, we did this last time, we did an unsorted vector
Dialogue: 0,0:00:38.00,0:00:40.00,Default,,0000,0000,0000,,implementation of the map, we just did a little struct of
Dialogue: 0,0:00:40.00,0:00:42.00,Default,,0000,0000,0000,,the key value pair.
Dialogue: 0,0:00:42.00,0:00:44.00,Default,,0000,0000,0000,,And then we went through
Dialogue: 0,0:00:44.00,0:00:48.00,Default,,0000,0000,0000,,that both add and get value are running at linear time in that form because of the need
Dialogue: 0,0:00:48.00,0:00:52.00,Default,,0000,0000,0000,,to search; search to find a value to override it, and search to find a value to
Dialogue: 0,0:00:52.00,0:00:54.00,Default,,0000,0000,0000,,pull out the existing
Dialogue: 0,0:00:54.00,0:00:55.00,Default,,0000,0000,0000,,match to it.
Dialogue: 0,0:00:55.00,0:00:58.00,Default,,0000,0000,0000,,And if we went to the sorted form of that, we could get get value to be able to
Dialogue: 0,0:00:58.00,0:01:02.00,Default,,0000,0000,0000,,capitalize on that binary search property and be able to quickly find the
Dialogue: 0,0:01:02.00,0:01:06.00,Default,,0000,0000,0000,,key if it exists in there or to determine it doesn't exist.
Dialogue: 0,0:01:06.00,0:01:09.00,Default,,0000,0000,0000,,But the add still suffered from the shuffling problem. We can quickly
Dialogue: 0,0:01:09.00,0:01:12.00,Default,,0000,0000,0000,,find, using the binary search to find where the
Dialogue: 0,0:01:12.00,0:01:15.00,Default,,0000,0000,0000,,new element would need to go. But if it doesn't already go there, it doesn't
Dialogue: 0,0:01:15.00,0:01:17.00,Default,,0000,0000,0000,,already exist. We're going to have to shuffle to make that space.
Dialogue: 0,0:01:17.00,0:01:21.00,Default,,0000,0000,0000,,So we have still a linear factor in there that we're working on getting rid of.
Dialogue: 0,0:01:21.00,0:01:24.00,Default,,0000,0000,0000,,And then I know at the bottom that none of them have any
Dialogue: 0,0:01:24.00,0:01:27.00,Default,,0000,0000,0000,,built in overhead per element. There may be some capacity, excess capacity in the
Dialogue: 0,0:01:27.00,0:01:30.00,Default,,0000,0000,0000,,vector that we're absorbing, but there's no
Dialogue: 0,0:01:30.00,0:01:33.00,Default,,0000,0000,0000,,four, ten, eight-byte chunk that every
Dialogue: 0,0:01:33.00,0:01:36.00,Default,,0000,0000,0000,,element is taking as a cost.
Dialogue: 0,0:01:36.00,0:01:39.00,Default,,0000,0000,0000,,So we started to talk about this at the end on Friday, and we're going to go with this and
Dialogue: 0,0:01:39.00,0:01:41.00,Default,,0000,0000,0000,,see where this takes
Dialogue: 0,0:01:41.00,0:01:45.00,Default,,0000,0000,0000,,us. We had the idea of the vector, and we know what vector constraints are, right? This
Dialogue: 0,0:01:45.00,0:01:48.00,Default,,0000,0000,0000,,idea of the contiguous memory, and we were going to think about the link list for a minute to
Dialogue: 0,0:01:48.00,0:01:51.00,Default,,0000,0000,0000,,see if it was going to buy us anything.
Dialogue: 0,0:01:51.00,0:01:54.00,Default,,0000,0000,0000,,It tends to have an inverse relationship, that once you know where you
Dialogue: 0,0:01:54.00,0:01:57.00,Default,,0000,0000,0000,,want to insert something it's easy to do that rearrangement because it's just a
Dialogue: 0,0:01:57.00,0:02:01.00,Default,,0000,0000,0000,,little bit of pointer rewiring that needs to happen in that situation.
Dialogue: 0,0:02:01.00,0:02:03.00,Default,,0000,0000,0000,,But it's hard to find a position insert,
Dialogue: 0,0:02:03.00,0:02:06.00,Default,,0000,0000,0000,,even if the link list is in sorted order,
Dialogue: 0,0:02:06.00,0:02:10.00,Default,,0000,0000,0000,,knowing where the S's are, or the M's are, or the B's are is still a
Dialogue: 0,0:02:10.00,0:02:13.00,Default,,0000,0000,0000,,matter of starting from the beginning; that your only access in the
Dialogue: 0,0:02:13.00,0:02:16.00,Default,,0000,0000,0000,,singly linked list is to start at the beginning and work your way down.
Dialogue: 0,0:02:16.00,0:02:20.00,Default,,0000,0000,0000,,And so I'm going to take you through a little bit of a thought exercise about well, what if
Dialogue: 0,0:02:20.00,0:02:23.00,Default,,0000,0000,0000,,we try to do something about that? Right now having a pointer coming into
Dialogue: 0,0:02:23.00,0:02:26.00,Default,,0000,0000,0000,,Bashful and then subsequent ones going in sorted order
Dialogue: 0,0:02:26.00,0:02:27.00,Default,,0000,0000,0000,,isn't really very helpful.
Dialogue: 0,0:02:27.00,0:02:30.00,Default,,0000,0000,0000,,But if we were willing to try to rearrange our pointers
Dialogue: 0,0:02:30.00,0:02:33.00,Default,,0000,0000,0000,,to give us the access that we have in the
Dialogue: 0,0:02:33.00,0:02:36.00,Default,,0000,0000,0000,,sorted array form; for example, if I had a pointer
Dialogue: 0,0:02:36.00,0:02:39.00,Default,,0000,0000,0000,,to the middlemost element, in
Dialogue: 0,0:02:39.00,0:02:42.00,Default,,0000,0000,0000,,this case the Grumpy that's
Dialogue: 0,0:02:42.00,0:02:43.00,Default,,0000,0000,0000,,midway down the list, if I had
Dialogue: 0,0:02:43.00,0:02:45.00,Default,,0000,0000,0000,,that pointer
Dialogue: 0,0:02:45.00,0:02:49.00,Default,,0000,0000,0000,,and from there I could say, is the element I'm looking for
Dialogue: 0,0:02:49.00,0:02:53.00,Default,,0000,0000,0000,,ahead of Grumpy or behind Grumpy. So having Grumpy split my input in
Dialogue: 0,0:02:53.00,0:02:54.00,Default,,0000,0000,0000,,half.
Dialogue: 0,0:02:54.00,0:02:56.00,Default,,0000,0000,0000,,If I had that, right, then that would actually get me
Dialogue: 0,0:02:56.00,0:02:59.00,Default,,0000,0000,0000,,sort of moving towards that direction that I wanted to get, which is using the binary
Dialogue: 0,0:02:59.00,0:03:03.00,Default,,0000,0000,0000,,search property to facilitate throwing away half the data
Dialogue: 0,0:03:03.00,0:03:06.00,Default,,0000,0000,0000,,and look into just the half remaining that's interesting.
Dialogue: 0,0:03:06.00,0:03:09.00,Default,,0000,0000,0000,,Well, if I had a pointer to Grumpy, that doesn't quite solve my problem. A pointer to Grumpy
Dialogue: 0,0:03:09.00,0:03:12.00,Default,,0000,0000,0000,,could get me halfway down the list, but then the pointer's coming in this way. If I
Dialogue: 0,0:03:12.00,0:03:16.00,Default,,0000,0000,0000,,inverted the pointers leading away from it,
Dialogue: 0,0:03:16.00,0:03:17.00,Default,,0000,0000,0000,,that's also kind of helping
Dialogue: 0,0:03:17.00,0:03:20.00,Default,,0000,0000,0000,,to facilitate what I'm trying to do. So if I could point toward the middle
Dialogue: 0,0:03:20.00,0:03:24.00,Default,,0000,0000,0000,,and then kind of move away, and then if I actually kind of applied the same strategy not just at the topmost
Dialogue: 0,0:03:24.00,0:03:28.00,Default,,0000,0000,0000,,level, but at every subsequent division down, from the half, to the
Dialogue: 0,0:03:28.00,0:03:29.00,Default,,0000,0000,0000,,quarter to the eight,
Dialogue: 0,0:03:29.00,0:03:32.00,Default,,0000,0000,0000,,to the sixteenth. And instead of having a pointer
Dialogue: 0,0:03:32.00,0:03:34.00,Default,,0000,0000,0000,,to the front of the list, what I really maintained was a pointer to the
Dialogue: 0,0:03:34.00,0:03:36.00,Default,,0000,0000,0000,,middlemost element, and then
Dialogue: 0,0:03:36.00,0:03:38.00,Default,,0000,0000,0000,,that element maintained pointers
Dialogue: 0,0:03:38.00,0:03:40.00,Default,,0000,0000,0000,,to the middle of the
Dialogue: 0,0:03:40.00,0:03:44.00,Default,,0000,0000,0000,,upper quarter and the middle of the lower quarter, and all the way down.
Dialogue: 0,0:03:44.00,0:03:46.00,Default,,0000,0000,0000,,Then I could pull up this list
Dialogue: 0,0:03:46.00,0:03:50.00,Default,,0000,0000,0000,,into something that we call a binary search tree.
Dialogue: 0,0:03:50.00,0:03:54.00,Default,,0000,0000,0000,,So the way I would be storing this is having a pointer to a node, which
Dialogue: 0,0:03:54.00,0:03:58.00,Default,,0000,0000,0000,,is expected to the median or the middle, or somewhere right along
Dialogue: 0,0:03:58.00,0:03:59.00,Default,,0000,0000,0000,,the
Dialogue: 0,0:03:59.00,0:04:00.00,Default,,0000,0000,0000,,values being stored.
Dialogue: 0,0:04:00.00,0:04:04.00,Default,,0000,0000,0000,,And that it has two pointers, not just a next or previous or something like that, that are related to all
Dialogue: 0,0:04:04.00,0:04:08.00,Default,,0000,0000,0000,,the elements that precede this one in the ordering, and all the elements that
Dialogue: 0,0:04:08.00,0:04:09.00,Default,,0000,0000,0000,,follow it are in
Dialogue: 0,0:04:09.00,0:04:11.00,Default,,0000,0000,0000,,these two pointers.
Dialogue: 0,0:04:11.00,0:04:14.00,Default,,0000,0000,0000,,They call these subtrees coming off the smaller trees over here with three
Dialogue: 0,0:04:14.00,0:04:17.00,Default,,0000,0000,0000,,elements on this side, and three elements on that side.
Dialogue: 0,0:04:17.00,0:04:19.00,Default,,0000,0000,0000,,And that each of those nodes
Dialogue: 0,0:04:19.00,0:04:22.00,Default,,0000,0000,0000,,has recursively the same formulation; that it has two
Dialogue: 0,0:04:22.00,0:04:25.00,Default,,0000,0000,0000,,subtree hanging off of it
Dialogue: 0,0:04:25.00,0:04:27.00,Default,,0000,0000,0000,,that contain,
Dialogue: 0,0:04:27.00,0:04:32.00,Default,,0000,0000,0000,,given any particular node, that there's this binary search ordering here that says
Dialogue: 0,0:04:32.00,0:04:36.00,Default,,0000,0000,0000,,everything that's in that left subtree precedes this node in ordering.
Dialogue: 0,0:04:36.00,0:04:38.00,Default,,0000,0000,0000,,And everything that's in that right subtree
Dialogue: 0,0:04:38.00,0:04:39.00,Default,,0000,0000,0000,,follows it.
Dialogue: 0,0:04:39.00,0:04:44.00,Default,,0000,0000,0000,,And that's true for every node throughout the entire arrangement here.
Dialogue: 0,0:04:44.00,0:04:47.00,Default,,0000,0000,0000,,So this is called a tree, and
Dialogue: 0,0:04:47.00,0:04:50.00,Default,,0000,0000,0000,,this particular form is actually called the binary search tree. I'm
Dialogue: 0,0:04:50.00,0:04:53.00,Default,,0000,0000,0000,,going to throw a little bit of vocabulary at you, because I'm going to start using these words, and I just want to get
Dialogue: 0,0:04:53.00,0:04:54.00,Default,,0000,0000,0000,,them out there
Dialogue: 0,0:04:54.00,0:04:58.00,Default,,0000,0000,0000,,early so that you understand what those words mean when I start using them.
Dialogue: 0,0:04:58.00,0:05:01.00,Default,,0000,0000,0000,,Is that each of the cells in here,
Dialogue: 0,0:05:01.00,0:05:02.00,Default,,0000,0000,0000,,like the cells that are
Dialogue: 0,0:05:02.00,0:05:04.00,Default,,0000,0000,0000,,allocated for a link list,
Dialogue: 0,0:05:04.00,0:05:07.00,Default,,0000,0000,0000,,are individually heap allocated, we're going to have pointers that allow us to get back
Dialogue: 0,0:05:07.00,0:05:08.00,Default,,0000,0000,0000,,to
Dialogue: 0,0:05:08.00,0:05:12.00,Default,,0000,0000,0000,,them. We typically call those nodes; in terms of tree I'll call it a cell or node in the list kind
Dialogue: 0,0:05:12.00,0:05:16.00,Default,,0000,0000,0000,,of interchangeably. I'm more likely to use node when I'm talking about tree.
Dialogue: 0,0:05:16.00,0:05:19.00,Default,,0000,0000,0000,,And a tree is really just a pointer to a node.
Dialogue: 0,0:05:19.00,0:05:21.00,Default,,0000,0000,0000,,The empty tree
Dialogue: 0,0:05:21.00,0:05:24.00,Default,,0000,0000,0000,,would be a pointer whose value is null, so pointing at nothing.
Dialogue: 0,0:05:24.00,0:05:27.00,Default,,0000,0000,0000,,A singleton tree would be a pointer to a single node
Dialogue: 0,0:05:27.00,0:05:29.00,Default,,0000,0000,0000,,that has left and right subtrees
Dialogue: 0,0:05:29.00,0:05:31.00,Default,,0000,0000,0000,,that are both empty or both null.
Dialogue: 0,0:05:31.00,0:05:35.00,Default,,0000,0000,0000,,So Bashful by itself is a singleton, a pointer to
Dialogue: 0,0:05:35.00,0:05:38.00,Default,,0000,0000,0000,,Bashful. When we talk about subtrees, it just kind of means looking at the top; Grumpy has two
Dialogue: 0,0:05:38.00,0:05:40.00,Default,,0000,0000,0000,,subtrees, a left and a right,
Dialogue: 0,0:05:40.00,0:05:41.00,Default,,0000,0000,0000,,
Dialogue: 0,0:05:41.00,0:05:42.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:05:42.00,0:05:45.00,Default,,0000,0000,0000,,themselves are just smaller forms of the same recursive structure.
Dialogue: 0,0:05:45.00,0:05:49.00,Default,,0000,0000,0000,,And then we would say that Grumpy is the parent of Doc and Sleepy.
Dialogue: 0,0:05:49.00,0:05:52.00,Default,,0000,0000,0000,,So those are the two children nodes, and we'll call them the left child and the right
Dialogue: 0,0:05:52.00,0:05:53.00,Default,,0000,0000,0000,,child.
Dialogue: 0,0:05:53.00,0:05:56.00,Default,,0000,0000,0000,,And the node that's at the very top,
Dialogue: 0,0:05:56.00,0:06:00.00,Default,,0000,0000,0000,,the one that our external pointer is coming into and then kind of leads the way, is called
Dialogue: 0,0:06:00.00,0:06:02.00,Default,,0000,0000,0000,,the root node. The
Dialogue: 0,0:06:02.00,0:06:02.00,Default,,0000,0000,0000,,first node
Dialogue: 0,0:06:02.00,0:06:05.00,Default,,0000,0000,0000,,of the tree where we first start our work is going to be called the root.
Dialogue: 0,0:06:05.00,0:06:09.00,Default,,0000,0000,0000,,And these nodes down here at the bottom that have empty subtrees are called leaf nodes.
Dialogue: 0,0:06:09.00,0:06:14.00,Default,,0000,0000,0000,,So a node that has no further subtrees, so by itself has null
Dialogue: 0,0:06:14.00,0:06:16.00,Default,,0000,0000,0000,,left and right trees, is called a leaf.
Dialogue: 0,0:06:16.00,0:06:18.00,Default,,0000,0000,0000,,So that actually means the tree is kind of upside down
Dialogue: 0,0:06:18.00,0:06:21.00,Default,,0000,0000,0000,,if you look at it. That Grumpy's the root and these things are the
Dialogue: 0,0:06:21.00,0:06:25.00,Default,,0000,0000,0000,,leaves shows you that apparently most computer scientists don't get out very much,
Dialogue: 0,0:06:25.00,0:06:28.00,Default,,0000,0000,0000,,because they haven't noticed that trees actually grow the other direction.
Dialogue: 0,0:06:28.00,0:06:29.00,Default,,0000,0000,0000,,
Dialogue: 0,0:06:29.00,0:06:32.00,Default,,0000,0000,0000,,But just kind of go with it, and
Dialogue: 0,0:06:32.00,0:06:33.00,Default,,0000,0000,0000,,you'll be
Dialogue: 0,0:06:33.00,0:06:36.00,Default,,0000,0000,0000,,speaking tree-speak in no time.
Dialogue: 0,0:06:36.00,0:06:43.00,Default,,0000,0000,0000,,Anybody have any questions about what we've got basically set up here?
Dialogue: 0,0:06:43.00,0:06:45.00,Default,,0000,0000,0000,,So there is a
Dialogue: 0,0:06:45.00,0:06:48.00,Default,,0000,0000,0000,,whole family of things that come under the heading of tree in computer
Dialogue: 0,0:06:48.00,0:06:52.00,Default,,0000,0000,0000,,science. We're going to look in particular at this one embodiment, the binary search
Dialogue: 0,0:06:52.00,0:06:53.00,Default,,0000,0000,0000,,tree.
Dialogue: 0,0:06:53.00,0:06:56.00,Default,,0000,0000,0000,,But before I get deep down in the details of that, I just want to back
Dialogue: 0,0:06:56.00,0:06:59.00,Default,,0000,0000,0000,,up for a second and just talk about what trees in general mean, and what kind of
Dialogue: 0,0:06:59.00,0:07:01.00,Default,,0000,0000,0000,,things in general are represented in manipulative trees.
Dialogue: 0,0:07:01.00,0:07:06.00,Default,,0000,0000,0000,,So that you have a sense of what is the broad notion of tree as a
Dialogue: 0,0:07:06.00,0:07:08.00,Default,,0000,0000,0000,,computer scientist would see it,
Dialogue: 0,0:07:08.00,0:07:10.00,Default,,0000,0000,0000,,is just that a tree is a recursive branching structure
Dialogue: 0,0:07:10.00,0:07:14.00,Default,,0000,0000,0000,,where there are nodes, which have pointers to subtrees.
Dialogue: 0,0:07:14.00,0:07:17.00,Default,,0000,0000,0000,,There may be one of those subtrees. There may be ten of those subtrees. There
Dialogue: 0,0:07:17.00,0:07:20.00,Default,,0000,0000,0000,,may be two; depending on the nature of the tree you're working on there may be a
Dialogue: 0,0:07:20.00,0:07:22.00,Default,,0000,0000,0000,,constraint on exactly how many children they have
Dialogue: 0,0:07:22.00,0:07:26.00,Default,,0000,0000,0000,,or some flexibility in the number of children they have
Dialogue: 0,0:07:26.00,0:07:27.00,Default,,0000,0000,0000,,
Dialogue: 0,0:07:27.00,0:07:29.00,Default,,0000,0000,0000,,depending on what's being modeled here.
Dialogue: 0,0:07:29.00,0:07:31.00,Default,,0000,0000,0000,,There's always a single root node.
Dialogue: 0,0:07:31.00,0:07:35.00,Default,,0000,0000,0000,,There's a node that kind of sits at the top of this hierarchy that leads down to
Dialogue: 0,0:07:35.00,0:07:36.00,Default,,0000,0000,0000,,these things,
Dialogue: 0,0:07:36.00,0:07:41.00,Default,,0000,0000,0000,,and that to form a tree there has to be a reachable path from the root
Dialogue: 0,0:07:41.00,0:07:43.00,Default,,0000,0000,0000,,to every single node.
Dialogue: 0,0:07:43.00,0:07:46.00,Default,,0000,0000,0000,,So there aren't some nodes that exist way out here, and there aren't two different ways to
Dialogue: 0,0:07:46.00,0:07:48.00,Default,,0000,0000,0000,,get to the same
Dialogue: 0,0:07:48.00,0:07:50.00,Default,,0000,0000,0000,,node in a tree; that if the
Dialogue: 0,0:07:50.00,0:07:53.00,Default,,0000,0000,0000,,midterm is kept in the folder called exams, which is in the folder
Dialogue: 0,0:07:53.00,0:07:56.00,Default,,0000,0000,0000,,called cs106, which is in my home folder. There's not some other way that
Dialogue: 0,0:07:56.00,0:07:59.00,Default,,0000,0000,0000,,you can get to the midterm; the midterm lives exactly that part in the tree,
Dialogue: 0,0:07:59.00,0:08:01.00,Default,,0000,0000,0000,,and there's no
Dialogue: 0,0:08:01.00,0:08:04.00,Default,,0000,0000,0000,,circularity or loops in the structure.
Dialogue: 0,0:08:04.00,0:08:07.00,Default,,0000,0000,0000,,And so a lot of things do get modeled tree, the one I've drawn here is just the file system.
Dialogue: 0,0:08:07.00,0:08:10.00,Default,,0000,0000,0000,,Think about how your files are maintained on a computer, there tends to be a
Dialogue: 0,0:08:10.00,0:08:11.00,Default,,0000,0000,0000,,structure of an
Dialogue: 0,0:08:11.00,0:08:14.00,Default,,0000,0000,0000,,outermost folder, which has inner folders,
Dialogue: 0,0:08:14.00,0:08:17.00,Default,,0000,0000,0000,,which have inner folders. And along the way there are these files, which you can think of as leaf
Dialogue: 0,0:08:17.00,0:08:21.00,Default,,0000,0000,0000,,nodes that have no further subtrees underneath them.
Dialogue: 0,0:08:21.00,0:08:24.00,Default,,0000,0000,0000,,And you can talk about, say, what is the size of
Dialogue: 0,0:08:24.00,0:08:27.00,Default,,0000,0000,0000,,all the folders in my home directory? Well it would kind
Dialogue: 0,0:08:27.00,0:08:28.00,Default,,0000,0000,0000,,of be recursively defined as summing over
Dialogue: 0,0:08:28.00,0:08:30.00,Default,,0000,0000,0000,,all the folders within it,
Dialogue: 0,0:08:30.00,0:08:33.00,Default,,0000,0000,0000,,how much storage is being used by those; which when it gets down to a leaf node can say, how
Dialogue: 0,0:08:33.00,0:08:38.00,Default,,0000,0000,0000,,much space does this file take up and kind of add those together.
Dialogue: 0,0:08:38.00,0:08:42.00,Default,,0000,0000,0000,,Things like your family trees, right, sort of modeling genealogy.
Dialogue: 0,0:08:42.00,0:08:44.00,Default,,0000,0000,0000,,Things like the decomposition tree in your program;
Dialogue: 0,0:08:44.00,0:08:47.00,Default,,0000,0000,0000,,main calling,
Dialogue: 0,0:08:47.00,0:08:50.00,Default,,0000,0000,0000,,read file calling, set up boggle board calling,
Dialogue: 0,0:08:50.00,0:08:52.00,Default,,0000,0000,0000,,give instructions.
Dialogue: 0,0:08:52.00,0:08:56.00,Default,,0000,0000,0000,,There is a tree structure to that, about what pieces use what pieces and
Dialogue: 0,0:08:56.00,0:08:57.00,Default,,0000,0000,0000,,descendants from there.
Dialogue: 0,0:08:57.00,0:09:01.00,Default,,0000,0000,0000,,The ones that we're going to look at in particularly are the ones that are in the family of the binary trees. So a binary
Dialogue: 0,0:09:01.00,0:09:05.00,Default,,0000,0000,0000,,tree has two children, exactly two children. There's a left and a right
Dialogue: 0,0:09:05.00,0:09:07.00,Default,,0000,0000,0000,,pointer coming out of each node.
Dialogue: 0,0:09:07.00,0:09:11.00,Default,,0000,0000,0000,,One or both of those can be null, but there can never be more than two
Dialogue: 0,0:09:11.00,0:09:11.00,Default,,0000,0000,0000,,children.
Dialogue: 0,0:09:11.00,0:09:15.00,Default,,0000,0000,0000,,And there is sort of space for recording two children, as opposed to recording things which
Dialogue: 0,0:09:15.00,0:09:17.00,Default,,0000,0000,0000,,are trinary, which have three
Dialogue: 0,0:09:17.00,0:09:20.00,Default,,0000,0000,0000,,possibilities for children, or where there may be some four or eight or
Dialogue: 0,0:09:20.00,0:09:22.00,Default,,0000,0000,0000,,some other number there.
Dialogue: 0,0:09:22.00,0:09:24.00,Default,,0000,0000,0000,,And in particular it's the search tree
Dialogue: 0,0:09:24.00,0:09:26.00,Default,,0000,0000,0000,,that's going to help us get
Dialogue: 0,0:09:26.00,0:09:28.00,Default,,0000,0000,0000,,the work done that we want, which is
Dialogue: 0,0:09:28.00,0:09:32.00,Default,,0000,0000,0000,,there's not just any old arrangement of what's on the left, and what's on the right side.
Dialogue: 0,0:09:32.00,0:09:35.00,Default,,0000,0000,0000,,That the nodes are going to be organized in here to facilitate binary search by
Dialogue: 0,0:09:35.00,0:09:36.00,Default,,0000,0000,0000,,keeping
Dialogue: 0,0:09:36.00,0:09:37.00,Default,,0000,0000,0000,,one half
Dialogue: 0,0:09:37.00,0:09:40.00,Default,,0000,0000,0000,,over on the left and one half over on the right, and that we'll know which
Dialogue: 0,0:09:40.00,0:09:44.00,Default,,0000,0000,0000,,half something goes in by virtue of looking at the key. So
Dialogue: 0,0:09:44.00,0:09:47.00,Default,,0000,0000,0000,,let's take a look at a simple example of a binary search tree with
Dialogue: 0,0:09:47.00,0:09:49.00,Default,,0000,0000,0000,,numbers. So
Dialogue: 0,0:09:49.00,0:09:53.00,Default,,0000,0000,0000,,if I have a struct node that keeps track of an integer value and has two pointers, the
Dialogue: 0,0:09:53.00,0:09:55.00,Default,,0000,0000,0000,,left and the right,
Dialogue: 0,0:09:55.00,0:09:59.00,Default,,0000,0000,0000,,that point away from it. And in this case my root node is 57,
Dialogue: 0,0:09:59.00,0:10:03.00,Default,,0000,0000,0000,,and looking at 57 I can tell you that every value in this tree
Dialogue: 0,0:10:03.00,0:10:07.00,Default,,0000,0000,0000,,that is less than 57 will be in the left subtree. There will be no values
Dialogue: 0,0:10:07.00,0:10:09.00,Default,,0000,0000,0000,,that are 56 or lower that are on the
Dialogue: 0,0:10:09.00,0:10:10.00,Default,,0000,0000,0000,,right side.
Dialogue: 0,0:10:10.00,0:10:14.00,Default,,0000,0000,0000,,And that will be true at every step down the tree. So if I'm looking for
Dialogue: 0,0:10:14.00,0:10:15.00,Default,,0000,0000,0000,,something
Dialogue: 0,0:10:15.00,0:10:18.00,Default,,0000,0000,0000,,that actually gives me that immediate access we were using the vector's
Dialogue: 0,0:10:18.00,0:10:19.00,Default,,0000,0000,0000,,sorting property for. Which is if
Dialogue: 0,0:10:19.00,0:10:24.00,Default,,0000,0000,0000,,I'm looking for the number 70, and I start at the root node of 57, then I know
Dialogue: 0,0:10:24.00,0:10:25.00,Default,,0000,0000,0000,,it's not in the left subtree,
Dialogue: 0,0:10:25.00,0:10:28.00,Default,,0000,0000,0000,,so assuming that about half the nodes are
Dialogue: 0,0:10:28.00,0:10:30.00,Default,,0000,0000,0000,,pointed to over on that side,
Dialogue: 0,0:10:30.00,0:10:34.00,Default,,0000,0000,0000,,I've now discarded half of the input even from consideration. If
Dialogue: 0,0:10:34.00,0:10:36.00,Default,,0000,0000,0000,,I start at the 70,
Dialogue: 0,0:10:36.00,0:10:39.00,Default,,0000,0000,0000,,and I say okay well if 57 must be over here, then again recursively apply the
Dialogue: 0,0:10:39.00,0:10:44.00,Default,,0000,0000,0000,,same search property here. It's like if I'm looking for 70, is it going to be
Dialogue: 0,0:10:44.00,0:10:45.00,Default,,0000,0000,0000,,before or after 79?
Dialogue: 0,0:10:45.00,0:10:49.00,Default,,0000,0000,0000,,It's going to be before, so in fact I throw away anything that leads away on
Dialogue: 0,0:10:49.00,0:10:52.00,Default,,0000,0000,0000,,the right subtree of 79, and work my way one level down.
Dialogue: 0,0:10:52.00,0:10:53.00,Default,,0000,0000,0000,,So each step
Dialogue: 0,0:10:53.00,0:10:58.00,Default,,0000,0000,0000,,in the recursive search is represented by sort of taking a step down
Dialogue: 0,0:10:58.00,0:11:02.00,Default,,0000,0000,0000,,in that search tree; working my way down from the root to the leaf nodes. And
Dialogue: 0,0:11:02.00,0:11:05.00,Default,,0000,0000,0000,,I either will find the value I'm looking for along the way,
Dialogue: 0,0:11:05.00,0:11:08.00,Default,,0000,0000,0000,,or I will fall off the bottom of that tree
Dialogue: 0,0:11:08.00,0:11:10.00,Default,,0000,0000,0000,,when I haven't been able to find it.
Dialogue: 0,0:11:10.00,0:11:13.00,Default,,0000,0000,0000,,And that will tell me; oh it couldn't have been in the tree, because the only place
Dialogue: 0,0:11:13.00,0:11:16.00,Default,,0000,0000,0000,,it could have been is the one that followed the binary search property.
Dialogue: 0,0:11:16.00,0:11:19.00,Default,,0000,0000,0000,,And so if I look for 70, I say is it greater or less than
Dialogue: 0,0:11:19.00,0:11:21.00,Default,,0000,0000,0000,,62? It's greater. Is it
Dialogue: 0,0:11:21.00,0:11:24.00,Default,,0000,0000,0000,,greater or less than 71? It's less then. And then I work off there I get to the empty
Dialogue: 0,0:11:24.00,0:11:26.00,Default,,0000,0000,0000,,tree. Then I say well if there was a 60, that's where it was
Dialogue: 0,0:11:26.00,0:11:31.00,Default,,0000,0000,0000,,going to be, and it wasn't there so there much not be a 70 in this tree.
Dialogue: 0,0:11:31.00,0:11:32.00,Default,,0000,0000,0000,,So it is exactly designed
Dialogue: 0,0:11:32.00,0:11:36.00,Default,,0000,0000,0000,,to support one kind of search, and one kind of search only, which is this
Dialogue: 0,0:11:36.00,0:11:40.00,Default,,0000,0000,0000,,efficient divide and conquer binary search, work its way down.
Dialogue: 0,0:11:40.00,0:11:40.00,Default,,0000,0000,0000,,
Dialogue: 0,0:11:40.00,0:11:42.00,Default,,0000,0000,0000,,The other kinds of things, let's say, that
Dialogue: 0,0:11:42.00,0:11:44.00,Default,,0000,0000,0000,,trees
Dialogue: 0,0:11:44.00,0:11:45.00,Default,,0000,0000,0000,,are used for
Dialogue: 0,0:11:45.00,0:11:48.00,Default,,0000,0000,0000,,may not need this kind of support, so they may not go out of their way to do this. But the one
Dialogue: 0,0:11:48.00,0:11:52.00,Default,,0000,0000,0000,,we're actually very interested in is because of maps doing a lot of
Dialogue: 0,0:11:52.00,0:11:55.00,Default,,0000,0000,0000,,additions into a sorted facility and
Dialogue: 0,0:11:55.00,0:11:57.00,Default,,0000,0000,0000,,searches in that sort of facility. If we can
Dialogue: 0,0:11:57.00,0:12:00.00,Default,,0000,0000,0000,,bottle it as a binary search tree, we're able to get the best of both worlds. To
Dialogue: 0,0:12:00.00,0:12:03.00,Default,,0000,0000,0000,,have that super fast logarithmic search,
Dialogue: 0,0:12:03.00,0:12:07.00,Default,,0000,0000,0000,,as well as have the flexibility of the pointer based structure
Dialogue: 0,0:12:07.00,0:12:11.00,Default,,0000,0000,0000,,to help us do an insert. So if I'm ready to put a 70 into this tree,
Dialogue: 0,0:12:11.00,0:12:14.00,Default,,0000,0000,0000,,the same path that led to me to where it should be
Dialogue: 0,0:12:14.00,0:12:16.00,Default,,0000,0000,0000,,tells us where to put that new node
Dialogue: 0,0:12:16.00,0:12:20.00,Default,,0000,0000,0000,,in place. And if all I need to do is to wire that in place; and if all I need to do to wire that in place is to kind of create a new node in the
Dialogue: 0,0:12:20.00,0:12:21.00,Default,,0000,0000,0000,,heap and
Dialogue: 0,0:12:21.00,0:12:24.00,Default,,0000,0000,0000,,put the pointers coming in and out of it the way that I would in a link list,
Dialogue: 0,0:12:24.00,0:12:27.00,Default,,0000,0000,0000,,then I should be able to do both searches and inserts
Dialogue: 0,0:12:27.00,0:12:30.00,Default,,0000,0000,0000,,in time proportional to the height of the tree,
Dialogue: 0,0:12:30.00,0:12:35.00,Default,,0000,0000,0000,,which for a relatively balanced tree would be logarithmic. So
Dialogue: 0,0:12:35.00,0:12:37.00,Default,,0000,0000,0000,,it sounds like we can get everything we wanted here
Dialogue: 0,0:12:37.00,0:12:40.00,Default,,0000,0000,0000,,with a little bit of work. So
Dialogue: 0,0:12:40.00,0:12:43.00,Default,,0000,0000,0000,,let me tell you - just do a little bit of playing with trees, just to kind of get used to thinking
Dialogue: 0,0:12:43.00,0:12:46.00,Default,,0000,0000,0000,,about how we do stuff on them, and then I'm going to go forward with
Dialogue: 0,0:12:46.00,0:12:49.00,Default,,0000,0000,0000,,implementing map using a binary search tree.
Dialogue: 0,0:12:49.00,0:12:52.00,Default,,0000,0000,0000,,Trees are very, very recursive. So for those of you who still feel like
Dialogue: 0,0:12:52.00,0:12:54.00,Default,,0000,0000,0000,,recursion is a little bit hazy,
Dialogue: 0,0:12:54.00,0:12:58.00,Default,,0000,0000,0000,,this is another great area to strengthen your thinking about
Dialogue: 0,0:12:58.00,0:13:01.00,Default,,0000,0000,0000,,recursive. In fact, I think a lot of people find operating on trees very, very
Dialogue: 0,0:13:01.00,0:13:03.00,Default,,0000,0000,0000,,natural. Because trees are so recursive, the
Dialogue: 0,0:13:03.00,0:13:07.00,Default,,0000,0000,0000,,idea that you write recursive algorithms to them is almost like you do it without even thinking, you don't
Dialogue: 0,0:13:07.00,0:13:08.00,Default,,0000,0000,0000,,have to think hard. You're like,
Dialogue: 0,0:13:08.00,0:13:11.00,Default,,0000,0000,0000,,you typically need to do something to your current node,
Dialogue: 0,0:13:11.00,0:13:14.00,Default,,0000,0000,0000,,and then recursively operate on your left and your right.
Dialogue: 0,0:13:14.00,0:13:17.00,Default,,0000,0000,0000,,And it's so natural that you don't even have stop and think hard about
Dialogue: 0,0:13:17.00,0:13:18.00,Default,,0000,0000,0000,,what that means. So
Dialogue: 0,0:13:18.00,0:13:21.00,Default,,0000,0000,0000,,your base case tends to be getting to an empty tree and having a
Dialogue: 0,0:13:21.00,0:13:23.00,Default,,0000,0000,0000,,pointer that points to null,
Dialogue: 0,0:13:23.00,0:13:28.00,Default,,0000,0000,0000,,and in the other cases have some node operate on your children.
Dialogue: 0,0:13:28.00,0:13:31.00,Default,,0000,0000,0000,,Some of the simplest things are just traversals.
Dialogue: 0,0:13:31.00,0:13:33.00,Default,,0000,0000,0000,,If I tree structure and I'd like to
Dialogue: 0,0:13:33.00,0:13:35.00,Default,,0000,0000,0000,,do something to every node,
Dialogue: 0,0:13:35.00,0:13:37.00,Default,,0000,0000,0000,,go through it and print them all,
Dialogue: 0,0:13:37.00,0:13:39.00,Default,,0000,0000,0000,,go through it and write them to a file,
Dialogue: 0,0:13:39.00,0:13:42.00,Default,,0000,0000,0000,,go through and add them all up to determine the average score, I
Dialogue: 0,0:13:42.00,0:13:46.00,Default,,0000,0000,0000,,need these things. I'm going to need to do some processing that visits every node of the
Dialogue: 0,0:13:46.00,0:13:48.00,Default,,0000,0000,0000,,tree once and exactly once,
Dialogue: 0,0:13:48.00,0:13:50.00,Default,,0000,0000,0000,,and recursion is exactly the way to do that.
Dialogue: 0,0:13:50.00,0:13:53.00,Default,,0000,0000,0000,,And there's a little bit of some choices, and when you're handling a
Dialogue: 0,0:13:53.00,0:13:55.00,Default,,0000,0000,0000,,particular part of a tree, are you handling the current node and then
Dialogue: 0,0:13:55.00,0:13:59.00,Default,,0000,0000,0000,,recurring on the left and right subtrees? Are you recurring first and then handling
Dialogue: 0,0:13:59.00,0:14:02.00,Default,,0000,0000,0000,,the nodes. So some of those things that we saw in terms of the link list
Dialogue: 0,0:14:02.00,0:14:03.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:14:03.00,0:14:06.00,Default,,0000,0000,0000,,change the order of the processing, but they don't change
Dialogue: 0,0:14:06.00,0:14:08.00,Default,,0000,0000,0000,,whether you visit everybody. It's just a matter of which one you want to do
Dialogue: 0,0:14:08.00,0:14:09.00,Default,,0000,0000,0000,,before.
Dialogue: 0,0:14:09.00,0:14:12.00,Default,,0000,0000,0000,,I'm going to look at a couple of the simple traversals here,
Dialogue: 0,0:14:12.00,0:14:14.00,Default,,0000,0000,0000,,and I'll point out
Dialogue: 0,0:14:14.00,0:14:16.00,Default,,0000,0000,0000,,why that mattered.
Dialogue: 0,0:14:16.00,0:14:18.00,Default,,0000,0000,0000,,If we look at in order,
Dialogue: 0,0:14:18.00,0:14:22.00,Default,,0000,0000,0000,,so we'll consider that an in order traversal is for you to operate on your
Dialogue: 0,0:14:22.00,0:14:24.00,Default,,0000,0000,0000,,left subtree recursively,
Dialogue: 0,0:14:24.00,0:14:27.00,Default,,0000,0000,0000,,handle the current node right here, and then operate on your right subtree
Dialogue: 0,0:14:27.00,0:14:29.00,Default,,0000,0000,0000,,recursively.
Dialogue: 0,0:14:29.00,0:14:31.00,Default,,0000,0000,0000,,The base case, which is
Dialogue: 0,0:14:31.00,0:14:34.00,Default,,0000,0000,0000,,kind of hidden in here, is if T is null, we get to an empty subtree we
Dialogue: 0,0:14:34.00,0:14:37.00,Default,,0000,0000,0000,,don't do anything. So only in the nonempty case are we actually
Dialogue: 0,0:14:37.00,0:14:39.00,Default,,0000,0000,0000,,processing and making recursive calls.
Dialogue: 0,0:14:39.00,0:14:43.00,Default,,0000,0000,0000,,So if I start with my node 57 being the root of my tree, and I say
Dialogue: 0,0:14:43.00,0:14:45.00,Default,,0000,0000,0000,,print that tree starting from the root.
Dialogue: 0,0:14:45.00,0:14:48.00,Default,,0000,0000,0000,,It will print everything out of the left subtree,
Dialogue: 0,0:14:48.00,0:14:52.00,Default,,0000,0000,0000,,then print the 57, and then print everything out of the right subtree.
Dialogue: 0,0:14:52.00,0:14:55.00,Default,,0000,0000,0000,,And given that gets applied everywhere down,
Dialogue: 0,0:14:55.00,0:14:58.00,Default,,0000,0000,0000,,the effect will be 57 says first print my left subtree.
Dialogue: 0,0:14:58.00,0:15:01.00,Default,,0000,0000,0000,,And 37 says, well print my left subtree. And 15 says, well first
Dialogue: 0,0:15:01.00,0:15:03.00,Default,,0000,0000,0000,,print my left subtree.
Dialogue: 0,0:15:03.00,0:15:06.00,Default,,0000,0000,0000,,And then seven says, first print my left subtree. Well, that ones empty,
Dialogue: 0,0:15:06.00,0:15:09.00,Default,,0000,0000,0000,,and so nothing gets printed.
Dialogue: 0,0:15:09.00,0:15:13.00,Default,,0000,0000,0000,,As the recursion unwinds, it comes back to the last most call. The last most call was
Dialogue: 0,0:15:13.00,0:15:17.00,Default,,0000,0000,0000,,seven. It says, okay, print seven and now print seven's right subtree. Again that's an empty,
Dialogue: 0,0:15:17.00,0:15:19.00,Default,,0000,0000,0000,,so nothing gets printed there. It
Dialogue: 0,0:15:19.00,0:15:22.00,Default,,0000,0000,0000,,will come back and then do the same thing with 15. I've done everything
Dialogue: 0,0:15:22.00,0:15:23.00,Default,,0000,0000,0000,,to the left of 15;
Dialogue: 0,0:15:23.00,0:15:26.00,Default,,0000,0000,0000,,let's print 15 and its right.
Dialogue: 0,0:15:26.00,0:15:29.00,Default,,0000,0000,0000,,And doing that kind of all the way throughout the tree means that we will get the numbers out
Dialogue: 0,0:15:29.00,0:15:31.00,Default,,0000,0000,0000,,in sorted order;
Dialogue: 0,0:15:31.00,0:15:34.00,Default,,0000,0000,0000,,all right, five, 17, seven,
Dialogue: 0,0:15:34.00,0:15:37.00,Default,,0000,0000,0000,,15, 32, 57, 59, 62, 71,
Dialogue: 0,0:15:37.00,0:15:40.00,Default,,0000,0000,0000,,79, 93. An in order traversal
Dialogue: 0,0:15:40.00,0:15:42.00,Default,,0000,0000,0000,,in a binary search tree
Dialogue: 0,0:15:42.00,0:15:50.00,Default,,0000,0000,0000,,rediscovers, visits all the nodes from smallest to largest. [Inaudible]
Dialogue: 0,0:15:50.00,0:15:54.00,Default,,0000,0000,0000,,So duplicates, you just have to have a strategy. It turns out in the map, the duplicates
Dialogue: 0,0:15:54.00,0:15:54.00,Default,,0000,0000,0000,,overwrite.
Dialogue: 0,0:15:54.00,0:15:58.00,Default,,0000,0000,0000,,So any time you get a new value you print there. Typically you just need to decide,
Dialogue: 0,0:15:58.00,0:16:00.00,Default,,0000,0000,0000,,do they go to the left or do they go to the right?
Dialogue: 0,0:16:00.00,0:16:03.00,Default,,0000,0000,0000,,So that you know when you're equal to if you wanted to find another one
Dialogue: 0,0:16:03.00,0:16:04.00,Default,,0000,0000,0000,,of these, where would it go?
Dialogue: 0,0:16:04.00,0:16:07.00,Default,,0000,0000,0000,,In a lot of situations you just don't have duplicates, so it's not actually a big deal.
Dialogue: 0,0:16:07.00,0:16:10.00,Default,,0000,0000,0000,,You can't throw them arbitrarily on either side because you would end up having to search
Dialogue: 0,0:16:10.00,0:16:14.00,Default,,0000,0000,0000,,both sides to find them. So you want to just know that's it's less than or equal to on the
Dialogue: 0,0:16:14.00,0:16:18.00,Default,,0000,0000,0000,,left and greater than on the right. So that's
Dialogue: 0,0:16:18.00,0:16:22.00,Default,,0000,0000,0000,,pretty neat, right, that that means that this
Dialogue: 0,0:16:22.00,0:16:22.00,Default,,0000,0000,0000,,
Dialogue: 0,0:16:22.00,0:16:25.00,Default,,0000,0000,0000,,for purposes of being able to iterate for something, if
Dialogue: 0,0:16:25.00,0:16:26.00,Default,,0000,0000,0000,,you were to walk
Dialogue: 0,0:16:26.00,0:16:30.00,Default,,0000,0000,0000,,the structure in order, then you can produce them back out in sorted order, which tends to be
Dialogue: 0,0:16:30.00,0:16:31.00,Default,,0000,0000,0000,,a convenient way
Dialogue: 0,0:16:31.00,0:16:33.00,Default,,0000,0000,0000,,
Dialogue: 0,0:16:33.00,0:16:36.00,Default,,0000,0000,0000,,to print the output. There are a lot of situations where you do want that browsable
Dialogue: 0,0:16:36.00,0:16:43.00,Default,,0000,0000,0000,,list in alphanumerical order. And the tree makes that easy to do.
Dialogue: 0,0:16:43.00,0:16:45.00,Default,,0000,0000,0000,,When it comes time to delete the tree, I'm
Dialogue: 0,0:16:45.00,0:16:48.00,Default,,0000,0000,0000,,going to need to go through and delete each of those nodes individually, the
Dialogue: 0,0:16:48.00,0:16:51.00,Default,,0000,0000,0000,,same way I would on a link list to delete the whole structure.
Dialogue: 0,0:16:51.00,0:16:54.00,Default,,0000,0000,0000,,The
Dialogue: 0,0:16:54.00,0:16:57.00,Default,,0000,0000,0000,,order of traversal that's going to be most convenient for doing that is going to be to do it
Dialogue: 0,0:16:57.00,0:16:58.00,Default,,0000,0000,0000,,post order.
Dialogue: 0,0:16:58.00,0:17:00.00,Default,,0000,0000,0000,,Which is to say, when I'm looking at the root node 57,
Dialogue: 0,0:17:00.00,0:17:05.00,Default,,0000,0000,0000,,I want to delete my entire left subtree recursively, delete my entire right
Dialogue: 0,0:17:05.00,0:17:10.00,Default,,0000,0000,0000,,subtree recursively, and only after both of those pieces have been cleaned up,
Dialogue: 0,0:17:10.00,0:17:12.00,Default,,0000,0000,0000,,delete the node we're on;
Dialogue: 0,0:17:12.00,0:17:14.00,Default,,0000,0000,0000,,so deleting down below to the left, down below to the right
Dialogue: 0,0:17:14.00,0:17:17.00,Default,,0000,0000,0000,,and then delete this one. If I did it in the other order, if
Dialogue: 0,0:17:17.00,0:17:21.00,Default,,0000,0000,0000,,I tried to delete in between in the in order or in the pre order case where I did
Dialogue: 0,0:17:21.00,0:17:23.00,Default,,0000,0000,0000,,my node and then to my subtrees,
Dialogue: 0,0:17:23.00,0:17:26.00,Default,,0000,0000,0000,,I'd be reaching into parts of my memory I've deleted.
Dialogue: 0,0:17:26.00,0:17:31.00,Default,,0000,0000,0000,,So we do want to do it in that order, so
Dialogue: 0,0:17:31.00,0:17:32.00,Default,,0000,0000,0000,,recursion
Dialogue: 0,0:17:32.00,0:17:35.00,Default,,0000,0000,0000,,coming back to visit you again.
Dialogue: 0,0:17:35.00,0:17:42.00,Default,,0000,0000,0000,,Let's talk about how to make map work as a tree.
Dialogue: 0,0:17:42.00,0:17:46.00,Default,,0000,0000,0000,,So if you think about what maps hold, maps hold a key, which is string type; a
Dialogue: 0,0:17:46.00,0:17:48.00,Default,,0000,0000,0000,,value, which is client
Dialogue: 0,0:17:48.00,0:17:51.00,Default,,0000,0000,0000,,some sort of template parameter there.
Dialogue: 0,0:17:51.00,0:17:55.00,Default,,0000,0000,0000,,Now that I've built a structure that raps those two things with a pair and
Dialogue: 0,0:17:55.00,0:17:58.00,Default,,0000,0000,0000,,adds to it, right these two additional pointers to the left and to the right
Dialogue: 0,0:17:58.00,0:18:01.00,Default,,0000,0000,0000,,subtrees that point back to a recursive struct,
Dialogue: 0,0:18:01.00,0:18:05.00,Default,,0000,0000,0000,,the one data member that the map will have at the top is just the root
Dialogue: 0,0:18:05.00,0:18:09.00,Default,,0000,0000,0000,,pointer. The pointer to the node at the top of the tree,
Dialogue: 0,0:18:09.00,0:18:12.00,Default,,0000,0000,0000,,and then from there we'll traverse pointers to find our way to other ones.
Dialogue: 0,0:18:12.00,0:18:15.00,Default,,0000,0000,0000,,And we will organize that tree for the binary search property.
Dialogue: 0,0:18:15.00,0:18:16.00,Default,,0000,0000,0000,,So using the
Dialogue: 0,0:18:16.00,0:18:20.00,Default,,0000,0000,0000,,key as the discriminate of what goes left and right,
Dialogue: 0,0:18:20.00,0:18:25.00,Default,,0000,0000,0000,,we'll compare each new key to the key at the root and decide is it going to go in the left subtree
Dialogue: 0,0:18:25.00,0:18:27.00,Default,,0000,0000,0000,,root or the right subtree root? And so on down to the
Dialogue: 0,0:18:27.00,0:18:31.00,Default,,0000,0000,0000,,matching position when we're doing a find, or to the place to insert if we're ready to
Dialogue: 0,0:18:31.00,0:18:33.00,Default,,0000,0000,0000,,put a new node in.
Dialogue: 0,0:18:33.00,0:18:36.00,Default,,0000,0000,0000,,So get value and add will have very similar structures, in terms of
Dialogue: 0,0:18:36.00,0:18:38.00,Default,,0000,0000,0000,,searching that tree
Dialogue: 0,0:18:38.00,0:18:39.00,Default,,0000,0000,0000,,
Dialogue: 0,0:18:39.00,0:18:40.00,Default,,0000,0000,0000,,from the root
Dialogue: 0,0:18:40.00,0:18:45.00,Default,,0000,0000,0000,,down to the leaf to find that match along the way, or to
Dialogue: 0,0:18:45.00,0:18:49.00,Default,,0000,0000,0000,,report where to put a new one in. So
Dialogue: 0,0:18:49.00,0:18:52.00,Default,,0000,0000,0000,,let's look at the actual code; it has
Dialogue: 0,0:18:52.00,0:18:54.00,Default,,0000,0000,0000,,my struct, it
Dialogue: 0,0:18:54.00,0:18:57.00,Default,,0000,0000,0000,,has the strike key, it has the value type node,
Dialogue: 0,0:18:57.00,0:19:00.00,Default,,0000,0000,0000,,two pointers there, and then the one data member for the map
Dialogue: 0,0:19:00.00,0:19:03.00,Default,,0000,0000,0000,,itself here is the pointer to the root node. I
Dialogue: 0,0:19:03.00,0:19:09.00,Default,,0000,0000,0000,,also put a couple of helper number functions that I'm going to need.
Dialogue: 0,0:19:09.00,0:19:10.00,Default,,0000,0000,0000,,
Dialogue: 0,0:19:10.00,0:19:13.00,Default,,0000,0000,0000,,Searching the tree and entering a new node in the tree are going to require a little
Dialogue: 0,0:19:13.00,0:19:18.00,Default,,0000,0000,0000,,helper, and we're going to see why that is. That basically that the add and get value public
Dialogue: 0,0:19:18.00,0:19:20.00,Default,,0000,0000,0000,,number functions are going to be just wrappers
Dialogue: 0,0:19:20.00,0:19:23.00,Default,,0000,0000,0000,,that turn and pass the code off to these recursive helpers.
Dialogue: 0,0:19:23.00,0:19:26.00,Default,,0000,0000,0000,,And if these cases, the additional information that each of these is
Dialogue: 0,0:19:26.00,0:19:28.00,Default,,0000,0000,0000,,tracking is what node we're at
Dialogue: 0,0:19:28.00,0:19:32.00,Default,,0000,0000,0000,,as we work our way down the tree. But the initial call to add is just going to say, well
Dialogue: 0,0:19:32.00,0:19:34.00,Default,,0000,0000,0000,,here's a key to value go put it in the right place.
Dialogue: 0,0:19:34.00,0:19:37.00,Default,,0000,0000,0000,,And that while we're doing the recursion we need to know where we are in the tree. So
Dialogue: 0,0:19:37.00,0:19:39.00,Default,,0000,0000,0000,,we're adding that extra parameter.
Dialogue: 0,0:19:39.00,0:19:43.00,Default,,0000,0000,0000,,What a lot of recursive code needs is just a little more housekeeping, and the
Dialogue: 0,0:19:43.00,0:19:44.00,Default,,0000,0000,0000,,housekeeping is
Dialogue: 0,0:19:44.00,0:19:51.00,Default,,0000,0000,0000,,what part of the tree we're currently searching or trying to enter into.
Dialogue: 0,0:19:51.00,0:19:54.00,Default,,0000,0000,0000,,So this is the outer call for get value.
Dialogue: 0,0:19:54.00,0:19:57.00,Default,,0000,0000,0000,,So get value is really just a wrapper,
Dialogue: 0,0:19:57.00,0:19:59.00,Default,,0000,0000,0000,,it's going to call tree search. It's going to
Dialogue: 0,0:19:59.00,0:20:03.00,Default,,0000,0000,0000,,ask the starting value for root. It's the
Dialogue: 0,0:20:03.00,0:20:04.00,Default,,0000,0000,0000,,beginning point for the search,
Dialogue: 0,0:20:04.00,0:20:07.00,Default,,0000,0000,0000,,looking for a particular key. And what tree searches are going to return is a
Dialogue: 0,0:20:07.00,0:20:10.00,Default,,0000,0000,0000,,pointer to a node. If
Dialogue: 0,0:20:10.00,0:20:14.00,Default,,0000,0000,0000,,that node was not found, if there was no node that has a string
Dialogue: 0,0:20:14.00,0:20:17.00,Default,,0000,0000,0000,,key that matches the one that we're looking for, then we'll return null. Otherwise, we'll return
Dialogue: 0,0:20:17.00,0:20:18.00,Default,,0000,0000,0000,,the node.
Dialogue: 0,0:20:18.00,0:20:20.00,Default,,0000,0000,0000,,And so it either will error
Dialogue: 0,0:20:20.00,0:20:23.00,Default,,0000,0000,0000,,when it didn't find it or
Dialogue: 0,0:20:23.00,0:20:25.00,Default,,0000,0000,0000,,pull out the value that was out of
Dialogue: 0,0:20:25.00,0:20:25.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:20:25.00,0:20:27.00,Default,,0000,0000,0000,,node structure.
Dialogue: 0,0:20:27.00,0:20:30.00,Default,,0000,0000,0000,,Well, this part looks pretty okay. The template, right, there's always just a
Dialogue: 0,0:20:30.00,0:20:33.00,Default,,0000,0000,0000,,little bit of goo up there, right, seeing kind of
Dialogue: 0,0:20:33.00,0:20:36.00,Default,,0000,0000,0000,,the template header on the top and the use of the val type, and all this other stuff.
Dialogue: 0,0:20:36.00,0:20:39.00,Default,,0000,0000,0000,,It's going to get a little bit worse here. So just kind of
Dialogue: 0,0:20:39.00,0:20:42.00,Default,,0000,0000,0000,,hopefully take a deep breath and say, okay that part actually
Dialogue: 0,0:20:42.00,0:20:46.00,Default,,0000,0000,0000,,doesn't scare me too much. We're going to look at what happens when I write the tree search code, where
Dialogue: 0,0:20:46.00,0:20:48.00,Default,,0000,0000,0000,,it really actually goes off and does the search down the tree. And there's going to be
Dialogue: 0,0:20:48.00,0:20:49.00,Default,,0000,0000,0000,,
Dialogue: 0,0:20:49.00,0:20:52.00,Default,,0000,0000,0000,,a little bit more machinations required on this. So let's just talk about it first,
Dialogue: 0,0:20:52.00,0:20:55.00,Default,,0000,0000,0000,,just what the code does. And then I'm going to come back and talk about some of the syntax that's
Dialogue: 0,0:20:55.00,0:20:58.00,Default,,0000,0000,0000,,required to make this work correctly.
Dialogue: 0,0:20:58.00,0:21:02.00,Default,,0000,0000,0000,,So the idea of tree search is, given a pointer to a particular
Dialogue: 0,0:21:02.00,0:21:02.00,Default,,0000,0000,0000,,subtree, it
Dialogue: 0,0:21:02.00,0:21:05.00,Default,,0000,0000,0000,,could be the root of the original tree or some
Dialogue: 0,0:21:05.00,0:21:07.00,Default,,0000,0000,0000,,smaller subtree further down, and a key that we're looking for, we're
Dialogue: 0,0:21:07.00,0:21:10.00,Default,,0000,0000,0000,,going to return a match when we find that node.
Dialogue: 0,0:21:10.00,0:21:15.00,Default,,0000,0000,0000,,So looking at the step here, where if the key that we have matches the key of the node
Dialogue: 0,0:21:15.00,0:21:17.00,Default,,0000,0000,0000,,we're looking at, then this is the node.
Dialogue: 0,0:21:17.00,0:21:19.00,Default,,0000,0000,0000,,This is the one we wanted.
Dialogue: 0,0:21:19.00,0:21:23.00,Default,,0000,0000,0000,,Otherwise, right, we look at two cases. If the key is less than this node's key,
Dialogue: 0,0:21:23.00,0:21:26.00,Default,,0000,0000,0000,,then we're just going to return the result from searching in the left subtree.
Dialogue: 0,0:21:26.00,0:21:31.00,Default,,0000,0000,0000,,Otherwise it must be greater than, and we're going to search in the right subtree.
Dialogue: 0,0:21:31.00,0:21:34.00,Default,,0000,0000,0000,,So this case, right, duplicates aren't allowed, so there will be exactly one match, if
Dialogue: 0,0:21:34.00,0:21:37.00,Default,,0000,0000,0000,,at all.
Dialogue: 0,0:21:37.00,0:21:39.00,Default,,0000,0000,0000,,And when we find it we return.
Dialogue: 0,0:21:39.00,0:21:43.00,Default,,0000,0000,0000,,The other case that needs to be handled as part of base case is if what if we ever get to an
Dialogue: 0,0:21:43.00,0:21:44.00,Default,,0000,0000,0000,,empty tree.
Dialogue: 0,0:21:44.00,0:21:47.00,Default,,0000,0000,0000,,So we're looking for 32 and the last node we just passed was
Dialogue: 0,0:21:47.00,0:21:50.00,Default,,0000,0000,0000,,35. We needed to be the left of it, and it turns out there was nothing down there, we
Dialogue: 0,0:21:50.00,0:21:52.00,Default,,0000,0000,0000,,have an empty tree.
Dialogue: 0,0:21:52.00,0:21:54.00,Default,,0000,0000,0000,,We'll hit this case where T is null, and we'll return null. That means there was never
Dialogue: 0,0:21:54.00,0:21:58.00,Default,,0000,0000,0000,,a match to that. There's no other place in the tree
Dialogue: 0,0:21:58.00,0:22:01.00,Default,,0000,0000,0000,,where that 32 could have been. The binary search property completely dictates the
Dialogue: 0,0:22:01.00,0:22:04.00,Default,,0000,0000,0000,,series of left and right turns. There's nowhere else to look.
Dialogue: 0,0:22:04.00,0:22:06.00,Default,,0000,0000,0000,,So that's actually, really solving
Dialogue: 0,0:22:06.00,0:22:07.00,Default,,0000,0000,0000,,
Dialogue: 0,0:22:07.00,0:22:11.00,Default,,0000,0000,0000,,a lot of our - cleaning up our work for us, streamlining where we need to go;
Dialogue: 0,0:22:11.00,0:22:14.00,Default,,0000,0000,0000,,because the tree is organized through the
Dialogue: 0,0:22:14.00,0:22:16.00,Default,,0000,0000,0000,,mid point and the quarter point and then the eighth point
Dialogue: 0,0:22:16.00,0:22:19.00,Default,,0000,0000,0000,,to narrow down to where we could go. So as
Dialogue: 0,0:22:19.00,0:22:21.00,Default,,0000,0000,0000,,it is, this code works correctly.
Dialogue: 0,0:22:21.00,0:22:25.00,Default,,0000,0000,0000,,So do you have any questions about how it's thinking about doing its work?
Dialogue: 0,0:22:25.00,0:22:30.00,Default,,0000,0000,0000,,And then I'm going to show you why the syntax is a little bit wrong though.
Dialogue: 0,0:22:30.00,0:22:32.00,Default,,0000,0000,0000,,Okay, so let's talk about this
Dialogue: 0,0:22:32.00,0:22:34.00,Default,,0000,0000,0000,,return type coming out of
Dialogue: 0,0:22:34.00,0:22:36.00,Default,,0000,0000,0000,,the function.
Dialogue: 0,0:22:36.00,0:22:38.00,Default,,0000,0000,0000,,So let's go back to this for a second.
Dialogue: 0,0:22:38.00,0:22:41.00,Default,,0000,0000,0000,,That node is defined
Dialogue: 0,0:22:41.00,0:22:43.00,Default,,0000,0000,0000,,as a private member
Dialogue: 0,0:22:43.00,0:22:46.00,Default,,0000,0000,0000,,of the map class.
Dialogue: 0,0:22:46.00,0:22:48.00,Default,,0000,0000,0000,,So node is actually not a global type.
Dialogue: 0,0:22:48.00,0:22:53.00,Default,,0000,0000,0000,,It does not exist outside the map class. Its real name is
Dialogue: 0,0:22:53.00,0:22:56.00,Default,,0000,0000,0000,,
Dialogue: 0,0:22:56.00,0:22:58.00,Default,,0000,0000,0000,,map
Dialogue: 0,0:22:58.00,0:23:00.00,Default,,0000,0000,0000,,val type::
Dialogue: 0,0:23:00.00,0:23:03.00,Default,,0000,0000,0000,,node.
Dialogue: 0,0:23:03.00,0:23:05.00,Default,,0000,0000,0000,,That's its full name,
Dialogue: 0,0:23:05.00,0:23:08.00,Default,,0000,0000,0000,,is that. Now,
Dialogue: 0,0:23:08.00,0:23:08.00,Default,,0000,0000,0000,,inside
Dialogue: 0,0:23:08.00,0:23:10.00,Default,,0000,0000,0000,,the implementation of map,
Dialogue: 0,0:23:10.00,0:23:14.00,Default,,0000,0000,0000,,which is to say inside the class map, or inside member functions that we're
Dialogue: 0,0:23:14.00,0:23:17.00,Default,,0000,0000,0000,,defining later, you'll not that we can just kind of drop
Dialogue: 0,0:23:17.00,0:23:21.00,Default,,0000,0000,0000,,the big full name. The kind of my name is mister such and such, and such and
Dialogue: 0,0:23:21.00,0:23:26.00,Default,,0000,0000,0000,,such; it's like okay, you can just call it node, the short name internal to the class
Dialogue: 0,0:23:26.00,0:23:28.00,Default,,0000,0000,0000,,because it's inside that scope. And
Dialogue: 0,0:23:28.00,0:23:31.00,Default,,0000,0000,0000,,it's able to say, okay in this scope is there something called node? Okay there is. Okay, that's the
Dialogue: 0,0:23:31.00,0:23:34.00,Default,,0000,0000,0000,,one. Outside of that scope, though, if you were trying to use that outside of the
Dialogue: 0,0:23:34.00,0:23:37.00,Default,,0000,0000,0000,,class or some other places, it's going to
Dialogue: 0,0:23:37.00,0:23:40.00,Default,,0000,0000,0000,,have a little bit more trouble with this idea of node by itself. It's going to need to see
Dialogue: 0,0:23:40.00,0:23:42.00,Default,,0000,0000,0000,,that full name. Let
Dialogue: 0,0:23:42.00,0:23:44.00,Default,,0000,0000,0000,,me show you on this piece of code,
Dialogue: 0,0:23:44.00,0:23:46.00,Default,,0000,0000,0000,,that node here
Dialogue: 0,0:23:46.00,0:23:51.00,Default,,0000,0000,0000,,happens to be in the slight quirk of the way sequel plus defines things, that that
Dialogue: 0,0:23:51.00,0:23:56.00,Default,,0000,0000,0000,,use of node is not considered in class scope yet.
Dialogue: 0,0:23:56.00,0:23:57.00,Default,,0000,0000,0000,,That
Dialogue: 0,0:23:57.00,0:24:01.00,Default,,0000,0000,0000,,the compiler leads from left to write, so we'll look at the first one. It says, template
Dialogue: 0,0:24:01.00,0:24:04.00,Default,,0000,0000,0000,,type name val type, and so what the compiler sees so far is, I'm about to
Dialogue: 0,0:24:04.00,0:24:07.00,Default,,0000,0000,0000,,see something that's templated on val type.
Dialogue: 0,0:24:07.00,0:24:10.00,Default,,0000,0000,0000,,So it's a pattern for which val type is a placeholder in.
Dialogue: 0,0:24:10.00,0:24:12.00,Default,,0000,0000,0000,,And then it sees val type
Dialogue: 0,0:24:12.00,0:24:16.00,Default,,0000,0000,0000,,as the return value, and it says, okay, that's the placeholder. And then it sees this map :: and
Dialogue: 0,0:24:16.00,0:24:18.00,Default,,0000,0000,0000,,
Dialogue: 0,0:24:18.00,0:24:21.00,Default,,0000,0000,0000,,it says, okay, this is within the - the thing
Dialogue: 0,0:24:21.00,0:24:26.00,Default,,0000,0000,0000,,that I'm defining here is within scope of the map class. And so it sees the map
Dialogue: 0,0:24:26.00,0:24:26.00,Default,,0000,0000,0000,,::
Dialogue: 0,0:24:26.00,0:24:29.00,Default,,0000,0000,0000,,and that as soon as it crosses those double colons,
Dialogue: 0,0:24:29.00,0:24:31.00,Default,,0000,0000,0000,,from that point forward
Dialogue: 0,0:24:31.00,0:24:33.00,Default,,0000,0000,0000,,it's inside the map scope.
Dialogue: 0,0:24:33.00,0:24:34.00,Default,,0000,0000,0000,,And so,
Dialogue: 0,0:24:34.00,0:24:37.00,Default,,0000,0000,0000,,when I use things like tree search, or I use the name node, it knows what I'm
Dialogue: 0,0:24:37.00,0:24:40.00,Default,,0000,0000,0000,,talking about. It says, oh there's a tree search in map class. There's a node struct in map
Dialogue: 0,0:24:40.00,0:24:43.00,Default,,0000,0000,0000,,class, it's all good.
Dialogue: 0,0:24:43.00,0:24:47.00,Default,,0000,0000,0000,,In the case of this one I've seen template type and val type, and
Dialogue: 0,0:24:47.00,0:24:50.00,Default,,0000,0000,0000,,at this point it doesn't know anything yet.
Dialogue: 0,0:24:50.00,0:24:53.00,Default,,0000,0000,0000,,And so it sees me using node, and it say,
Dialogue: 0,0:24:53.00,0:24:54.00,Default,,0000,0000,0000,,node I've
Dialogue: 0,0:24:54.00,0:24:55.00,Default,,0000,0000,0000,,never heard of node.
Dialogue: 0,0:24:55.00,0:24:58.00,Default,,0000,0000,0000,,I'm in the middle of making some template based on val type, but I haven't heard
Dialogue: 0,0:24:58.00,0:25:01.00,Default,,0000,0000,0000,,anything about node. Node isn't something that exists in the global name space.
Dialogue: 0,0:25:01.00,0:25:03.00,Default,,0000,0000,0000,,You must have made some
Dialogue: 0,0:25:03.00,0:25:04.00,Default,,0000,0000,0000,,tragic error.
Dialogue: 0,0:25:04.00,0:25:08.00,Default,,0000,0000,0000,,What it wants you to say is
Dialogue: 0,0:25:08.00,0:25:09.00,Default,,0000,0000,0000,,to give it the full name
Dialogue: 0,0:25:09.00,0:25:12.00,Default,,0000,0000,0000,,of map :: node.
Dialogue: 0,0:25:12.00,0:25:14.00,Default,,0000,0000,0000,,That the real full
Dialogue: 0,0:25:14.00,0:25:16.00,Default,,0000,0000,0000,,this is my name,
Dialogue: 0,0:25:16.00,0:25:21.00,Default,,0000,0000,0000,,and otherwise it will be quite confused.
Dialogue: 0,0:25:21.00,0:25:24.00,Default,,0000,0000,0000,,If that weren't enough,
Dialogue: 0,0:25:24.00,0:25:26.00,Default,,0000,0000,0000,,we'd like to think that we were done
Dialogue: 0,0:25:26.00,0:25:27.00,Default,,0000,0000,0000,,with
Dialogue: 0,0:25:27.00,0:25:30.00,Default,,0000,0000,0000,,placating the C compiler. But it turns out there's one other little
Dialogue: 0,0:25:30.00,0:25:32.00,Default,,0000,0000,0000,,thing that has to happen here,
Dialogue: 0,0:25:32.00,0:25:34.00,Default,,0000,0000,0000,,which is there is an obscure
Dialogue: 0,0:25:34.00,0:25:38.00,Default,,0000,0000,0000,,reason why, even though I've given it the full name, and I feel like I've done my
Dialogue: 0,0:25:38.00,0:25:40.00,Default,,0000,0000,0000,,duty in describing this thing,
Dialogue: 0,0:25:40.00,0:25:43.00,Default,,0000,0000,0000,,that the compiler still is a little bit confused
Dialogue: 0,0:25:43.00,0:25:45.00,Default,,0000,0000,0000,,by this usage.
Dialogue: 0,0:25:45.00,0:25:48.00,Default,,0000,0000,0000,,And because the C language is just immensely complicated,
Dialogue: 0,0:25:48.00,0:25:50.00,Default,,0000,0000,0000,,there are a lot of funny interactions,
Dialogue: 0,0:25:50.00,0:25:52.00,Default,,0000,0000,0000,,there are a couple of situations it can get in to,
Dialogue: 0,0:25:52.00,0:25:53.00,Default,,0000,0000,0000,,where
Dialogue: 0,0:25:53.00,0:25:56.00,Default,,0000,0000,0000,,because it's trying hard to read left to right and see the things.
Dialogue: 0,0:25:56.00,0:25:59.00,Default,,0000,0000,0000,,Sometimes it needs to know some things in advance that it doesn't have all the
Dialogue: 0,0:25:59.00,0:26:00.00,Default,,0000,0000,0000,,information for.
Dialogue: 0,0:26:00.00,0:26:03.00,Default,,0000,0000,0000,,And it turns out in this case there's actually some obscure situation where
Dialogue: 0,0:26:03.00,0:26:06.00,Default,,0000,0000,0000,,it might not realize this is really a type.
Dialogue: 0,0:26:06.00,0:26:08.00,Default,,0000,0000,0000,,It might think it was
Dialogue: 0,0:26:08.00,0:26:10.00,Default,,0000,0000,0000,,more of a global constant
Dialogue: 0,0:26:10.00,0:26:14.00,Default,,0000,0000,0000,,that we actually have to use the type name key word again here
Dialogue: 0,0:26:14.00,0:26:16.00,Default,,0000,0000,0000,,on this one
Dialogue: 0,0:26:16.00,0:26:17.00,Default,,0000,0000,0000,,construction.
Dialogue: 0,0:26:17.00,0:26:20.00,Default,,0000,0000,0000,,It is basically a hint to the compiler
Dialogue: 0,0:26:20.00,0:26:22.00,Default,,0000,0000,0000,,that says, the next thing coming up
Dialogue: 0,0:26:22.00,0:26:25.00,Default,,0000,0000,0000,,really is a type name.
Dialogue: 0,0:26:25.00,0:26:28.00,Default,,0000,0000,0000,,So given that you can't tell that, you'd think it would be obvious; in
Dialogue: 0,0:26:28.00,0:26:31.00,Default,,0000,0000,0000,,this case it doesn't seem like there's a lot for it to be confused at, but there's
Dialogue: 0,0:26:31.00,0:26:33.00,Default,,0000,0000,0000,,actually some other constructions that we can't rule out.
Dialogue: 0,0:26:33.00,0:26:37.00,Default,,0000,0000,0000,,So the compiler is a little bit confused in this situation, and it wants you to
Dialogue: 0,0:26:37.00,0:26:38.00,Default,,0000,0000,0000,,tell it in advance,
Dialogue: 0,0:26:38.00,0:26:41.00,Default,,0000,0000,0000,,and so I'll tell you that the basic rules for when you're going to need to use this is
Dialogue: 0,0:26:41.00,0:26:45.00,Default,,0000,0000,0000,,exactly in this and only this situation.
Dialogue: 0,0:26:45.00,0:26:48.00,Default,,0000,0000,0000,,And I'll tell you what the things are that are required for type name to
Dialogue: 0,0:26:48.00,0:26:50.00,Default,,0000,0000,0000,,become part of your
Dialogue: 0,0:26:50.00,0:26:51.00,Default,,0000,0000,0000,,repertoire.
Dialogue: 0,0:26:51.00,0:26:53.00,Default,,0000,0000,0000,,You have a return type
Dialogue: 0,0:26:53.00,0:26:54.00,Default,,0000,0000,0000,,on a member function
Dialogue: 0,0:26:54.00,0:26:58.00,Default,,0000,0000,0000,,that is defined as part of a class that is a template,
Dialogue: 0,0:26:58.00,0:27:00.00,Default,,0000,0000,0000,,and that type that you are using
Dialogue: 0,0:27:00.00,0:27:03.00,Default,,0000,0000,0000,,is defined within the scope of that template.
Dialogue: 0,0:27:03.00,0:27:07.00,Default,,0000,0000,0000,,So it's trying to use something that's within a template class scope
Dialogue: 0,0:27:07.00,0:27:08.00,Default,,0000,0000,0000,,outside of that scope
Dialogue: 0,0:27:08.00,0:27:09.00,Default,,0000,0000,0000,,
Dialogue: 0,0:27:09.00,0:27:11.00,Default,,0000,0000,0000,,that requires this type name.
Dialogue: 0,0:27:11.00,0:27:14.00,Default,,0000,0000,0000,,And the only place where we see things used out of their scope is on the
Dialogue: 0,0:27:14.00,0:27:15.00,Default,,0000,0000,0000,,return value.
Dialogue: 0,0:27:15.00,0:27:19.00,Default,,0000,0000,0000,,So this is kind of the one
Dialogue: 0,0:27:19.00,0:27:21.00,Default,,0000,0000,0000,,configuration that causes you to have to do this.
Dialogue: 0,0:27:21.00,0:27:22.00,Default,,0000,0000,0000,,
Dialogue: 0,0:27:22.00,0:27:25.00,Default,,0000,0000,0000,,It's really just, you know, a little bit of a C quirk.
Dialogue: 0,0:27:25.00,0:27:28.00,Default,,0000,0000,0000,,It doesn't change anything about what the code's doing or anything interesting about binary
Dialogue: 0,0:27:28.00,0:27:31.00,Default,,0000,0000,0000,,search trees, but it will come up in any situation where you have this helper member
Dialogue: 0,0:27:31.00,0:27:34.00,Default,,0000,0000,0000,,function that wants to return something that's templated. You
Dialogue: 0,0:27:34.00,0:27:35.00,Default,,0000,0000,0000,,have
Dialogue: 0,0:27:35.00,0:27:37.00,Default,,0000,0000,0000,,to placate the compiler there.
Dialogue: 0,0:27:37.00,0:27:39.00,Default,,0000,0000,0000,,The error message when you don't do it, actually turns out to be very good in
Dialogue: 0,0:27:39.00,0:27:45.00,Default,,0000,0000,0000,,GCC and very terrible in visual studio. GCC says type name required here,
Dialogue: 0,0:27:45.00,0:27:47.00,Default,,0000,0000,0000,,and visual studio says something completely
Dialogue: 0,0:27:47.00,0:27:48.00,Default,,0000,0000,0000,,mystical.
Dialogue: 0,0:27:48.00,0:27:49.00,Default,,0000,0000,0000,,So it
Dialogue: 0,0:27:49.00,0:27:52.00,Default,,0000,0000,0000,,is something to be just a little bit careful about when you're trying to write
Dialogue: 0,0:27:52.00,0:27:56.00,Default,,0000,0000,0000,,that kind of
Dialogue: 0,0:27:56.00,0:27:58.00,Default,,0000,0000,0000,,code. Question? The asterisk? The asterisk is just because it returns a pointer.
Dialogue: 0,0:27:58.00,0:28:00.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:00.00,0:28:03.00,Default,,0000,0000,0000,,In all the situations, I'm always returning a pointer to the node back
Dialogue: 0,0:28:03.00,0:28:04.00,Default,,0000,0000,0000,,there.
Dialogue: 0,0:28:04.00,0:28:16.00,Default,,0000,0000,0000,,So here's the pointer to the match I found or node when I didn't find one. All right, that's a little bit of grimy code. Let's keep going.
Dialogue: 0,0:28:16.00,0:28:17.00,Default,,0000,0000,0000,,So how is it
Dialogue: 0,0:28:17.00,0:28:18.00,Default,,0000,0000,0000,,that add
Dialogue: 0,0:28:18.00,0:28:22.00,Default,,0000,0000,0000,,works? Well, it starts like get value, that
Dialogue: 0,0:28:22.00,0:28:23.00,Default,,0000,0000,0000,,the
Dialogue: 0,0:28:23.00,0:28:27.00,Default,,0000,0000,0000,,strategy we're going to use for inserting into the tree is the really simple one that say,
Dialogue: 0,0:28:27.00,0:28:30.00,Default,,0000,0000,0000,,well don't rearrange anything that's there. For example, if I were trying to put
Dialogue: 0,0:28:30.00,0:28:32.00,Default,,0000,0000,0000,,the number 54 into this tree,
Dialogue: 0,0:28:32.00,0:28:33.00,Default,,0000,0000,0000,,you could say - well
Dialogue: 0,0:28:33.00,0:28:36.00,Default,,0000,0000,0000,,you could imagine putting it at the root and moving things around. Imagine
Dialogue: 0,0:28:36.00,0:28:40.00,Default,,0000,0000,0000,,that your goal is to put it in with a minimal amount of rearrangement.
Dialogue: 0,0:28:40.00,0:28:44.00,Default,,0000,0000,0000,,So leaving all the existing nodes connected the way they are,
Dialogue: 0,0:28:44.00,0:28:47.00,Default,,0000,0000,0000,,we're going to follow the binary search path of
Dialogue: 0,0:28:47.00,0:28:49.00,Default,,0000,0000,0000,,the get value code
Dialogue: 0,0:28:49.00,0:28:51.00,Default,,0000,0000,0000,,to find the place where 54 would have been
Dialogue: 0,0:28:51.00,0:28:54.00,Default,,0000,0000,0000,,if we left everything else in tact.
Dialogue: 0,0:28:54.00,0:28:57.00,Default,,0000,0000,0000,,Looking at 57 you could say, well it has to be to the left of
Dialogue: 0,0:28:57.00,0:29:01.00,Default,,0000,0000,0000,,57. Looking to the 32 you say, it has to be to the right of
Dialogue: 0,0:29:01.00,0:29:01.00,Default,,0000,0000,0000,,32.
Dialogue: 0,0:29:01.00,0:29:05.00,Default,,0000,0000,0000,,Here's where we get some empty tree, so we say, well that's the place where we'll put it.
Dialogue: 0,0:29:05.00,0:29:06.00,Default,,0000,0000,0000,,We're going to tack it off, kind
Dialogue: 0,0:29:06.00,0:29:12.00,Default,,0000,0000,0000,,of hang it off one of the empty trees
Dialogue: 0,0:29:12.00,0:29:15.00,Default,,0000,0000,0000,,along the front tier, the bottom of that tree.
Dialogue: 0,0:29:15.00,0:29:18.00,Default,,0000,0000,0000,,And so, we'll just walk our way down to where we fall off the tree, and put the
Dialogue: 0,0:29:18.00,0:29:19.00,Default,,0000,0000,0000,,new node in place there.
Dialogue: 0,0:29:19.00,0:29:22.00,Default,,0000,0000,0000,,So if I want the node 58 in, I'll say it
Dialogue: 0,0:29:22.00,0:29:25.00,Default,,0000,0000,0000,,has to go to the right; it has to go to the left; it has to go to the left; it has to go to the left; it
Dialogue: 0,0:29:25.00,0:29:27.00,Default,,0000,0000,0000,,will go right down there. If
Dialogue: 0,0:29:27.00,0:29:30.00,Default,,0000,0000,0000,,I want the node 100 in, it has to go right, right, right, right, right.
Dialogue: 0,0:29:30.00,0:29:35.00,Default,,0000,0000,0000,,That just kind of following the path, leaving all the current pointers and
Dialogue: 0,0:29:35.00,0:29:40.00,Default,,0000,0000,0000,,nodes in place, kind of finding a new place. And there's exactly one
Dialogue: 0,0:29:40.00,0:29:43.00,Default,,0000,0000,0000,,that given any number in a current configuration
Dialogue: 0,0:29:43.00,0:29:46.00,Default,,0000,0000,0000,,and the goal of not rearranging anything, there's exactly one place to put
Dialogue: 0,0:29:46.00,0:29:48.00,Default,,0000,0000,0000,,that new node in there
Dialogue: 0,0:29:48.00,0:29:49.00,Default,,0000,0000,0000,,that will
Dialogue: 0,0:29:49.00,0:29:51.00,Default,,0000,0000,0000,,keep the binary search property in tact.
Dialogue: 0,0:29:51.00,0:29:55.00,Default,,0000,0000,0000,,So it actually does a lot of decision making for us.
Dialogue: 0,0:29:55.00,0:29:58.00,Default,,0000,0000,0000,,We don't have to make any hard decisions about where to go. It just all this
Dialogue: 0,0:29:58.00,0:30:05.00,Default,,0000,0000,0000,,left, right, left, right based on less than and greater than. What if the values are equal? If
Dialogue: 0,0:30:05.00,0:30:09.00,Default,,0000,0000,0000,,the values are equal you have to have a plan, and it could be
Dialogue: 0,0:30:09.00,0:30:11.00,Default,,0000,0000,0000,,that you're using all the less than or equal to or greater than
Dialogue: 0,0:30:11.00,0:30:14.00,Default,,0000,0000,0000,,or equal to. You just have to have a plan. In terms of our map it turns out to
Dialogue: 0,0:30:14.00,0:30:17.00,Default,,0000,0000,0000,,equal to all the rights.
Dialogue: 0,0:30:17.00,0:30:20.00,Default,,0000,0000,0000,,So we handle it differently, which we don't every put a duplicate into the
Dialogue: 0,0:30:20.00,0:30:23.00,Default,,0000,0000,0000,,tree.
Dialogue: 0,0:30:23.00,0:30:26.00,Default,,0000,0000,0000,,So the add call is going to basically just be a wrapper
Dialogue: 0,0:30:26.00,0:30:29.00,Default,,0000,0000,0000,,that calls tree enter, starting from the root
Dialogue: 0,0:30:29.00,0:30:31.00,Default,,0000,0000,0000,,with the key and the value
Dialogue: 0,0:30:31.00,0:30:34.00,Default,,0000,0000,0000,,that then goes and does that work, walks its way down to the bottom to
Dialogue: 0,0:30:34.00,0:30:40.00,Default,,0000,0000,0000,,find the right place to stick the new one in.
Dialogue: 0,0:30:40.00,0:30:43.00,Default,,0000,0000,0000,,Here is
Dialogue: 0,0:30:43.00,0:30:44.00,Default,,0000,0000,0000,,a
Dialogue: 0,0:30:44.00,0:30:49.00,Default,,0000,0000,0000,,very dense little piece of code that will put a node into a tree
Dialogue: 0,0:30:49.00,0:30:52.00,Default,,0000,0000,0000,,using the strategy that we've just talked about of,
Dialogue: 0,0:30:52.00,0:30:55.00,Default,,0000,0000,0000,,don't rearrange any of the pointers, just walk your way down to where you find an empty
Dialogue: 0,0:30:55.00,0:30:59.00,Default,,0000,0000,0000,,tree. And once you find that empty tree, replace the empty tree with a singleton node
Dialogue: 0,0:30:59.00,0:31:02.00,Default,,0000,0000,0000,,with the new key and value that you have.
Dialogue: 0,0:31:02.00,0:31:06.00,Default,,0000,0000,0000,,So let's not look at the base case first. Let's actually look at the
Dialogue: 0,0:31:06.00,0:31:09.00,Default,,0000,0000,0000,,recursive cases, because I think that they're a little bit easier to think about.
Dialogue: 0,0:31:09.00,0:31:13.00,Default,,0000,0000,0000,,Is if we every find a match, so we have a key coming in, and it matches
Dialogue: 0,0:31:13.00,0:31:14.00,Default,,0000,0000,0000,,the current node, then we just overwrite.
Dialogue: 0,0:31:14.00,0:31:17.00,Default,,0000,0000,0000,,So that's the way the map handles
Dialogue: 0,0:31:17.00,0:31:18.00,Default,,0000,0000,0000,,insertion of a duplicate value.
Dialogue: 0,0:31:18.00,0:31:21.00,Default,,0000,0000,0000,,Now, in some other situation you might actually insert one. But in our case it turns out we
Dialogue: 0,0:31:21.00,0:31:24.00,Default,,0000,0000,0000,,never want a duplicate. We always want to take the existing value and replace
Dialogue: 0,0:31:24.00,0:31:26.00,Default,,0000,0000,0000,,it with a new one.
Dialogue: 0,0:31:26.00,0:31:28.00,Default,,0000,0000,0000,,If it matches, we're done.
Dialogue: 0,0:31:28.00,0:31:29.00,Default,,0000,0000,0000,,Otherwise,
Dialogue: 0,0:31:29.00,0:31:32.00,Default,,0000,0000,0000,,we need to decide whether we go left or right.
Dialogue: 0,0:31:32.00,0:31:36.00,Default,,0000,0000,0000,,Based on the key we're attempting to insert or the current node value, it either
Dialogue: 0,0:31:36.00,0:31:39.00,Default,,0000,0000,0000,,will go in the left of the subtree, left of the right, in which case we make
Dialogue: 0,0:31:39.00,0:31:44.00,Default,,0000,0000,0000,,exactly one recursive call either to the left or to the right depending on the
Dialogue: 0,0:31:44.00,0:31:46.00,Default,,0000,0000,0000,,relationship of key to the current
Dialogue: 0,0:31:46.00,0:31:48.00,Default,,0000,0000,0000,,key's value.
Dialogue: 0,0:31:48.00,0:31:49.00,Default,,0000,0000,0000,,And then
Dialogue: 0,0:31:49.00,0:31:52.00,Default,,0000,0000,0000,,the one base case that everything eventually gets down to, that's going to create a
Dialogue: 0,0:31:52.00,0:31:53.00,Default,,0000,0000,0000,,new node,
Dialogue: 0,0:31:53.00,0:31:57.00,Default,,0000,0000,0000,,is when you have an empty tree,
Dialogue: 0,0:31:57.00,0:31:59.00,Default,,0000,0000,0000,,then that says that you have followed the path that
Dialogue: 0,0:31:59.00,0:32:04.00,Default,,0000,0000,0000,,has lead off the tree and fallen off the bottom. It says replace that with
Dialogue: 0,0:32:04.00,0:32:05.00,Default,,0000,0000,0000,,this new singleton node.
Dialogue: 0,0:32:05.00,0:32:07.00,Default,,0000,0000,0000,,So we make a new node out in the heap.
Dialogue: 0,0:32:07.00,0:32:09.00,Default,,0000,0000,0000,,We're assigning the key
Dialogue: 0,0:32:09.00,0:32:12.00,Default,,0000,0000,0000,,based on this. We're assigning the value based on the parameter coming in. And then we set
Dialogue: 0,0:32:12.00,0:32:14.00,Default,,0000,0000,0000,,its left and right null to do
Dialogue: 0,0:32:14.00,0:32:16.00,Default,,0000,0000,0000,,
Dialogue: 0,0:32:16.00,0:32:20.00,Default,,0000,0000,0000,,a new leaf node, right, it has left and right null subtrees.
Dialogue: 0,0:32:20.00,0:32:22.00,Default,,0000,0000,0000,,And the way this got wired in the tree,
Dialogue: 0,0:32:22.00,0:32:26.00,Default,,0000,0000,0000,,you don't see who is it that's now pointing to this tree, this new
Dialogue: 0,0:32:26.00,0:32:28.00,Default,,0000,0000,0000,,singleton node that I placed into here?
Dialogue: 0,0:32:28.00,0:32:31.00,Default,,0000,0000,0000,,You don't typically see that wire that's coming into it. Who
Dialogue: 0,0:32:31.00,0:32:33.00,Default,,0000,0000,0000,,is pointing to it
Dialogue: 0,0:32:33.00,0:32:34.00,Default,,0000,0000,0000,,is actually being done
Dialogue: 0,0:32:34.00,0:32:39.00,Default,,0000,0000,0000,,by T being passed by reference.
Dialogue: 0,0:32:39.00,0:32:42.00,Default,,0000,0000,0000,,The node right above it,
Dialogue: 0,0:32:42.00,0:32:44.00,Default,,0000,0000,0000,,the left or the right
Dialogue: 0,0:32:44.00,0:32:48.00,Default,,0000,0000,0000,,of what's going to become the parent of the new node being entered,
Dialogue: 0,0:32:48.00,0:32:51.00,Default,,0000,0000,0000,,was passed by reference. It previously was null,
Dialogue: 0,0:32:51.00,0:32:55.00,Default,,0000,0000,0000,,and it got reassigned to point to this new node. So the kind of wiring in of
Dialogue: 0,0:32:55.00,0:32:58.00,Default,,0000,0000,0000,,that node is happening by the pass by reference of the pointer, which is a
Dialogue: 0,0:32:58.00,0:33:04.00,Default,,0000,0000,0000,,tricky thing to kind of watch and get your head around. Let's
Dialogue: 0,0:33:04.00,0:33:06.00,Default,,0000,0000,0000,,look at the code operating. Do you have a
Dialogue: 0,0:33:06.00,0:33:13.00,Default,,0000,0000,0000,,question? Yes. [Inaudible]. Can you
Dialogue: 0,0:33:13.00,0:33:14.00,Default,,0000,0000,0000,,explain
Dialogue: 0,0:33:14.00,0:33:16.00,Default,,0000,0000,0000,,
Dialogue: 0,0:33:16.00,0:33:17.00,Default,,0000,0000,0000,,that little step?
Dialogue: 0,0:33:17.00,0:33:22.00,Default,,0000,0000,0000,,Instructor: Well this step is just something in the case of the map, if we every find an existing entity that has that key, and
Dialogue: 0,0:33:22.00,0:33:23.00,Default,,0000,0000,0000,,we overwrite.
Dialogue: 0,0:33:23.00,0:33:27.00,Default,,0000,0000,0000,,So in the map you said previously, Bob's phone number is this, and then you install a new
Dialogue: 0,0:33:27.00,0:33:30.00,Default,,0000,0000,0000,,phone number on Bob. If it finds a map to Bob saying Bob was previously entered, it just
Dialogue: 0,0:33:30.00,0:33:34.00,Default,,0000,0000,0000,,replaces his value. So no nodes are created, no pointers are rearranged;
Dialogue: 0,0:33:34.00,0:33:38.00,Default,,0000,0000,0000,,it just commandeers that node and changes its value.
Dialogue: 0,0:33:38.00,0:33:43.00,Default,,0000,0000,0000,,That's the behaviors specified by map.
Dialogue: 0,0:33:43.00,0:33:45.00,Default,,0000,0000,0000,,So if we have this
Dialogue: 0,0:33:45.00,0:33:46.00,Default,,0000,0000,0000,,right now, we've got
Dialogue: 0,0:33:46.00,0:33:49.00,Default,,0000,0000,0000,,some handful of fruits that are installed
Dialogue: 0,0:33:49.00,0:33:53.00,Default,,0000,0000,0000,,in our tree with some value. It's doesn't matter what the value is, so I didn't even bother to fill
Dialogue: 0,0:33:53.00,0:33:57.00,Default,,0000,0000,0000,,it in to confuse you. So this is what I have, papaya is my root node, and then
Dialogue: 0,0:33:57.00,0:34:01.00,Default,,0000,0000,0000,,the next level down has banana and peach, and the pear and what not. So
Dialogue: 0,0:34:01.00,0:34:03.00,Default,,0000,0000,0000,,root is pointing to papaya right now.
Dialogue: 0,0:34:03.00,0:34:06.00,Default,,0000,0000,0000,,When I make my call to insert a new value,
Dialogue: 0,0:34:06.00,0:34:09.00,Default,,0000,0000,0000,,let's say that the one that I want to put in the tree now is orange,
Dialogue: 0,0:34:09.00,0:34:13.00,Default,,0000,0000,0000,,the very first call to tree enter looks like this,
Dialogue: 0,0:34:13.00,0:34:16.00,Default,,0000,0000,0000,,T is the reference parameter that's coming in, and
Dialogue: 0,0:34:16.00,0:34:20.00,Default,,0000,0000,0000,,it refers to root.
Dialogue: 0,0:34:20.00,0:34:24.00,Default,,0000,0000,0000,,So the very first call to tree enter says please insert
Dialogue: 0,0:34:24.00,0:34:27.00,Default,,0000,0000,0000,,orange and its value
Dialogue: 0,0:34:27.00,0:34:28.00,Default,,0000,0000,0000,,into the tree
Dialogue: 0,0:34:28.00,0:34:31.00,Default,,0000,0000,0000,,who is pointed to by
Dialogue: 0,0:34:31.00,0:34:34.00,Default,,0000,0000,0000,,root. So it actually has that by reference. It's going to need that by
Dialogue: 0,0:34:34.00,0:34:37.00,Default,,0000,0000,0000,,reference because it's actually planning on updating that
Dialogue: 0,0:34:37.00,0:34:39.00,Default,,0000,0000,0000,,when it finally installs the new node.
Dialogue: 0,0:34:39.00,0:34:43.00,Default,,0000,0000,0000,,So the first call to tree enter says, okay well is orange less than or greater than
Dialogue: 0,0:34:43.00,0:34:45.00,Default,,0000,0000,0000,,papaya.
Dialogue: 0,0:34:45.00,0:34:47.00,Default,,0000,0000,0000,,Orange precedes papaya
Dialogue: 0,0:34:47.00,0:34:48.00,Default,,0000,0000,0000,,in the alphabet,
Dialogue: 0,0:34:48.00,0:34:50.00,Default,,0000,0000,0000,,so okay, well call tree enter
Dialogue: 0,0:34:50.00,0:34:52.00,Default,,0000,0000,0000,,the second time
Dialogue: 0,0:34:52.00,0:34:53.00,Default,,0000,0000,0000,,passing
Dialogue: 0,0:34:53.00,0:34:58.00,Default,,0000,0000,0000,,the left subtree of the current value of tee. And so T
Dialogue: 0,0:34:58.00,0:35:00.00,Default,,0000,0000,0000,,was a reference to root right then,
Dialogue: 0,0:35:00.00,0:35:04.00,Default,,0000,0000,0000,,now T becomes a reference to the left subtree coming out of papaya. So it says, now
Dialogue: 0,0:35:04.00,0:35:06.00,Default,,0000,0000,0000,,okay, for the tree
Dialogue: 0,0:35:06.00,0:35:10.00,Default,,0000,0000,0000,,that we're talking about here, which is the one that points to the banana and
Dialogue: 0,0:35:10.00,0:35:14.00,Default,,0000,0000,0000,,below. That's the new root of that subtree is banana, it says, does orange go
Dialogue: 0,0:35:14.00,0:35:15.00,Default,,0000,0000,0000,,to the left or right
Dialogue: 0,0:35:15.00,0:35:19.00,Default,,0000,0000,0000,,of the root node
Dialogue: 0,0:35:19.00,0:35:21.00,Default,,0000,0000,0000,,banana? And it goes to the right. So the third stack frame
Dialogue: 0,0:35:21.00,0:35:24.00,Default,,0000,0000,0000,,of tree enter now says, well the reference pointer
Dialogue: 0,0:35:24.00,0:35:28.00,Default,,0000,0000,0000,,is now looking at the right subtree coming out of banana. And it
Dialogue: 0,0:35:28.00,0:35:29.00,Default,,0000,0000,0000,,says, well does melon go to
Dialogue: 0,0:35:29.00,0:35:31.00,Default,,0000,0000,0000,,the left or the right of
Dialogue: 0,0:35:31.00,0:35:32.00,Default,,0000,0000,0000,,that?
Dialogue: 0,0:35:32.00,0:35:34.00,Default,,0000,0000,0000,,It goes to the right,
Dialogue: 0,0:35:34.00,0:35:36.00,Default,,0000,0000,0000,,so now on this call, right,
Dialogue: 0,0:35:36.00,0:35:40.00,Default,,0000,0000,0000,,the current value of T is going to be null. It is a reference, so a synonym for
Dialogue: 0,0:35:40.00,0:35:44.00,Default,,0000,0000,0000,,what was the right field coming out of the melon node,
Dialogue: 0,0:35:44.00,0:35:47.00,Default,,0000,0000,0000,,and in this is the case where it says, if orange was in the tree,
Dialogue: 0,0:35:47.00,0:35:50.00,Default,,0000,0000,0000,,then this is where it would be hanging off of. It would be coming off of the
Dialogue: 0,0:35:50.00,0:35:51.00,Default,,0000,0000,0000,,right
Dialogue: 0,0:35:51.00,0:35:52.00,Default,,0000,0000,0000,,
Dialogue: 0,0:35:52.00,0:35:53.00,Default,,0000,0000,0000,,subtree of melon.
Dialogue: 0,0:35:53.00,0:35:55.00,Default,,0000,0000,0000,,That part is null,
Dialogue: 0,0:35:55.00,0:35:58.00,Default,,0000,0000,0000,,and so that's our place. That's the place where we're going to take out the
Dialogue: 0,0:35:58.00,0:35:59.00,Default,,0000,0000,0000,,existing null,
Dialogue: 0,0:35:59.00,0:36:00.00,Default,,0000,0000,0000,,wipe over it,
Dialogue: 0,0:36:00.00,0:36:04.00,Default,,0000,0000,0000,,and put in a new pointer to the node orange
Dialogue: 0,0:36:04.00,0:36:06.00,Default,,0000,0000,0000,,that's out here.
Dialogue: 0,0:36:06.00,0:36:09.00,Default,,0000,0000,0000,,And so that's how the thing got wired in. It's actually kind of
Dialogue: 0,0:36:09.00,0:36:12.00,Default,,0000,0000,0000,,subtle to see how that happened, because you don?t ever see a
Dialogue: 0,0:36:12.00,0:36:16.00,Default,,0000,0000,0000,,direct descendant, like T is left equals this, equals that new node; or T is
Dialogue: 0,0:36:16.00,0:36:17.00,Default,,0000,0000,0000,,right equals that new
Dialogue: 0,0:36:17.00,0:36:20.00,Default,,0000,0000,0000,,node. It happened by virtue of passing T right
Dialogue: 0,0:36:20.00,0:36:22.00,Default,,0000,0000,0000,,by reference into the
Dialogue: 0,0:36:22.00,0:36:26.00,Default,,0000,0000,0000,,calls further down the stack. That eventually, right when it hit the base
Dialogue: 0,0:36:26.00,0:36:26.00,Default,,0000,0000,0000,,case,
Dialogue: 0,0:36:26.00,0:36:30.00,Default,,0000,0000,0000,,it took what was previously a pointer to null and overwrote it with a pointer to this
Dialogue: 0,0:36:30.00,0:36:31.00,Default,,0000,0000,0000,,new cell,
Dialogue: 0,0:36:31.00,0:36:37.00,Default,,0000,0000,0000,,that then got attached into the tree. Let's take a
Dialogue: 0,0:36:37.00,0:36:38.00,Default,,0000,0000,0000,,look at this piece
Dialogue: 0,0:36:38.00,0:36:40.00,Default,,0000,0000,0000,,of code.
Dialogue: 0,0:36:40.00,0:36:44.00,Default,,0000,0000,0000,,That by reference there turns out to be really, really important.
Dialogue: 0,0:36:44.00,0:36:46.00,Default,,0000,0000,0000,,If that
Dialogue: 0,0:36:46.00,0:36:49.00,Default,,0000,0000,0000,,T was just being passed as an ordinary node star,
Dialogue: 0,0:36:49.00,0:36:52.00,Default,,0000,0000,0000,,nodes would just get lost, dropped on the floor like crazy.
Dialogue: 0,0:36:52.00,0:36:56.00,Default,,0000,0000,0000,,For example, consider the very first time when you're passing in root and root
Dialogue: 0,0:36:56.00,0:36:58.00,Default,,0000,0000,0000,,is empty. If root is null,
Dialogue: 0,0:36:58.00,0:36:59.00,Default,,0000,0000,0000,,it would say, well if root is null
Dialogue: 0,0:36:59.00,0:37:02.00,Default,,0000,0000,0000,,and then it would change this local parameter T; T is some new node of these
Dialogue: 0,0:37:02.00,0:37:06.00,Default,,0000,0000,0000,,things. But if it really wasn't making permanent changes to the root,
Dialogue: 0,0:37:06.00,0:37:08.00,Default,,0000,0000,0000,,really wasn't making root pointer of that new node, root
Dialogue: 0,0:37:08.00,0:37:12.00,Default,,0000,0000,0000,,would continue pointing to null, and that node would just get orphaned. And
Dialogue: 0,0:37:12.00,0:37:14.00,Default,,0000,0000,0000,,every subsequent one, the same thing would happen.
Dialogue: 0,0:37:14.00,0:37:17.00,Default,,0000,0000,0000,,So in order to have this be a persistent change,
Dialogue: 0,0:37:17.00,0:37:19.00,Default,,0000,0000,0000,,the pointer that's coming in,
Dialogue: 0,0:37:19.00,0:37:22.00,Default,,0000,0000,0000,,either the root in the first case or T left or T
Dialogue: 0,0:37:22.00,0:37:23.00,Default,,0000,0000,0000,,right
Dialogue: 0,0:37:23.00,0:37:25.00,Default,,0000,0000,0000,,in subsequent calls,
Dialogue: 0,0:37:25.00,0:37:30.00,Default,,0000,0000,0000,,needed to have the ability to be permanently modified when we attach that new
Dialogue: 0,0:37:30.00,0:37:33.00,Default,,0000,0000,0000,,subtree.
Dialogue: 0,0:37:33.00,0:37:37.00,Default,,0000,0000,0000,,That's really very tricky code, so I would be happy to
Dialogue: 0,0:37:37.00,0:37:39.00,Default,,0000,0000,0000,,try to answer
Dialogue: 0,0:37:39.00,0:37:41.00,Default,,0000,0000,0000,,questions or go through something to try to get your head around what
Dialogue: 0,0:37:41.00,0:37:44.00,Default,,0000,0000,0000,,it's supposed to be doing. If you could ask a question I
Dialogue: 0,0:37:44.00,0:37:47.00,Default,,0000,0000,0000,,could
Dialogue: 0,0:37:47.00,0:37:49.00,Default,,0000,0000,0000,,help you. Or you could just nod your head and say, I'm just totally fine.
Dialogue: 0,0:37:49.00,0:37:52.00,Default,,0000,0000,0000,,Could you use the tree search algorithm that you programmed before?
Dialogue: 0,0:37:52.00,0:37:53.00,Default,,0000,0000,0000,,They're
Dialogue: 0,0:37:53.00,0:37:58.00,Default,,0000,0000,0000,,very close, right, and
Dialogue: 0,0:37:58.00,0:37:59.00,Default,,0000,0000,0000,,where did I put it?
Dialogue: 0,0:37:59.00,0:38:02.00,Default,,0000,0000,0000,,It's on this slide.
Dialogue: 0,0:38:02.00,0:38:05.00,Default,,0000,0000,0000,,The problem with this one right now is it does really stop and return the
Dialogue: 0,0:38:05.00,0:38:07.00,Default,,0000,0000,0000,,null. So I could actually unify them, but it would take a little more
Dialogue: 0,0:38:07.00,0:38:11.00,Default,,0000,0000,0000,,work, and at some point you say, wow I could unify this
Dialogue: 0,0:38:11.00,0:38:15.00,Default,,0000,0000,0000,,at the expense of making this other piece of code a little more complicated. So in this case I chose
Dialogue: 0,0:38:15.00,0:38:18.00,Default,,0000,0000,0000,,to keep them separate. It's not impossible to unify them, but you end up
Dialogue: 0,0:38:18.00,0:38:19.00,Default,,0000,0000,0000,,having to point to
Dialogue: 0,0:38:19.00,0:38:22.00,Default,,0000,0000,0000,,where the node is or a null where you would insert a new node. Tree
Dialogue: 0,0:38:22.00,0:38:26.00,Default,,0000,0000,0000,,search doesn't care about, but tree enter does. It sort of would
Dialogue: 0,0:38:26.00,0:38:29.00,Default,,0000,0000,0000,,modify it to fit the needs of both at the expense of making it a little more awkward
Dialogue: 0,0:38:29.00,0:38:38.00,Default,,0000,0000,0000,,on both sides. Question here.
Dialogue: 0,0:38:38.00,0:38:43.00,Default,,0000,0000,0000,,[Inaudible] the number example.
Dialogue: 0,0:38:43.00,0:38:47.00,Default,,0000,0000,0000,,If you were inserting 54 where you said, if you called print,
Dialogue: 0,0:38:47.00,0:38:49.00,Default,,0000,0000,0000,,wouldn't it print
Dialogue: 0,0:38:49.00,0:38:51.00,Default,,0000,0000,0000,,out of order? So
Dialogue: 0,0:38:51.00,0:38:56.00,Default,,0000,0000,0000,,54 would go left of 57, right of 32, so it'd go over here.
Dialogue: 0,0:38:56.00,0:38:59.00,Default,,0000,0000,0000,,But the way in order traversals work is says,
Dialogue: 0,0:38:59.00,0:39:03.00,Default,,0000,0000,0000,,print everything in my left subtree, print everything in my left subtree, left subtree. So it would kind of print seven
Dialogue: 0,0:39:03.00,0:39:07.00,Default,,0000,0000,0000,,as it came back five, 32, and then it would print 54 before it got to the
Dialogue: 0,0:39:07.00,0:39:08.00,Default,,0000,0000,0000,,57. So
Dialogue: 0,0:39:08.00,0:39:12.00,Default,,0000,0000,0000,,an in order traversal of a binary search tree, as long as the binary search tree
Dialogue: 0,0:39:12.00,0:39:16.00,Default,,0000,0000,0000,,is properly maintained, will print them in sorted order.
Dialogue: 0,0:39:16.00,0:39:19.00,Default,,0000,0000,0000,,It's almost like, don't even think too hard about it, if
Dialogue: 0,0:39:19.00,0:39:22.00,Default,,0000,0000,0000,,everything in my left subtree is smaller, and everything in my right subtree is greater than me,
Dialogue: 0,0:39:22.00,0:39:26.00,Default,,0000,0000,0000,,if I print all of those I have to come out in sorted order.
Dialogue: 0,0:39:26.00,0:39:30.00,Default,,0000,0000,0000,,If the property is correctly maintained in the tree, then that
Dialogue: 0,0:39:30.00,0:39:31.00,Default,,0000,0000,0000,,by definition
Dialogue: 0,0:39:31.00,0:39:34.00,Default,,0000,0000,0000,,is a sorted way to pass through all the numbers. So if
Dialogue: 0,0:39:34.00,0:39:38.00,Default,,0000,0000,0000,,at any point an in order traversal is hitting numbers out of order, it would mean that the tree wasn't
Dialogue: 0,0:39:38.00,0:39:40.00,Default,,0000,0000,0000,,properly
Dialogue: 0,0:39:40.00,0:39:51.00,Default,,0000,0000,0000,,organized.
Dialogue: 0,0:39:51.00,0:39:55.00,Default,,0000,0000,0000,,So let's talk about how that works, there are a
Dialogue: 0,0:39:55.00,0:39:59.00,Default,,0000,0000,0000,,couple of other operations on the tree, things like doing the size,
Dialogue: 0,0:39:59.00,0:40:01.00,Default,,0000,0000,0000,,which would count the number of members. Which you could do by just doing a traversal, or you
Dialogue: 0,0:40:01.00,0:40:04.00,Default,,0000,0000,0000,,might do by just caching a number
Dialogue: 0,0:40:04.00,0:40:07.00,Default,,0000,0000,0000,,that you updated as you added and moved nodes. And
Dialogue: 0,0:40:07.00,0:40:10.00,Default,,0000,0000,0000,,the contains keys, that's basically just a tree search
Dialogue: 0,0:40:10.00,0:40:14.00,Default,,0000,0000,0000,,that determines whether it found a node or not.
Dialogue: 0,0:40:14.00,0:40:17.00,Default,,0000,0000,0000,,The rest of the implementation is not interest. There's also deleting, but I
Dialogue: 0,0:40:17.00,0:40:18.00,Default,,0000,0000,0000,,didn't show you
Dialogue: 0,0:40:18.00,0:40:23.00,Default,,0000,0000,0000,,that. The space use, how does this relate to the other known
Dialogue: 0,0:40:23.00,0:40:24.00,Default,,0000,0000,0000,,implementations that we have for math?
Dialogue: 0,0:40:24.00,0:40:27.00,Default,,0000,0000,0000,,It adds certainly some space overhead. We're
Dialogue: 0,0:40:27.00,0:40:31.00,Default,,0000,0000,0000,,going to have two pointers, a left and a right off every entry. So every entry is
Dialogue: 0,0:40:31.00,0:40:35.00,Default,,0000,0000,0000,,guaranteed to have an excess 8-byte capacity
Dialogue: 0,0:40:35.00,0:40:37.00,Default,,0000,0000,0000,,relative to the data being stored.
Dialogue: 0,0:40:37.00,0:40:40.00,Default,,0000,0000,0000,,It does actually add those tightly to the allocation. So like a link
Dialogue: 0,0:40:40.00,0:40:43.00,Default,,0000,0000,0000,,list, it allocates nodes on a per
Dialogue: 0,0:40:43.00,0:40:46.00,Default,,0000,0000,0000,,entry basis, so there's actually not a lot of
Dialogue: 0,0:40:46.00,0:40:49.00,Default,,0000,0000,0000,,reserve capacity that's waiting around unused the way it might been in a
Dialogue: 0,0:40:49.00,0:40:51.00,Default,,0000,0000,0000,,vector situation.
Dialogue: 0,0:40:51.00,0:40:53.00,Default,,0000,0000,0000,,And the performance of it is that it's based on the
Dialogue: 0,0:40:53.00,0:40:55.00,Default,,0000,0000,0000,,height of the tree,
Dialogue: 0,0:40:55.00,0:41:00.00,Default,,0000,0000,0000,,that both the add and the get value are doing a traversal starting from the root and
Dialogue: 0,0:41:00.00,0:41:03.00,Default,,0000,0000,0000,,working their way down to the bottom of the tree, either finding what it wanted
Dialogue: 0,0:41:03.00,0:41:05.00,Default,,0000,0000,0000,,along the way
Dialogue: 0,0:41:05.00,0:41:07.00,Default,,0000,0000,0000,,or falling off the bottom of the tree
Dialogue: 0,0:41:07.00,0:41:11.00,Default,,0000,0000,0000,,when it wasn't found or when it needs to be inserting a new node.
Dialogue: 0,0:41:11.00,0:41:15.00,Default,,0000,0000,0000,,That height of the tree, you're expecting it to be logarithmic. And so
Dialogue: 0,0:41:15.00,0:41:17.00,Default,,0000,0000,0000,,if I look at, for example, the values, I've got
Dialogue: 0,0:41:17.00,0:41:22.00,Default,,0000,0000,0000,,seven values here, two, eight, 14, 15, 20, and 21.
Dialogue: 0,0:41:22.00,0:41:23.00,Default,,0000,0000,0000,,Those seven,
Dialogue: 0,0:41:23.00,0:41:27.00,Default,,0000,0000,0000,,eight values can be inserted in a tree to get very
Dialogue: 0,0:41:27.00,0:41:28.00,Default,,0000,0000,0000,,different results.
Dialogue: 0,0:41:28.00,0:41:30.00,Default,,0000,0000,0000,,There's not one binary search tree
Dialogue: 0,0:41:30.00,0:41:33.00,Default,,0000,0000,0000,,that represents those values
Dialogue: 0,0:41:33.00,0:41:37.00,Default,,0000,0000,0000,,uniquely. Depending on what order you manage to insert them you'll have
Dialogue: 0,0:41:37.00,0:41:38.00,Default,,0000,0000,0000,,different things.
Dialogue: 0,0:41:38.00,0:41:39.00,Default,,0000,0000,0000,,For example,
Dialogue: 0,0:41:39.00,0:41:41.00,Default,,0000,0000,0000,,given the way we're doing it,
Dialogue: 0,0:41:41.00,0:41:44.00,Default,,0000,0000,0000,,whatever node is inserted first will be the root, and we never move the
Dialogue: 0,0:41:44.00,0:41:48.00,Default,,0000,0000,0000,,root. We leave the root along. So if you look at this as a historical
Dialogue: 0,0:41:48.00,0:41:50.00,Default,,0000,0000,0000,,artifact and say, well they entered a bunch of numbers,
Dialogue: 0,0:41:50.00,0:41:52.00,Default,,0000,0000,0000,,and this is the tree I got.
Dialogue: 0,0:41:52.00,0:41:55.00,Default,,0000,0000,0000,,I can tell you for sure that 15 was the very first number that they entered.
Dialogue: 0,0:41:55.00,0:41:57.00,Default,,0000,0000,0000,,There's no other possibility, 15 got entered first.
Dialogue: 0,0:41:57.00,0:42:01.00,Default,,0000,0000,0000,,The next number that got inserted was one of eight or 20, I don't know
Dialogue: 0,0:42:01.00,0:42:03.00,Default,,0000,0000,0000,,which.
Dialogue: 0,0:42:03.00,0:42:06.00,Default,,0000,0000,0000,,I can tell you, for example, that eight got inserted before 14. In terms
Dialogue: 0,0:42:06.00,0:42:09.00,Default,,0000,0000,0000,,of a level-by-level arrangement, the ones on level one
Dialogue: 0,0:42:09.00,0:42:13.00,Default,,0000,0000,0000,,were always inserted before the ones on level two.
Dialogue: 0,0:42:13.00,0:42:16.00,Default,,0000,0000,0000,,But one possibility I said here was well maybe 15 went in first,
Dialogue: 0,0:42:16.00,0:42:18.00,Default,,0000,0000,0000,,then eight, and then two,
Dialogue: 0,0:42:18.00,0:42:21.00,Default,,0000,0000,0000,,and then 20, and then 21, and then 14, and then 18. There
Dialogue: 0,0:42:21.00,0:42:25.00,Default,,0000,0000,0000,,are some other rearrangements that are also possible that would create the exact same
Dialogue: 0,0:42:25.00,0:42:26.00,Default,,0000,0000,0000,,tree.
Dialogue: 0,0:42:26.00,0:42:30.00,Default,,0000,0000,0000,,And there are other variations that would produce a different, but still valid,
Dialogue: 0,0:42:30.00,0:42:32.00,Default,,0000,0000,0000,,binary search tree.
Dialogue: 0,0:42:32.00,0:42:33.00,Default,,0000,0000,0000,,So with these seven nodes, right,
Dialogue: 0,0:42:33.00,0:42:36.00,Default,,0000,0000,0000,,this tree is height three,
Dialogue: 0,0:42:36.00,0:42:39.00,Default,,0000,0000,0000,,and is what's considered perfectly balanced. Half the nodes are on the
Dialogue: 0,0:42:39.00,0:42:42.00,Default,,0000,0000,0000,,left and the right of each tree all the way through it,
Dialogue: 0,0:42:42.00,0:42:45.00,Default,,0000,0000,0000,,leading to that just beautifully balanced
Dialogue: 0,0:42:45.00,0:42:46.00,Default,,0000,0000,0000,,
Dialogue: 0,0:42:46.00,0:42:47.00,Default,,0000,0000,0000,,result we're hoping for
Dialogue: 0,0:42:47.00,0:42:52.00,Default,,0000,0000,0000,,where both our operations, both add and get value, will be logarithmic. So
Dialogue: 0,0:42:52.00,0:42:54.00,Default,,0000,0000,0000,,if I have
Dialogue: 0,0:42:54.00,0:42:56.00,Default,,0000,0000,0000,,1,000
Dialogue: 0,0:42:56.00,0:42:59.00,Default,,0000,0000,0000,,nodes inserted, that height tree should be about ten. And if everything kind of went
Dialogue: 0,0:42:59.00,0:43:03.00,Default,,0000,0000,0000,,well and we got kind of went well, and we got an even split all the way around, then it would take ten
Dialogue: 0,0:43:03.00,0:43:06.00,Default,,0000,0000,0000,,comparisons to find something in that tree or determine it wasn't there' and
Dialogue: 0,0:43:06.00,0:43:07.00,Default,,0000,0000,0000,,also to insert,
Dialogue: 0,0:43:07.00,0:43:10.00,Default,,0000,0000,0000,,which was the thing we were having trouble with at the vector case, that
Dialogue: 0,0:43:10.00,0:43:13.00,Default,,0000,0000,0000,,because that search leads us right to the place where it needs to go,
Dialogue: 0,0:43:13.00,0:43:16.00,Default,,0000,0000,0000,,and the inserting because of the flexibility of the pointer base structure is
Dialogue: 0,0:43:16.00,0:43:17.00,Default,,0000,0000,0000,,very easy,
Dialogue: 0,0:43:17.00,0:43:21.00,Default,,0000,0000,0000,,we can make both that insert and add operate logarithmically.
Dialogue: 0,0:43:21.00,0:43:24.00,Default,,0000,0000,0000,,Let's think about some cases that aren't so good.
Dialogue: 0,0:43:24.00,0:43:28.00,Default,,0000,0000,0000,,I take those same seven numbers and I insert them
Dialogue: 0,0:43:28.00,0:43:32.00,Default,,0000,0000,0000,,not quite so perfectly, and I get a not quite so even result.
Dialogue: 0,0:43:32.00,0:43:36.00,Default,,0000,0000,0000,,So on this side I can tell you that 20 was the first one inserted.
Dialogue: 0,0:43:36.00,0:43:38.00,Default,,0000,0000,0000,,It was the root and the root doesn't move,
Dialogue: 0,0:43:38.00,0:43:41.00,Default,,0000,0000,0000,,but then subsequent ones was inserted an eight, and then a 21, and then an 18,
Dialogue: 0,0:43:41.00,0:43:46.00,Default,,0000,0000,0000,,and then a 14, and then a 15, and then it went back and got that two,
Dialogue: 0,0:43:46.00,0:43:47.00,Default,,0000,0000,0000,,the one over there.
Dialogue: 0,0:43:47.00,0:43:50.00,Default,,0000,0000,0000,,Another possibility for how it got inserted
Dialogue: 0,0:43:50.00,0:43:51.00,Default,,0000,0000,0000,,
Dialogue: 0,0:43:51.00,0:43:53.00,Default,,0000,0000,0000,,18, 14, 15, and so on.
Dialogue: 0,0:43:53.00,0:43:54.00,Default,,0000,0000,0000,,These are
Dialogue: 0,0:43:54.00,0:43:58.00,Default,,0000,0000,0000,,not quite as balanced as the last one, but they're not terribly unbalanced.
Dialogue: 0,0:43:58.00,0:44:00.00,Default,,0000,0000,0000,,They're like one or two
Dialogue: 0,0:44:00.00,0:44:03.00,Default,,0000,0000,0000,,more than the perfectly balanced case.
Dialogue: 0,0:44:03.00,0:44:09.00,Default,,0000,0000,0000,,So at logarithmic plus a little constant still doesn't look
Dialogue: 0,0:44:09.00,0:44:11.00,Default,,0000,0000,0000,,that bad. Okay, how bad can it really get?
Dialogue: 0,0:44:11.00,0:44:15.00,Default,,0000,0000,0000,,It can get really bad.
Dialogue: 0,0:44:15.00,0:44:18.00,Default,,0000,0000,0000,,I can take those seven numbers and insert them in the worst
Dialogue: 0,0:44:18.00,0:44:21.00,Default,,0000,0000,0000,,case, and produce a completely degenerate tree
Dialogue: 0,0:44:21.00,0:44:24.00,Default,,0000,0000,0000,,where, for example, if I insert them in sorted order
Dialogue: 0,0:44:24.00,0:44:25.00,Default,,0000,0000,0000,,or in reverse sorted order,
Dialogue: 0,0:44:25.00,0:44:26.00,Default,,0000,0000,0000,,
Dialogue: 0,0:44:26.00,0:44:28.00,Default,,0000,0000,0000,,I really have a link list.
Dialogue: 0,0:44:28.00,0:44:32.00,Default,,0000,0000,0000,,I don't have a tree at all. It goes two, 18, 14, 15, 20, 21,
Dialogue: 0,0:44:32.00,0:44:34.00,Default,,0000,0000,0000,,that's still a valid binary search tree.
Dialogue: 0,0:44:34.00,0:44:35.00,Default,,0000,0000,0000,,If you
Dialogue: 0,0:44:35.00,0:44:38.00,Default,,0000,0000,0000,,print it in order, it still comes out in sorted order.
Dialogue: 0,0:44:38.00,0:44:41.00,Default,,0000,0000,0000,,It still can be searched using a binary search strategy.
Dialogue: 0,0:44:41.00,0:44:45.00,Default,,0000,0000,0000,,It's just because the way it's been divided up here, it's not buying
Dialogue: 0,0:44:45.00,0:44:48.00,Default,,0000,0000,0000,,us a lot. So if I'm looking for the number 22, I'll say, well
Dialogue: 0,0:44:48.00,0:44:52.00,Default,,0000,0000,0000,,is it to the left or the right of two? It's to the right. Is it to the left or right of
Dialogue: 0,0:44:52.00,0:44:55.00,Default,,0000,0000,0000,,eight? Oh, it's to the right. Is it to the left or right, you know like all the way down, so finding
Dialogue: 0,0:44:55.00,0:44:57.00,Default,,0000,0000,0000,,22 looking at every single one
Dialogue: 0,0:44:57.00,0:45:01.00,Default,,0000,0000,0000,,of the current entries in the tree, before I could conclude, as I fell off the
Dialogue: 0,0:45:01.00,0:45:04.00,Default,,0000,0000,0000,,bottom, that it wasn't there.
Dialogue: 0,0:45:04.00,0:45:06.00,Default,,0000,0000,0000,,Similarly kind of over there;
Dialogue: 0,0:45:06.00,0:45:09.00,Default,,0000,0000,0000,,it didn't buy us a lot. It has a lot to do with
Dialogue: 0,0:45:09.00,0:45:13.00,Default,,0000,0000,0000,,how we inserted it as to how good a balance we're going to get.
Dialogue: 0,0:45:13.00,0:45:16.00,Default,,0000,0000,0000,,And there are some cases that will produce just drastically unbalanced
Dialogue: 0,0:45:16.00,0:45:17.00,Default,,0000,0000,0000,,
Dialogue: 0,0:45:17.00,0:45:21.00,Default,,0000,0000,0000,,things that require linear searches, totally linear to walk that way
Dialogue: 0,0:45:21.00,0:45:22.00,Default,,0000,0000,0000,,down
Dialogue: 0,0:45:22.00,0:45:25.00,Default,,0000,0000,0000,,to find something.
Dialogue: 0,0:45:25.00,0:45:26.00,Default,,0000,0000,0000,,There's a couple of other
Dialogue: 0,0:45:26.00,0:45:29.00,Default,,0000,0000,0000,,degenerate trees, just to mention it's not only the sorted or reverse sorted.
Dialogue: 0,0:45:29.00,0:45:33.00,Default,,0000,0000,0000,,There's also these other kind of saw tooth inputs, they're called,
Dialogue: 0,0:45:33.00,0:45:35.00,Default,,0000,0000,0000,,where you just happen to at any given point to
Dialogue: 0,0:45:35.00,0:45:39.00,Default,,0000,0000,0000,,have inserted the max or the min of the elements that remain, so it
Dialogue: 0,0:45:39.00,0:45:42.00,Default,,0000,0000,0000,,keeps kind of dividing the input into one and
Dialogue: 0,0:45:42.00,0:45:44.00,Default,,0000,0000,0000,,N-1. So having the
Dialogue: 0,0:45:44.00,0:45:47.00,Default,,0000,0000,0000,,largest and the smallest, and the largest and the smallest, and then
Dialogue: 0,0:45:47.00,0:45:48.00,Default,,0000,0000,0000,,subsequent smallest down there
Dialogue: 0,0:45:48.00,0:45:52.00,Default,,0000,0000,0000,,can also produce a linear line. It's not quite all just down the left or
Dialogue: 0,0:45:52.00,0:45:55.00,Default,,0000,0000,0000,,down the right, but it does mean that every single node has an empty
Dialogue: 0,0:45:55.00,0:45:59.00,Default,,0000,0000,0000,,left or right subtree is what's considered the degenerate case here. And
Dialogue: 0,0:45:59.00,0:46:01.00,Default,,0000,0000,0000,,both have the same property where
Dialogue: 0,0:46:01.00,0:46:04.00,Default,,0000,0000,0000,,half of the pointers off
Dialogue: 0,0:46:04.00,0:46:08.00,Default,,0000,0000,0000,,of each cell are going nowhere.
Dialogue: 0,0:46:08.00,0:46:10.00,Default,,0000,0000,0000,,There is an interesting relationship here
Dialogue: 0,0:46:10.00,0:46:12.00,Default,,0000,0000,0000,,between these worst-case inputs for transversion and quick sort, and they're
Dialogue: 0,0:46:12.00,0:46:14.00,Default,,0000,0000,0000,,actually kind of exactly one to one.
Dialogue: 0,0:46:14.00,0:46:18.00,Default,,0000,0000,0000,,That what made quick sort deteriorate was the element of the input,
Dialogue: 0,0:46:18.00,0:46:21.00,Default,,0000,0000,0000,,the max or the min of what remain. And that's exactly the same case
Dialogue: 0,0:46:21.00,0:46:25.00,Default,,0000,0000,0000,,for transversion, max or min of what remains means that you are not dividing your
Dialogue: 0,0:46:25.00,0:46:29.00,Default,,0000,0000,0000,,input into two partitions of roughly equal size. You're dividing them into the
Dialogue: 0,0:46:29.00,0:46:33.00,Default,,0000,0000,0000,,one, N-1, which is getting you nowhere. What do you
Dialogue: 0,0:46:33.00,0:46:37.00,Default,,0000,0000,0000,,get to do about it?
Dialogue: 0,0:46:37.00,0:46:40.00,Default,,0000,0000,0000,,You have to decide first of all if it's a problem worth solving.
Dialogue: 0,0:46:40.00,0:46:41.00,Default,,0000,0000,0000,,
Dialogue: 0,0:46:41.00,0:46:44.00,Default,,0000,0000,0000,,So that's what the first one say. Sometimes you just say that
Dialogue: 0,0:46:44.00,0:46:46.00,Default,,0000,0000,0000,,it will sometimes happen in some
Dialogue: 0,0:46:46.00,0:46:47.00,Default,,0000,0000,0000,,inputs
Dialogue: 0,0:46:47.00,0:46:50.00,Default,,0000,0000,0000,,that I consider rare enough that it will degenerate. I don't think they're
Dialogue: 0,0:46:50.00,0:46:52.00,Default,,0000,0000,0000,,important enough or common enough to make a big deal out of.
Dialogue: 0,0:46:52.00,0:46:56.00,Default,,0000,0000,0000,,I don't think that applies here, because it turns out that getting your data in sorted order is
Dialogue: 0,0:46:56.00,0:46:59.00,Default,,0000,0000,0000,,probably not unlikely. That somebody might be refilling a map
Dialogue: 0,0:46:59.00,0:47:02.00,Default,,0000,0000,0000,,with data they read from a file that they wrote out in sorted order last time.
Dialogue: 0,0:47:02.00,0:47:05.00,Default,,0000,0000,0000,,So saying that if it is coming in sorted,
Dialogue: 0,0:47:05.00,0:47:09.00,Default,,0000,0000,0000,,then I'm probably going to tolerate that, is probably not going to work.
Dialogue: 0,0:47:09.00,0:47:12.00,Default,,0000,0000,0000,,And there's two main strategies then, if you've agreed to take action about it,
Dialogue: 0,0:47:12.00,0:47:14.00,Default,,0000,0000,0000,,about what you're going to do.
Dialogue: 0,0:47:14.00,0:47:15.00,Default,,0000,0000,0000,,
Dialogue: 0,0:47:15.00,0:47:19.00,Default,,0000,0000,0000,,The first one is to wait until
Dialogue: 0,0:47:19.00,0:47:21.00,Default,,0000,0000,0000,,the problem gets bad enough
Dialogue: 0,0:47:21.00,0:47:23.00,Default,,0000,0000,0000,,that you decide to do something about it.
Dialogue: 0,0:47:23.00,0:47:28.00,Default,,0000,0000,0000,,So you don't do any rebalancing as you go. You just let stuff go, left, right, left,
Dialogue: 0,0:47:28.00,0:47:30.00,Default,,0000,0000,0000,,right, whatever's happening. And
Dialogue: 0,0:47:30.00,0:47:31.00,Default,,0000,0000,0000,,
Dialogue: 0,0:47:31.00,0:47:34.00,Default,,0000,0000,0000,,you try to keep track of the height of your tree,
Dialogue: 0,0:47:34.00,0:47:37.00,Default,,0000,0000,0000,,and you realize when the height of your tree seems sufficiently out of whack with
Dialogue: 0,0:47:37.00,0:47:39.00,Default,,0000,0000,0000,,your expected logarithmic height,
Dialogue: 0,0:47:39.00,0:47:42.00,Default,,0000,0000,0000,,to do something about it. Then you just fix the whole tree.
Dialogue: 0,0:47:42.00,0:47:45.00,Default,,0000,0000,0000,,You can clean the whole thing up. Pull them all out into a vector, rearrange them,
Dialogue: 0,0:47:45.00,0:47:49.00,Default,,0000,0000,0000,,put them back in, so the middlemost node is the root all the way down. And kind of
Dialogue: 0,0:47:49.00,0:47:50.00,Default,,0000,0000,0000,,create the perfectly balanced tree,
Dialogue: 0,0:47:50.00,0:47:52.00,Default,,0000,0000,0000,,and then keep going
Dialogue: 0,0:47:52.00,0:47:54.00,Default,,0000,0000,0000,,and wait for it to get out of whack, and fix it again;
Dialogue: 0,0:47:54.00,0:47:56.00,Default,,0000,0000,0000,,kind
Dialogue: 0,0:47:56.00,0:47:58.00,Default,,0000,0000,0000,,of wait and see.
Dialogue: 0,0:47:58.00,0:48:01.00,Default,,0000,0000,0000,,The other strategy, and this happens to be a more common one in
Dialogue: 0,0:48:01.00,0:48:06.00,Default,,0000,0000,0000,,practice, is you just constantly do a little bit of fixing up all the time.
Dialogue: 0,0:48:06.00,0:48:09.00,Default,,0000,0000,0000,,Whenever you notice that the tree is looking just a little bit lopsided, you let
Dialogue: 0,0:48:09.00,0:48:12.00,Default,,0000,0000,0000,,it get a little bit; usually you'll let it be out of balance by one.
Dialogue: 0,0:48:12.00,0:48:15.00,Default,,0000,0000,0000,,So you might have height four on that side and height three on that side.
Dialogue: 0,0:48:15.00,0:48:17.00,Default,,0000,0000,0000,,But as soon as it starts to get to be three and five,
Dialogue: 0,0:48:17.00,0:48:20.00,Default,,0000,0000,0000,,you do a little shuffle to bring them back to both four. And it
Dialogue: 0,0:48:20.00,0:48:21.00,Default,,0000,0000,0000,,involves just a little bit of work
Dialogue: 0,0:48:21.00,0:48:23.00,Default,,0000,0000,0000,,all the time
Dialogue: 0,0:48:23.00,0:48:25.00,Default,,0000,0000,0000,,to where you just don't let
Dialogue: 0,0:48:25.00,0:48:28.00,Default,,0000,0000,0000,,the tree turn into a real mess.
Dialogue: 0,0:48:28.00,0:48:31.00,Default,,0000,0000,0000,,But there's a little bit of extra fixing up being done all the time.
Dialogue: 0,0:48:31.00,0:48:35.00,Default,,0000,0000,0000,,And so the particular kind of tree that's discussed in the text, which you can read about,
Dialogue: 0,0:48:35.00,0:48:37.00,Default,,0000,0000,0000,,but we won't cover
Dialogue: 0,0:48:37.00,0:48:40.00,Default,,0000,0000,0000,,as part of our core material, is called the ADL tree. It's interesting to
Dialogue: 0,0:48:40.00,0:48:43.00,Default,,0000,0000,0000,,read about it to see what does it take, what kind of
Dialogue: 0,0:48:43.00,0:48:47.00,Default,,0000,0000,0000,,process is required to monitor this and do something about it. And
Dialogue: 0,0:48:47.00,0:48:50.00,Default,,0000,0000,0000,,so if we have that in place,
Dialogue: 0,0:48:50.00,0:48:51.00,Default,,0000,0000,0000,,
Dialogue: 0,0:48:51.00,0:48:53.00,Default,,0000,0000,0000,,we can get it to where
Dialogue: 0,0:48:53.00,0:48:57.00,Default,,0000,0000,0000,,the binary search tree part of this is logarithmic on both
Dialogue: 0,0:48:57.00,0:48:59.00,Default,,0000,0000,0000,,inserting new values and searching for values,
Dialogue: 0,0:48:59.00,0:49:03.00,Default,,0000,0000,0000,,which is that Holy Grail of efficiency boundary. You can say, yeah logarithmic is
Dialogue: 0,0:49:03.00,0:49:04.00,Default,,0000,0000,0000,,something we can tolerate
Dialogue: 0,0:49:04.00,0:49:08.00,Default,,0000,0000,0000,,by virtue of adding 8 bytes of pointer, potentially some balance factor,
Dialogue: 0,0:49:08.00,0:49:12.00,Default,,0000,0000,0000,,and some fanciness to guarantee that performance all over,
Dialogue: 0,0:49:12.00,0:49:15.00,Default,,0000,0000,0000,,but gets us somewhere that will scale very, very well for thousands
Dialogue: 0,0:49:15.00,0:49:18.00,Default,,0000,0000,0000,,and millions of entries, right, logarithmic is still a very, very fast
Dialogue: 0,0:49:18.00,0:49:20.00,Default,,0000,0000,0000,,function. So it
Dialogue: 0,0:49:20.00,0:49:24.00,Default,,0000,0000,0000,,creates a map that could really actually go the distance in scale. So, that's
Dialogue: 0,0:49:24.00,0:49:28.00,Default,,0000,0000,0000,,your talk about binary search trees. We'll come back and talk about
Dialogue: 0,0:49:28.00,0:49:38.00,Default,,0000,0000,0000,,hashing in graphs and stuff. I will see you on Wednesday.