Welcome to a nother lecture on anvil trees in this lecture, we will be doing some implementation of
the code and I will not be going over a theoretical things in this portion.
But when we do a second part of our implementation, I will refer back to some images that we've looked
at some slides just so we can get a better grasp of what it is that we're doing and kind of switch back
and forth so we can see why we're writing the code that we're writing.
And so if you were if you're still actually a little bit confused about the rotations and things and
movement of the pointers and restructuring the tree, don't worry about it.
We will look even in more detail when we are writing the code for these rotations.
I will include some slides that show exactly what we're doing when we're writing this line of code.
So don't worry about that.
If it's still a little confusing, we kind of just took a general look at that tree and there were some
arrows and stuff, but it might still be unclear.
So hopefully I can clear that up for you in the next lecture.
But today we're just going to do kind of a little bit of a scaffolding for what we're going to need
for the real tree, some helper functions and things like that.
So I went ahead and made a new project.
You see, it's a real tree record.
If you would like to, you can kind of piggyback off of your binary search tree, and that's totally
fine.
I went ahead and already made a few files, so I have a header file for my node class.
I have a header file for the actual Avielle tree class and then an implementation for each class.
And you're probably wondering unless you've already done something like this, why is there no implementation
for the node class?
And we will see that right here, and it's because I'm going to actually do the implementation in the
header.
So a few things I'm going to show in this lecture that you may or may not have seen before.
They're just kind of style and syntax things.
I kind of want my node class to be compact in the header.
So I'm just going to put the implementation there, since the implementations are very simple for these
functions.
So I will have it kind of prototyped and implemented in the same area in the class.
So that's another way of writing code and C++ if you haven't done that before.
If you have, you can just ignore what I'm saying, and I'm also going to go over a tune things that
might be new in C++ for you if you haven't gone over them before and the previous portion of this course
or just in your own studies.
And that'll be initialization lists and ternary operator.
So or sorry ternary statements.
So I will go ahead and get started then.
So what I'm going to do is actually commit to using namespace STD.
And I'm going to, I think, increase the size a little bit in this video.
I'm hoping that the previous recordings weren't too small, but from now on, I'm going to try and write
code kind of like in the biggest size that's usable for me, just so it's as visible as possible.
So hopefully that hasn't been an issue till now and that it's been big enough.
But you know, I'm trying to increase the size for sure.
All right.
So let's go ahead and make our class name for Node and I'll do a public section.
And this is one of the things that I was talking about, right?
The constructor here.
And it's not just going to be a prototype, it's going to be the implementation as well.
And I'm going to do it in the form of what is called an initialization list.
So it's just a more compact syntax for writing and constructor.
And that looks like this.
So it's you write, what would you normally write for the prototype, something like this node?
And then you put a colon and then you're basically going to write a list of the things to be initialized
and use parentheses for it like this.
So I haven't written my private members yet, so it's probably going to be underlined in red for sure.
Will be, but I'm just going to start writing that right now and now implement them after I write this.
Sorry, I'll declare them in the private section.
So I'm going to have a left pointer off my node, just like binary search tree.
And I'm initialize that and no pointer and like this.
So I say left and then in parentheses, I put no pointer and then a comma, and we continue our list.
I'm going to have a right.
I do know pointer like that, and then I'm going to have the value for the data, and I just can call
that underscore value and initialize that to zero.
And then we.
Finish it off with just some empty brackets here, and they don't have to be empty and they can actually
have.
Things inside of this like more implementation inside here, but I don't need that, so I'm just putting
an empty right there.
All right.
So since I don't like that underline now I'm going to go ahead and just write this year, so we have
a no pointer called left.
We have A. pointer and call right.
And we have an integer on a core value.
So that way it's not underlined anymore.
I'm going to make another constructor that gets past the value to initialize them and do the same thing
with my initialization list here.
I'm going to have left a no pointer.
In fact, you know what?
I will just copy the.
Rest of this office, and I'm going to have this value be in, which is passed there.
OK, so now I have another constructor there, then I'm going to do my setters and getters for these
nodes so we can set the sub trees and I'm going to call this left sub tree.
This will be the getter, so it turns left.
And another thing for right some tree we saw in Karen's right, then I'll have the setters that get
passed and node pointer and this will be left.
And since I'm putting left in here, I'm going to have something like this.
This uses the calling object with the keyword.
This and I see this arrow left equals the path to left.
Same thing for their right.
So that's right.
And I forgot the semicolon there.
So let's finish that.
Then we'll get all right.
We'll do a getter accessory for our value.
So I have that there and then I'll do a setter to set value.
I should probably continue the camel case here, so I'll do that.
Well, yeah, this will be on.
I'll pass the contest and now and I'll just say value equals style.
Oops.
OK, so that's be pretty much it for our Noad class.
Yeah.
So let's go ahead and head over to our email tree.
Header file So for this, I'm going to want to include the let's see what I include my class and then
I think, yeah, it's all wrinkly right now.
Put that in there for the sake of it.
Let's say class Avielle Tree
of Public section.
I'm going to have a basic constructor then and I'm going to have a function.
We're going to need a function, actually, so we can calculate our balance factors and stuff.
We're going to need a function that helps facilitate that card height.
And I'll be explaining this a little bit.
I'm not going to be showing a visualization of this lake, but it will be a recursive function and I'm
trying to explain it to the best of my ability, the implementation when we're doing it.
But this is something that I recommend you trying to see if you can figure out how to write on yourself
by yourself and try and figure out what you would do for a recursive function to find the height of
a binary search tree.
So I will be implementing it and explaining it, but it would be good practice to see if you can implement
it before I explain it.
Also going to have the balance factor, of course, that will return the balance factor.
I'm actually going to go back there and continue the camel case.
This will be passed a route to find the balance factor of.
And then I'm going to prototype my other functions here, but I'm not going to implement them in this
lecture, but I'm going to have all the rotations and these are going to return a node.
So I'm going to say L-l rotation and I'm going to call this in real life movie and we'll do L-R rotation
with this, our location
and our El rotation.
OK.
And then I'm, of course, going to want some functions to insert into the tree.
So.
Yeah, we want to call this
insert the value that this will be kind of the public facing one and then I'll have and local one that
returns and then I call that local and state and that gets passed a root node to start at and p value.
OK.
And then in my private section, I'm pretty much only having the root of the tree right now.
And that should be good.
So, yeah, let's go ahead and move over to the implementation file.
So we're going to definitely need to include our header files, so I'm going to include a real tree
and I'll include my node
in each.
And I know at some point I'm going to be writing a function to print out the tree in some order.
We're using like one of those reversals and printing out, and so I'm going to include extreme,
but that and then left to our constructor.
So I'm not going to do an initialization list for this and just going to do a basic one.
But you can definitely do an edit initialization list if you'd like.
So let's talk about this height function now.
So.
How do we find the height of a binary search tree, so I definitely think that it's a good idea to see
if you can figure this out on your own and if it's too crazy and you get stuck, don't worry.
But definitely, you know, congratulations if you're able to figure it out.
Go ahead and pass the video if you want to do that.
Otherwise, I'm going to explain it right now.
So if you think about the height of a binary search tree and how to figure that out, we basically need
to count the nodes during the recursive process so we go all the way down to a leaf node, whether that
be, you know, taking whatever path.
We want to go all the way down to all the leaf nodes and explore.
And we're talking about when we say the height, we're talking about the max depth.
That's kind of another way that you could call this function.
We want to have the longest path from a given node.
You know, the node route that's being passed is an argument.
That's one of the parameters from that node, any given node.
We want to find the longest path, you know, whether that's taking whatever combination of left and
right turns from the route to go down to Alif node.
And so how do we do that?
Well, since we need to count during that recursive process?
We basically need to dig down to each left sub tree, and even though I talked about not really using
local variables inside of a function, we are in fact going to be able to use that and leverage that
somehow in this function.
And we're going to need to save the height of each left sub tree and the height of each right sub tree.
Then we're going to want to find which one is bigger.
And basically, you know, if one is bigger, if the left is bigger than the right, we're going to
want to return the left value plus one during our recursive phase.
Is it going to be adding one each time we come up from a non null?
No, you know, and otherwise, you know, we'll return there to the right one plus one, so it's basically
like finding which one is a larger path.
So you can think about it as we dig all the way to the bottom of all these like past recursively.
And then as we come up in the recursive phase, we're going to be adding one each time if it's not null,
if it's no, our base case is just going to be to return to zero, so we won't add anything.
And we're checking when we add one.
We're only adding one to whatever the biggest number is so far, whether it was coming from the right
or coming from the left.
So that's how we're going to do this.
Some must start out with that base case, and I must say if the route is well, not is no point.
The route is, you know, Poyner can't spell right now.
Go ahead and just return zero because we're not going to add anything in that case.
Then we're going to say I've put a variable here instead of equal to so this can be left into a recursive
call.
It goes to the left so left tree and then we're going to do a recursive call that goes to the right
and that's going to be the right century.
And then we do our check here.
So if left is greater than right, then return left +1.
So we're going to keep that number that's been recursively returned to the X frame that we're at and
we'll add another one to it.
And it will return back up to its parent node, which is also, you know, the previous stack frame
that was calling it before.
So, you know, and then the other case, if it's not, then we want to instead return, right?
Plus one, because that contains that means that right contains the longest path like the count of the
longest path so far, coming back up recursively from the bottom.
And it's as simple as that, actually.
That's all I need.
So if you want to, you can go ahead and make a small example for this function and draw it out on paper,
draw the recursive tree, the tree of the records of calls or just a binary search tree, you know?
You know, they're kind of synonymous in the case of binary search tree and recursive tree, you know,
because we can think of the actual nodes that we're at since we're just traversing the tree recursively,
the nose kind of double as the stack frames, which you've probably noticed so far since I've been talking
about it in that way.
So go ahead and draw that out and just kind of see if you can make sense of a small example of a tree
where you come back up and kind of add values to left and right and keep track of that recursive process
that'll definitely help you understand it and visualize it.
All right.
So now that we got that out of the way, let's go ahead and write the code for our balance factor functions.
So this is going to be a real tree, and I'm going to say, oops, not capital balance factor.
And for the balance factor, I'm going to need the height of the left and the height of the right,
because remember, we get our balance factor by subtracting the height of the right from the left.
So I'm going to say age left and age right.
And what I'm going to say actually is I'm going to say if Root, which is basically just seen, if it's
not if the roots, not null pointer and if it's not null pointer, then I'm going to say if the sub
tree is not no, then set the left or right height to the sub tree.
Otherwise we're going to set it to zero.
And so that is going to I'm going to actually do this in the form of a ternary.
So if you haven't done turn areas before, don't worry, I'm going to explain them right now.
If you have, then you know, this is going to be nothing new to you, but it set a variable.
We have our height left, which is an integer, and I'm basically going to say, OK, so if the left
sub tree is not know which, all I have to do is say if root left sub tree.
So that's basically, you know, asking, you know, is it null or not?
You can just put it as a condition there, just like we did with f root.
And then I put a question mark and then I say, OK, you know, if it's not, no.
If Root left some tree, then I'm going to call the hate function and pass it the left sub tree.
Otherwise, you know, if it is null, I'm just going to say to zero.
And so, you know, if this evaluates to true right here.
Then it's going to take this value.
So this is kind of like the what the question symbolizes and, you know, if it's like the else is kind
of what comes after the colon, which is zero so zero will get put in here.
You know, if it's the condition, this will get put into this variable.
If it's the, you know, if the if is satisfied, if this condition satisfied and you can actually turn
it back and forth here, like, let's see if I can get it to pop up here.
So you notice I click on a little light bulb, it says replace this turn area with, if else so that
basically this is what it would look like as an if else.
And then I kind of can go back to here to this light bulb and I'll return it back to turn so you can
toggle back and forth with C Line, which is kind of nice.
But I just like it, it's kind of a more compact thing, just like the initialization list, so I just
want to mention it in case people didn't know it already.
Let's go ahead and do it for the right century then or sorry, our right value.
So let's do it right.
Some tree.
Question mark height.
Fruit.
Right century.
Otherwise zero.
Cool.
And then, of course, our balance factor is going to, you know, we're getting the height and saving
it in these variables and then we're going to return the difference.
So from each left, we actually specifically want the height of the left sub tree minus the high rates
of tree.
So pretty simple there.
That's all we got for our balance factor function.
And I am actually going to cut the video off here.
I think the next video is going to be all about inserting and doing the rotations, so we're going to
cover all those functions, and I kind of want just a full video dedicated to that.
I'm going to bring up some visualizations that are actually a little more fine tuned in detail than
what we went over in that theoretical first lecture about real trees.
And so I'm hoping it'll really help you clear up any misunderstandings or confusion you might have had
with it so far.
OK, so with that, I will see you in the next video.