[Section 7] [Less Comfortable]
[Nate Hardison] [Harvard University]
[This is CS50.] [CS50.TV]
>> Welcome to Section 7.
Thanks to hurricane Sandy,
instead of having a normal section this week,
we're doing this walkthrough through the section of questions.
I'm going to be following along with the Problem Set 6 specification
and going through all of the questions in the
"A Section of Questions" section.
If there are any questions,
please post these on CS50 Discuss.
>> Alright. Let's get started.
Right now, I'm looking at page 3 of the problem set specification.
We're going to first start talking about binary trees
since those have a lot of relevance to this week's problem set--
the Huffman tree encoding.
One of the very first data structures we talked about on CS50 was the array.
Remember that an array is a sequence of elements--
all of the same type--stored right next to each other in memory.
If I have an integer array that I can draw using this boxes-numbers-integers style--
Let's say I have 5 in the first box, I have 7 in the second,
then I have 8, 10, and 20 in the final box.
Remember, the two really good things about this array
are that we have this constant-time access to any particular element
in the array if we know its index.
For example, if I want to grab the third element in the array--
at index 2 using our zero-based indexing system--
I literally just have to do a simple mathematical calculation,
hop to that position in the array,
pull out the 8 that is stored there,
and I'm good to go.
>> One of the bad things about this array--that we talked about
when we discussed linked lists--
is that if I want to insert an element into this array,
I'm going to have to do some shifting around.
For example, this array right here
is in sorted order--sorted in ascending order--
5, then 7, then 8, then 10, and then 20--
but if I want to insert the number 9 into this array,
I'm going to have to shift some of the elements in order to make space.
We can draw this out here.
I'm going to have to move the 5, the 7, and then the 8;
create a gap where I can put the 9,
and then the 10 and the 20 can go to the right of the 9.
This is kind of a pain because in the worst-case scenario--
when we're having to insert either at the beginning or at the end
of the array, depending on how we're shifting--
we might end up having to shift all of the elements
that we're currently storing in the array.
>> So, what was the way around this?
The way around this was to go to our linked-list method where--
instead of storing the elements 5, 7, 8, 10, and 20 all next to each other in memory--
what we instead did was store them kind of wherever we wanted to store them
in these linked-list nodes which I'm drawing out here, kind of ad hoc.
And then we connected them together using these next pointers.
I can have a pointer from 5 to the 7,
a pointer from the 7 to the 8,
a pointer from the 8 to the 10,
and, finally, a pointer from the 10 to the 20,
and then a null pointer at the 20 indicating that there's nothing left.
The trade-off that we have here
is that now if we want to insert the number 9 into our sorted list,
all we have to do is create a new node with 9,
wire it up to point to the appropriate place,
and then rewire the 8 to point down to the 9.
That's pretty fast, assuming we know exactly where we want to insert the 9.
But the trade-off in exchange for this is that we've now lost the constant-time access
to any particular element in our data structure.
For example, if I want to find the fourth element in this linked list,
I'm going to have to start at the very beginning of the list
and work my way through counting node-by-node until I find the fourth one.
>> In order to get better access performance than a linked list--
but also retain some of the benefits that we had
in terms of insertion time from a linked list--
a binary tree is going to need to use a little more memory.
In particular, instead of just having one pointer in a binary tree node--
like the linked-list node does--
we're going to add a second pointer to the binary tree node.
Rather than just having one pointer to the next element,
we're going to have a pointer to a left child and a right child.
>> Let's draw a picture to see what that actually looks like.
Again, I'm going to use these boxes and arrows.
A binary tree node will start off with just a simple box.
It's going to have a space for the value,
and then it's also going to have a space for the left child and the right child.
I'm going to label them here.
We're going to have the left child, and then we're going to have the right child.
There are many different ways of doing this.
Sometimes for space and convenience,
I'll actually draw it like I'm doing here on the bottom
where I'm going to have the value at the top,
and then the right child on the bottom right,
and the left child on the bottom left.
Going back to this top diagram,
we have the value at the very top,
then we have the left-child pointer, and then we have the right-child pointer.
>> In the problem set specification,
we talk about drawing a node that has a value 7,
and then a left-child pointer that is null, and a right-child pointer that is null.
We can either write capital N-U-L-L in the space for
both the left child and the right child, or we can draw this diagonal slash
through each of the boxes to indicate that it's null.
I'm going to do that just because that's simpler.
What you see here are two ways of diagramming a very simple binary tree node
where we have the value 7 and null child pointers.
>> The second part of our specification talks about how with linked lists--
remember, we only had to hold on to the very first element in a list
to remember the entire list--
and likewise, with a binary tree, we only have to hold on to one pointer to the tree
in order to maintain control over the entire data structure.
This special element of the tree is called the root node of the tree.
For example, if this one node--this node containing the value 7
with null left- and right-child pointers--
were the only value in our tree,
then this would be our root node.
It's the very beginning of our tree.
We can see this a little more clearly once we start adding more nodes to our tree.
Let me pull up a new page.
>> Now we're going to draw a tree that has 7 at the root,
and 3 inside of the left child, and 9 inside of the right child.
Again, this is pretty simple.
We've got 7, draw a node for the 3, a node for 9,
and I'm going to set the left-child pointer of 7 to point to the node containing 3,
and the right-child pointer of the node containing 7 to the node containing 9.
Now, since 3 and 9 don't have any children,
we're going to set all of their child pointers to be null.
Here, the root of our tree corresponds to the node containing the number 7.
You can see that if all we have is a pointer to that root node,
we can then walk through our tree and access both child nodes--
both 3 and 9.
No need to maintain pointers to every single node on the tree.
All right. Now we're going to add another node to this diagram.
We're going to add a node containing 6,
and we're going to add this as the right child of the node containing 3.
To do that, I'm going to erase that null pointer in the 3 node
and wire it up to point to the node containing 6. All right.
>> At this point, let's go over a little bit of terminology.
To start, the reason that this is called a binary tree in particular
is that it has two child pointers.
There are other kinds of trees that have more child pointers.
In particular, you did a "trie" in Problem Set 5.
You'll notice that in that trie, you had 27 different pointers to different children--
one for each of the 26 letters in the English alphabet,
and then the 27th for the apostrophe--
so, that's similar to a type of tree.
But here, since it's binary, we only have two child pointers.
>> In addition to this root node that we talked about,
we've also been throwing around this term "child".
What does it mean for one node to be a child of another node?
It literally means that a child node is a child of another node
if that other node has one of its child pointers set to point to that node.
To put this into more concrete terms,
if 3 is pointed to by one of the child pointers of 7, then 3 is a child of 7.
If we were to figure out what the children of 7 are--
well, we see that 7 has a pointer to 3 and a pointer to 9,
so 9 and 3 are the children of 7.
9 has no children because its child pointers are null,
and 3 has only one child, 6.
6 also has no children because both of its pointers are null, which we'll draw right now.
>> Additionally, we also talk about the parents of a particular node,
and this is, as you'd expect, the reverse of this child description.
Each node has only one parent--instead of two as you might expect with humans.
For example, the parent of 3 is 7.
The parent of 9 is also 7, and the parent of 6 is 3. Not much to it.
We also have terms to talk about, grandparents and grandchildren,
and more generally, we talk about the ancestors
and descendants of a particular node.
The ancestor of a node--or ancestors, rather, of a node--
are all of the nodes that lie on the path from the root to that node.
For example, if I'm looking at the node 6,
then the ancestors are going to be both 3 and 7.
The ancestors of 9, for example, are--if I'm looking at the node 9--
then the ancestor of 9 is just 7.
And descendants are exactly the reverse.
If I want to look at all of the descendants of 7,
then I have to look at all of the nodes beneath it.
So, I have 3, 9, and 6 all as descendants of 7.
>> The final term that we'll talk about is this notion of being a sibling.
Siblings--kind of following along on these family terms--
are nodes that are at the same level in the tree.
So, 3 and 9 are siblings because they are at the same level in the tree.
They both have the same parent, 7.
The 6 has no siblings because 9 doesn't have any children.
And 7 doesn't have any siblings because it's the root of our tree,
and there's only ever one root.
For 7 to have siblings, there would have to be a node above 7.
There would have to be a parent of 7, in which case 7 would no longer be the root of the tree.
Then that new parent of 7 would also have to have a child,
and that child would then be the sibling of 7.
>> All right. Moving on.
When we started our discussion of binary trees,
we talked about how we were going to use them to
gain an advantage over both arrays and linked lists.
And the way we're going to do that is with this ordering property.
We say that a binary tree is ordered, according to the specification,
if for each node in our tree, all of its descendants on the left--
the left child and all of the left child's descendants--
have lesser values, and all of the nodes on the right--
the right child and all of the right child's descendants--
have nodes greater than the value of the current node that we're looking at.
Just for simplicity, we're going to assume that there aren't any duplicate nodes in our tree.
For example, in this tree, we're not going to deal with the case
where we have the value 7 at the root
and then we also have the value 7 elsewhere in the tree.
In this case, you'll notice that this tree is indeed ordered.
We have the value 7 at the root.
Everything to the left of 7--
if I undo all of these little marks here--
everything to the left of 7--the 3 and the 6--
those values are both less than 7, and everything to the right--which is just this 9--
is greater than 7.
>> This is not the only ordered tree containing these values,
but let's draw a few more of them.
There is actually a whole bunch of ways that we can do this.
I'm going to use a shorthand just to keep things simple where--
rather than drawing out the whole boxes-and-arrows--
I'm just going to draw the numbers and add arrows connecting them.
To start, we'll just write our original tree again where we had 7, and then a 3,
and then 3 pointed back to the right to the 6,
and 7 had a right child that was 9.
All right. What's another way that we could write this tree?
Instead of having 3 be the left child of 7,
we could also have the 6 be the left child of 7,
and then 3 be the left child of the 6.
That would look like this tree right here where I've got 7,
then 6, then 3, and a 9 on the right.
We also don't have to have 7 as our root node.
We could also have 6 as our root node.
What would that look like?
If we're going to maintain this ordered property,
everything to the left of the 6 has to be less than it.
There's only one possibility, and that's 3.
But then as the right child of 6, we have two possibilities.
First, we could have the 7 and then the 9,
or we could draw it--like I'm about to do here--
where we have the 9 as the right child of the 6,
and then the 7 as the left child of the 9.
>> Now, 7 and 6 aren't the only possible values for the root.
We could also have 3 be at the root.
What happens if 3 is at the root?
Here, things get a little bit interesting.
3 doesn't have any values that are less than it,
so that entire left side of the tree is just going to be null.
There's not going to be anything there.
To the right, we could list things in ascending order.
We could have 3, then 6, then 7, then 9.
Or, we could do 3, then 6, then 9, then 7.
Or, we could do 3, then 7, then 6, then 9.
Or, 3, 7--actually no, we can't do a 7 anymore.
That's our one thing there.
We can do 9, and then from the 9 we can do 6 and then 7.
Or, we can do 3, then 9, then 7, and then 6.
>> One thing to draw your attention to here is
that these trees are a little weird-looking.
In particular, if we look at the 4 trees on the right side--
I'll circle them, here--
these trees look almost exactly like a linked list.
Each node has only one child,
and so we don't have any of this tree-like structure that we see, for example,
in this one lone tree over here on the bottom left.
These trees are actually called degenerate binary trees,
and we'll talk about these more in the future--
especially if you go on to take other computer science courses.
These trees are degenerate.
They're not very useful because, indeed, this structure lends itself
to lookup times similar to that of a linked list.
We don't get to take advantage of the extra memory--this extra pointer--
because of our structure being bad in this way.
Rather than go on and draw out the binary trees that have 9 at the root,
which is the final case that we would have,
we're instead, at this point, going to talk a little bit about this other term
that we use when talking about trees, which is called the height.
>> The height of a tree is the distance from the root to the most-distant node,
or, rather, the number of hops that you would have to make in order to
start from the root and then end up at the most-distant node in the tree.
If we look at some of these trees that we've drawn right here,
we can see that if we take this tree in the top left corner and we start at the 3,
then we have to make one hop to get to the 6, a second hop to get to the 7,
and a third hop to get to the 9.
So, the height of this tree is 3.
We can do the same exercise for the other trees outlined with this green,
and we see that the height of all of these trees is also indeed 3.
That's part of what makes them degenerate--
that their height is just one less than the number of nodes in the entire tree.
If we look at this other tree that's encircled with red, on the other hand,
we see that the most-distant leaf nodes are the 6 and the 9--
the leaves being those nodes that have no children.
So, in order to get from the root node to either the 6 or the 9,
we have to make one hop to get to the 7 and then a second hop to get to the 9,
and likewise, only a second hop from the 7 to get to the 6.
So, the height of this tree over here is only 2.
You can go back and do that for all of the other trees that we previously discussed
beginning with the 7 and the 6,
and you'll find that the height of all of those trees is also 2.
>> The reason we've been talking about ordered binary trees
and why they're cool is because you can search through them in
a very similar way to searching over a sorted array.
This is where we talk about getting that improved lookup time
over the simple linked list.
With a linked list--if you want to find a particular element--
you're at best going to do some sort of linear search
where you start at the beginning of a list and hop one-by-one--
one node by one node--
through the entire list until you find whatever you're searching for.
Whereas, if you have a binary tree that's stored in this nice format,
you can actually get more of a binary search going on
where you divide and conquer
and search through the appropriate half of the tree at each step.
Let's see how that works.
>> If we have--again, going back to our original tree--
we start at 7, we have 3 on the left, 9 on the right,
and beneath the 3 we have the 6.
If we want to search for the number 6 in this tree, we'd start at the root.
We would compare the value we're looking for--say 6--
to the value stored in the node that we're currently looking at, 7,
find that 6 is indeed less than 7, so we'd move to the left.
If the value of 6 had been greater than 7, we would have instead moved to the right.
Since we know that--due to the structure of our ordered binary tree--
all of the values less than 7 are going to be stored to the left of 7,
there's no need to even bother looking through the right side of the tree.
Once we move to the left and we're now at the node containing 3,
we can do that same comparison again where we compare the 3 and the 6.
And we find that while 6--the value we're looking for--is greater than 3,
we can go to the right side of the node containing 3.
There's no left side here, so we could have ignored that.
But we only know that because we're looking at the tree itself,
and we can see that the tree has no children.
>> It's also pretty easy to look up 6 in this tree if we're doing it ourselves as humans,
but let's follow this process mechanically like a computer would do
to really understand the algorithm.
At this point, we're now looking at a node that contains 6,
and we're looking for the value 6,
so, indeed, we've found the appropriate node.
We found the value 6 in our tree, and we can stop our search.
At this point, depending on what's going on,
we can say yes, we have found the value 6, it exists in our tree.
Or, if we're planning to insert a node or do something, we can do that at this point.
>> Let's do a couple more lookups just to see how this works.
Let's look at what happens if we were to try and look up the value 10.
If we were to look up the value 10, we would start at the root.
We'd see that 10 is greater than 7, so we'd move to the right.
We'd get to the 9 and compare 9 to the 10 and see that 9 is indeed less than 10.
So again, we'd try to move to the right.
But at this point, we'd notice that we're at a null node.
There's nothing there. There's nothing where the 10 should be.
This is where we can report failure--that there is indeed no 10 in the tree.
And finally, let's go through the case where we're trying to look up 1 in the tree.
This is similar to what happens if we look up 10, except instead of going to the right,
we're going to go to the left.
We start at the 7 and see that 1 is less than 7, so we move to the left.
We get to the 3 and see that 1 is less than 3, so again, we try to move to the left.
At this point, we have a null node, so again we can report failure.
>> If you do want to learn more about binary trees,
there are a whole bunch of fun little problems that you can do with them.
I suggest practicing the drawing out of these diagrams one-by-one
and following through all of the different steps,
because this will come in super-handy
not only when you're doing the Huffman encoding problem set
but also in future courses--
just learning how to draw out these data structures and think through the problems
with pen and paper or, in this case, iPad and stylus.
>> At this point, though, we're going to move on to do some coding practice
and actually play with these binary trees and see.
I'm going to switch back over to my computer.
For this part of the section, instead of using CS50 Run or CS50 Spaces,
I'm going to use the appliance.
>> Following along with the problem set specification,
I see that I'm supposed to open up the appliance,
go to my Dropbox folder, create a folder called Section 7,
and then create a file called binary_tree.c.
Here we go. I've got the appliance already open.
I'm going pull up a terminal.
I'm going to go to the Dropbox folder, make a directory called section7,
and see it's totally empty.
Now I'm going to open up binary_tree.c.
Alright. Here we go--empty file.
>> Let's go back to the specification.
The specification asks to create a new type definition
for a binary tree node containing int values--
just like the values that we drew out in our diagramming before.
We're going to use this boilerplate typedef that we've done right here
that you should recognize from Problem Set 5--
if you did the hash table way of conquering the speller program.
You should also recognize it from last week's section
where we talked about linked lists.
We've got this typedef of a struct node,
and we've given this struct node this name of struct node beforehand
so that we can then refer to it since we'll want to have struct node pointers
as part of our struct, but we've then encircled this--
or rather, enclosed this--in a typedef
so that, later in the code, we can refer to this struct as just a node instead of a struct node.
>> This is going to be very similar to the singly-linked list definition that we saw last week.
To do this, let's just start by writing out the boilerplate.
We know that we have to have an integer value,
so we'll put in int value, and then instead of having just one pointer to the next element--
as we did with singly-linked lists--
we're going to have left and right child pointers.
That's pretty simple too--struct node* left_child;
and struct node* right_child;. Cool.
That looks like a pretty good start.
Let's go back to the specification.
>> Now we need to declare a global node* variable for the root of a tree.
We're going to make this global just like we made first pointer in our linked list also global.
This was so that in the functions that we write,
we don't have to keep passing around this root--
though we'll see that if you do want to write these functions recursively,
it might be better to not even pass it around as a global in the first place
and instead initialize it locally in your main function.
But, we'll do it globally to start.
Again, we'll give a couple of spaces, and I'm going to declare a node* root.
Just to make sure that I don't leave this uninitialized, I'm going to set it equal to null.
Now, in the main function--which we'll write really quickly right here--
int main(int argc, const char* argv[ ])--
and I'm going to start declaring my argv array as const just so that I know
that those arguments are arguments that I probably don't want to modify.
If I want to modify them, I should probably be making copies of them.
You'll see this a lot in code.
It's fine either way. It's fine to leave it as--omit the const if you'd like.
I typically put it in just so that I remind myself
that I probably don't want to modify those arguments.
>> As always, I'm going to include this return 0 line at the end of main.
Here, I will initialize my root node.
As it stands right now, I've got a pointer that's set to null,
so it's pointing at nothing.
In order to actually start building the node,
I first need to allocate memory for it.
I'm going to do that by making memory on the heap using malloc.
I'm going to set root equal to the result of malloc,
and I'm going to use the sizeof operator to calculate the size of a node.
The reason that I use sizeof node as opposed to, say,
doing something like this--malloc(4 + 4 +4) or malloc 12--
is because I want my code to be as compatible as possible.
I want to be able to take this .c file, compile it on the appliance,
and then compile it on my 64-bit Mac--
or on a completely different architecture--
and I want this all to work the same.
>> If I'm making assumptions about the size of variables--
the size of an int or the size of a pointer--
then I'm also making assumptions about the kinds of architectures
on which my code can successfully compile when run.
Always use sizeof as opposed to manually summing the struct fields.
The other reason is that there might also be padding that the compiler puts into the struct.
Even just summing the individual fields is not something that you typically want to do,
so, delete that line.
Now, to really initialize this root node,
I'm going to have to plug in values for each of its different fields.
For example, for value I know I want to initialize to 7,
and for now I'm going to set the left child to be null
and the right child to also be null. Great!
We've done that part of the spec.
>> The specification down at the bottom of page 3 asks me to create three more nodes--
one containing 3, one containing 6, and one with 9--
and then wire them up so it looks exactly like our tree diagram
that we were talking about previously.
Let's do that pretty quickly here.
You'll see really quickly that I'm going to start writing a bunch of duplicate code.
I'm going to create a node* and I'm going to call it three.
I'm going to set it equal to malloc(sizeof(node)).
I'm going to set three->value = 3.
Three->left_child = NULL; three->right _child = NULL; as well.
That looks pretty similar to initializing the root, and that's exactly what
I'm going to have to do if I start initializing 6 and 9 as well.
I'll do that really quickly here--actually, I'm going to do a little copy and paste,
and make sure that I--alright.
Now, I've got it copied and I can go ahead and set this equal to 6.
You can see that this takes a while and isn't super-efficient.
In just a little bit, we'll write a function that will do this for us.
I want to replace this with a 9, replace that with a 6.
>> Now we've got all of our nodes created and initialized.
We've got our root set equal to 7, or containing the value 7,
our node containing 3, our node containing 6, and our node containing 9.
At this point, all we have to do is wire everything up.
The reason I initialized all the pointers to null is just so that I make sure that
I don't have any uninitialized pointers in there by accident.
And also since, at this point, I only have to actually connect the nodes to each other--
to the ones that they're actually connected to--I don't have to go through and make
sure that all the nulls are in there in the appropriate places.
>> Starting at the root, I know that the root's left child is 3.
I know that the root's right child is 9.
After that, the only other child that I have left to worry about
is 3's right child, which is 6.
At this point, it all looks pretty good.
We'll delete some of these lines.
Now everything looks pretty good.
Let's go back to our specification and see what we have to do next.
>> At this point, we have to write a function called "contains",
with a prototype of "bool contains(int value)".
And this contains function is going to return true
if the tree pointed to by our global root variable
contains the value passed into the function and false otherwise.
Let's go ahead and do that.
This is going to be exactly like the lookup that we did by hand on the iPad just a little bit ago.
Let's zoom back in a little bit and scroll up.
We're going to put this function right above our main function
so that we don't have to do any sort of prototyping.
So, bool contains(int value).
There we go. There's our boilerplate declaration.
Just to make sure that this will compile,
I'm going to go ahead and just set it equal to return false.
Right now, this function just won't do anything and always report that
the value that we're looking for is not in the tree.
>> At this point, it's probably a good idea--
since we've written a whole bunch of code and we haven't even tried testing it yet--
to make sure that it all compiles.
There are a couple of things that we have to do to make sure that this will actually compile.
First, see if we've been using any functions in any libraries that we haven't yet included.
The functions we've used so far are malloc,
and then we've also been using this type--this nonstandard type called "bool"--
which is included in the standard bool header file.
We definitely want to include stdbool.h for the bool type,
and we also want to #include stdlib.h for the standard libraries
that include malloc and free and all of that.
So, zoom out, we're going to quit.
Let's try and make sure that this actually did compile.
We see that it does, so we're on the right track.
>> Let's open up binary_tree.c again.
It compiles. Let's go down and make sure that we insert some calls to our contains function--
just to make sure that that's all well and good.
For example, when we did some lookups in our tree earlier,
we tried to look up the values 6, 10, and 1, and we knew that 6 was in the tree,
10 was not in the tree, and 1 was not in the tree either.
Let's use those sample calls as a way to figure out whether or not
our contains function is working.
In order to do that, I'm going to use the printf function,
and we're going to print out the result of the call to contains.
I'm going to put in a string "contains(%d) = because
we're going to plug in the value that we're going to look for,
and = %s\n" and use that as our format string.
We're just going to see--literally print out on the screen--
what looks like a function call.
This isn't actually the function call.
This is just a string designed to look like a function call.
>> Now, we're going to plug in the values.
We're going to try contains on 6,
and then what we're going to do here is use that ternary operator.
Let's see--contains(6)--so, now I've contained 6 and if contains(6) is true,
the string that we're going to send to the %s format character
is going to be the string "true".
Let's scroll over a little bit.
Otherwise, we want to send the string "false" if contains(6) returns false.
This is a little goofy-looking, but I figure I might as well illustrate
what the ternary operator looks like since we haven't seen it for a while.
This will be a nice, handy way to figure out if our contains function is working.
I'm going to scroll back over to the left,
and I'm going to copy and paste this line a few times.
It changed some of these values around,
so this is going to be 1, and this is going to be 10.
>> At this point, we've got a nice contains function.
We've got some tests, and we'll see if this all works.
At this point, we've written some more code.
Time to quit out and make sure that everything still compiles.
Quit out, and now let's try making binary tree again.
Well, it looks like we've got an error,
and we've got this explicitly declaring the library function printf.
It looks like we need to go in and #include stdio.h.
And with that, everything should compile. We're all good.
Now let's try running binary tree and see what happens.
Here we are, ./binary_tree,
and we see that, as we expected--
because we haven't implemented contains yet,
or rather, we've just put in return false--
we see that it's just returning false for all of them,
so that's all working for the most part fairly well.
>> Let's go back in and actually implement contains at this point.
I'm going to scroll down, zoom in, and--
remember, the algorithm that we used was that we started at the root node
and then at each node that we encounter, we do a comparison,
and based on that comparison, we either move to the left child or to the right child.
This is going to look very similar to the binary search code that we wrote earlier in the term.
When we start off, we know that we want to hold on to the current node
that we're looking at, and the current node is going to be initialized to the root node.
And now, we're going to keep going through the tree,
and remember that our stopping condition--
when we actually worked through the example by hand--
was when we encountered a null node,
not when we looked at a null child,
but rather when we actually moved to a node in the tree
and found that we're at a null node.
We're going to iterate until cur is not equal to null.
And what are we going to do?
We're going to test if (cur->value == value),
then we know that we've actually found the node that we're looking for.
So here, we can return true.
Otherwise, we want to see whether or not the value is less than the value.
If the current node's value is less than the value we're looking for,
we're going to move to the right.
So, cur = cur->right_child; and otherwise, we're going to move to the left.
cur = cur->left_child;. Pretty simple.
>> You probably recognize the loop that looks very similar to this from
binary search earlier in the term, except then we were dealing with low, mid, and high.
Here, we just have to look at a current value,
so it's nice and simple.
Let's make sure this code is working.
First, make sure it compiles. Looks like it does.
Let's try running it.
And indeed, it prints out everything that we expected.
It finds 6 in the tree, doesn't find 10 because 10's not in the tree,
and doesn't find 1 either because 1's also not in the tree.
Cool stuff.
>> All rright. Let's go back to our specification and see what's next.
Now, it wants to add some more nodes to our tree.
It wants to add 5, 2, and 8, and make sure that our contains code
still works as expected.
Let's go do that.
At this point, rather than doing that annoying copy and paste again,
let's write a function to actually create a node.
If we scroll down all the way to main, we see that we've been doing this
very similar code over and over again each time that we want to create a node.
>> Let's write a function that will actually build a node for us and return it.
I'm going to call it build_node.
I'm going to build a node with a particular value.
Zoom in here.
The first thing I'm going to do is actually create space for the node on the heap.
So, node* n = malloc(sizeof(node)); n->value = value;
and then here, I'm just going to initialize all of the fields to be appropriate values.
And at the very end, we'll return our node.
All right. One thing to note is that this function right here
is going to return a pointer to memory that has been heap-allocated.
What's nice about this is that this node now--
we have to declare it on the heap because if we declared it on the stack,
we wouldn't be able to do it in this function like this.
That memory would go out of scope
and would be invalid if we tried to access it later on.
Since we are declaring heap-allocated memory,
we are going to have to take care of freeing it later
for our program to not leak any memory.
We've been punting on that for everything else in the code
just for simplicity's sake at the time,
but if you ever write a function that looks like this
where you've got--some call it a malloc or realloc inside--
you want to make sure that you put some sort of comment up here that says,
hey, you know, returns a heap-allocated node initialized with the passed-in value.
And then you want to make sure that you put in some sort of note that says
the caller must free the returned memory.
That way, if somebody ever goes and uses that function,
they know that whatever they get back from that function
at some point will need to be freed.
>> Assuming that all is well and good here,
we can go down into our code and replace all of these lines right here
with calls to our build node function.
Let's do that really quickly.
The one part that we're not going to replace is this part down here
at the bottom where we actually wire up the nodes to point to each other,
because that we can't do in our function.
But, let's do root = build_node(7); node* three = build_node(3);
node* six = build_node(6); node* nine = build_node(9);.
And now, we also wanted to add nodes for--
node* five = build_node(5); node* eight = build_node(8);
and what was the other node? Let's see here. We wanted to also add a 2--
node* two = build_node(2);.
All right. At this point, we know that we've got the 7, the 3, the 9, and the 6
all wired up appropriately, but what about the 5, the 8, and the 2?
To keep everything in the appropriate order,
we know that three's right child is 6.
So, if we're going to add the 5,
the 5 also belongs in the right side of the tree of which 3 is the root,
so 5 belongs as the left child of 6.
We can do this by saying, six->left_child = five;
and then the 8 belongs as the left child of 9, so nine->left_child = eight;
and then 2 is the left child of 3, so we can do that up here--three->left_child = two;.
If you didn't quite follow along with that, I suggest you draw it out yourself.
>> All right. Let's save this. Let's go out and make sure it compiles,
and then we can add in our contains calls.
Looks like everything still compiles.
Let's go in and add in some contains calls.
Again, I'm going to do a little bit of copy and paste.
Now let's search for 5, 8, and 2. Alright.
Let's make sure that this all looks good still. Great! Save and quit.
Now let's make, compile, and now let's run.
From the results, it looks like everything is working just nice and well.
Great! So now we've got our contains function written.
Let's move on and start working on how to insert nodes into the tree
since, as we're doing it right now, things aren't very pretty.
>> If we go back to the specification,
it asks us to write a function called insert--again, returning a bool
for whether or not we could actually insert the node into the tree--
and then the value to insert into the tree is specified as
the only argument to our insert function.
We will return true if we could indeed insert the node containing value into the tree,
which means that we, one, had enough memory,
and then, two, that node didn't already exist in the tree since--
remember, we are not going to have duplicate values in the tree, just to make things simple.
All right. Back to the code.
Open it up. Zoom in a bit, then scroll down.
Let's put the insert function right above the contains.
Again, it's going to be called bool insert(int value).
Give it a little more space, and then, as a default,
let's put in return false at the very end.
Now down at the bottom, let's go ahead and instead of manually building the nodes
in main ourselves and wiring them up to point to each other like we're doing,
we'll rely on our insert function to do that.
We won't rely on our insert function to build the entire tree from scratch just yet,
but rather, we'll get rid of these lines--we'll comment out these lines--
that build the nodes 5, 8, and 2.
And instead, we'll insert calls to our insert function
to make sure that that actually works.
Here we go.
>> Now we've commented out these lines.
We only have 7, 3, 9, and 6 in our tree at this point.
To make sure that this is all working,
we can zoom out, make our binary tree,
run it, and we can see that contains is now telling us that we're totally right--
5, 8, and 2 are no longer in the tree.
Go back into the code,
and how are we going to insert?
Remember what we did when we were actually inserting 5, 8, and 2 previously.
We played that Plinko game where we started at the root,
went down the tree one by one by one
until we found the appropriate gap,
and then we wired in the node at the appropriate spot.
We're going to do the same thing.
This is basically like writing the code that we used in the contains function
to find the spot where the node should be,
and then we're just going to insert the node right there.
Let's start doing that.
>> So we have a node* cur = root; we're just going to follow the contains code
until we find that it doesn't quite work for us.
We're going to go through the tree while the current element is not null,
and if we find that cur's value is equal to the value that we're trying to insert--
well, this is one of the cases in which we couldn't actually insert the node
into the tree because this means we have a duplicate value.
Here, we're actually going to return false.
Now, else if cur's value is less than value,
now we know that we move to the right
because the value belongs in the right half of the cur tree.
Otherwise, we're going to move to the left.
That's basically our contains function right there.
>> At this point, once we've completed this while loop,
our cur pointer is going to be pointing to null
if the function hasn't already returned.
We're therefore having cur at the spot where we want to insert the new node.
What remains to be done is to actually build the new node,
which we can do pretty easily.
We can use our super-handy build_node function,
and something that we didn't do earlier--
we just kind of took for granted, but now we'll do just to make sure--
we'll test to make sure that the value returned by new_node was actually
not null, because we don't want to start accessing that memory if it is null.
We can test to make sure that new_node is not equal to null.
Or instead, we can just see if it actually is null,
and if it is null, then we can just return false early.
>> At this point, we have to wire new-node into its appropriate spot in the tree.
If we look back at main and where we were actually wiring in values before,
we see that the way we were doing it when we wanted to put 3 in the tree
was we accessed the left child of root.
When we put 9 in the tree, we had to access the right child of the root.
We had to have a pointer to the parent in order to put a new value into the tree.
Scrolling back up to insert, that's not going to quite work here
because we don't have a parent pointer.
What we want to be able to do is, at this point,
check the parent's value and see--well, gosh,
if the parent's value is less than the current value,
then the parent's right child should be the new node;
otherwise, the parent's left child should be the new node.
But we don't have this parent pointer quite yet.
>> In order to get it, we're actually going to have to track it as we go through the tree
and find the appropriate spot in our loop above.
We can do that by scrolling back up to the top of our insert function
and tracking another pointer variable called the parent.
We're going to set it equal to null initially,
and then every time we go through the tree,
we're going to set the parent pointer to match the current pointer.
Set parent equal to cur.
This way, each time we go through,
we're going to ensure that as the current pointer gets incremented,
the parent pointer follows it--just one level higher than the current pointer in the tree.
That all looks pretty good.
>> I think the one thing that we'll want to adjust is this build_node returning null.
In order to get build_node to actually successfully return null,
we'll have to modify that code,
because here, we never tested to make sure that malloc returned a valid pointer.
So, if (n != NULL), then--
if malloc returned a valid pointer, then we'll initialize it;
otherwise, we'll just return and that will end up returning null for us.
Now all looks pretty good. Let's make sure this actually compiles.
Make binary_tree, and oh, we've got some stuff going on here.
>> We've got an implicit declaration of function build_node.
Again, with these compilers, we're going to start at the top.
What that must mean is that I'm calling build_node before I've actually declared it.
Let's go back to the code really quickly.
Scroll down, and sure enough, my insert function is declared
above the build_node function,
but I'm trying to use build_node inside of insert.
I'm going to go in and copy and then paste the build_node function way up here at the top.
That way, hopefully, that will work. Let's give this another go.
Now it all compiles. All is good.
>> But at this point, we haven't actually called our insert function.
We just know that it compiles, so let's go in and put some calls in.
Let's do that in our main function.
Here, we commented out 5, 8, and 2,
and then we didn't wire them up down here.
Let's make some calls to insert,
and let's also use the same kind of stuff that we used
when we made these printf calls to make sure that everything did get inserted properly.
I'm going to copy and paste,
and instead of contains, we're going to do insert.
And instead of 6, 10, and 1, we're going to use 5, 8, and 2.
This should hopefully insert 5, 8, and 2 into the tree.
Compile. All is good. Now we'll actually run our program.
>> Everything returned false.
So, 5, 8, and 2 did not go, and it looks like contains didn't find them either.
What's going on? Let's zoom out.
The first problem was that insert seemed to return false,
and it looks like that's because we left in our return false call,
and we never actually returned true.
We can set that up.
The second problem is now even if we do--save this, quit this,
run make again, have it compile, then run it--
we see that something else happened here.
The 5, 8, and 2 were still never found in the tree.
So what's going on?
>> Let's take a look at this in the code.
Let's see if we can figure this out.
We start with the parent not being null.
We set the current pointer equal to the root pointer,
and we're going to work our way down through the tree.
If the current node isn't null, then we know that we can move down a little bit.
We set our parent pointer to be equal to the current pointer,
checked the value--if the values are the same, we returned false.
If the values are less, we moved to the right;
otherwise, we moved to the left.
Then we build a node. I'll zoom in a little bit.
And here, we're going to try to wire up the values to be the same.
What's going on? Let's see if possibly Valgrind can give us a hint.
>> I like to use Valgrind just because Valgrind really quickly runs
and tells you if there are any memory errors.
When we run Valgrind on the code,
as you can see right here--Valgrind./binary_tree--and hit Enter.
You see that we didn't have any memory error, so it looks like everything's okay so far.
We do have some memory leaks, which we know because we're not
happening to free any of our nodes.
Let's try running GDB to see what's actually going on.
We'll do gdb ./binary_tree. It booted up just fine.
Let's set a break point on insert.
Let's run.
It looks like we never actually called insert.
It looks like the problem was just that when I changed down here in main--
all of these printf calls from contains--
I never actually changed these to call insert.
Now let's give it a try. Let's compile.
All looks good there. Now let's try running it, see what happens.
All right! Everything looks pretty good there.
>> The final thing to think about is are there any edge cases to this insert?
And it turns out that, well, the one edge case that is always interesting to think about
is what happens if your tree is empty and you call this insert function?
Will it work? Well, let's give it a try.
--binary_tree.c--
The way we're going to test this is we're going to go down to our main function,
and rather than wiring these nodes up like this,
we're just going to comment out the entire thing,
and instead of wiring up the nodes ourselves,
we can actually just go ahead and delete all of this.
We're going to make everything a call to insert.
So, let's do--instead of 5, 8, and 2, we're going to insert 7, 3, and 9.
And then we'll also want to insert 6 as well.
Save. Quit. Make binary_tree.
It all compiles.
We can just run it as is and see what happens,
but it's also going to be really important to make sure that
we don't have any memory errors,
since this is one of our edge cases that we know about.
>> Let's make sure that it works well under Valgrind,
which we'll do by just running Valgrind ./binary_tree.
It looks like we indeed have one error from one context--
we have this segmentation fault.
What happened?
Valgrind actually tells us where it is.
Zoom out a little bit.
It looks like it's happening in our insert function,
where we have an invalid read of size 4 at insert, line 60.
Let's go back and see what's going on here.
Zoom out really quick.
I want to make sure that it doesn't go to the edge of the screen so we can see everything.
Pull that in a little bit. All right.
Scroll down, and the problem is right here.
What happens if we get down and our current node is already null,
our parent node is null, so if we look up at the very top, right here--
if this while loop never actually executes
because our current value is null--our root is null, so cur is null--
then our parent never gets set to cur or to a valid value,
so parent will also be null.
We need to remember to check for that
by the time we get down here and we start accessing the parent's value.
So what happens? Well, if the parent is null--
if (parent == NULL)--then we know that
there must not be anything in the tree.
We must be trying to insert it at the root.
We can do that by just setting the root equal to the new node.
Then, at this point, we don't actually want to go through these other things.
Instead, right here, we can do either an else-if-else,
or we could combine everything up here in an else,
but here, we'll just use else and do it that way.
Now, we're going to test to make sure that our parent is not null
before then actually trying to access its fields.
This will help us avoid the segmentation fault.
So, we quit, zoom out, compile, run.
>> No errors, but we still have a bunch of memory leaks
because we didn't free any of our nodes.
But if we go up here and we look at our printout,
we see that, well, looks like all of our inserts were returning true, which is good.
The inserts are all true,
and then the appropriate contains calls are also true.
>> Good job! It looks like we've successfully written insert.
That's all we have for this week's problem set specification.
One fun challenge to think about is how you would actually go in
and free all of the nodes in this tree.
We can do so a number of different ways,
but I'll leave that up to you to experiment,
and as a fun challenge, try and make sure that you can make sure
that this Valgrind report returns no errors and no leaks.
>> Good luck on this week's Huffman coding problem set,
and we'll see you next week!
[CS50.TV]