Depth-First: Insert

[00:00:00]
>> So, hey, you know what? What happened if we inserted 51? All right, so let's do this. So the insertion algorithm, or actually before we do that, let's quickly do the find algorithm. What is the running time of the find algorithm? It's a bit tricky. So your probably gut instinct is to say something along the lines of log n, right?

[00:00:23]
We're effectively splitting our input in half every single time. It's not quite accurate. Up we have a question.
>> n log n.
>> n log n? No, because we do not visit every node. So the n would require us to visit every node and we'd have to visit it a log n amount of times.

[00:00:43]
So we're not gonna be doing that. That's a good guess, though. At least, you got the n log n part, right? Gut check, good, you did that.
>> Worst case is o of n, right?
>> Yes, in this case, the worst case is o of n with this.

[00:00:57]
But we usually don't measure it in o of n, what we'll actually measure it in is o of height. What is the height of our tree? That is going to be our running time cuz if you have a really long single track tree, the height is n. If you have a complete binary tree, the height is log n.

[00:01:17]
Just like QuickSort, it's gonna be somewhere between log n to n. It has its own range for find. Just like QuickSort went from n log n to n squared, this thing has a very similar type of property to it, where it has a range depending on how balanced your binary tree is.

[00:01:35]
And so this goes into an entire, you could do a whole three hour thing on different ways in which you can balance a tree. The two predominant ones are AVL and Red-Black Trees. Red-Black fun fact, the reason why it's called the Red-Black Tree is because printers back in the 70s printed red and black phenomenally, and nothing else good.

[00:01:55]
So therefore, it was Red-Black Tree cuz that's the only two colors you could print well. It's just a fun fact. I don't know, those kind of things just bring joy to my heart knowing that getting named by legacy just hurts a little bit. So there we go. So that is a find, we now know the running time, awesome.

[00:02:13]
Let's move on and do insert. So let's talk about insertion. So insertion is a lot like find, right? You effectively kinda have to find your way to a node, correct? Yeah, so if I were to insert, let's say we're gonna insert, we could insert 17. So let's start with that cuz that's kinda a goofy case, right?

[00:02:37]
Because our root node is a 17, right? Well, your first gut instinct is, man, how do we replace 15 with 17, right? And then we're gonna have to bubble it down and do these type of operations? Well, no, you don't have to do that. Cuz remember, long as we adhere to these simple principles, we will be able to just insert it.

[00:02:58]
And of course, remember right now we're only considering it like that. There we go. So that means when we insert 17, we say, hey, am I larger than or smaller than you? Or am I larger than you or smaller than or equal to you? If I'm smaller than or equal to, I'll just go on this side.

[00:03:14]
Hey, am I larger than or smaller than or equal to you? I'm larger than, so let's go on this side. Hey, am I larger than or smaller than or equal to? I'm larger than, so 17 would actually put, my goodness, I just realized I completely ran out of room.

[00:03:27]
I think, is it E? No, it's definitely not E. Is it Shift+N? My goodness, I'm sorry, I was just trying to guess what the eraser was. What is the eraser? Do I know? I don't even know. All right, so I'm just gonna pretend like that doesn't exist. [SOUND] Don't tell the man behind the curtain.

[00:03:47]
All right, look at that. Boom, we just drew 17 in there. Awesome, so 17 was inserted way down there. So again, ask ourselves how do we preserve the rule of the binary tree? Is this entire subtree less than or equal to, The node above it. Yes, it is.

[00:04:08]
The entire thing is less than or equal to. The 17 can still be put here, it can still be preserved in this case. If the value is 18, it would have trickled down, it would have started here. Then it would have gone to the larger section. Then it would have gone to the smaller section.

[00:04:21]
It would have gone to the smaller section and effectively been inserted on this side of the node, right? Right, they don't actually match up to the same spot. It's just I ran out of room to actually draw it in. So that, I mean, if I were to draw it more correctly, it would look something like [SOUND].

[00:04:40]
There we go, right? It would have been on that side of the node as a 18. So insertion is actually really easy cuz it's a version of find, we do the same type of traversal, we just have to keep going until we hit a point in which is null.

[00:04:53]
So we could really do this pretty easily. We'll write out the pseudocode for insertion, just because insertion tends to be a pretty easy operation to do. So insert, which is gonna take in the node, and the value. And so we'll simply do this. If, or I should have called that n, n.value is greater than the current, which is not that way, is less than our current value.

[00:05:19]
We need to travel left. I mean, we need to travel right, right? Yes, we need to travel right because we are bigger, we go on the bigger side. So then we go insert node, right, with our value. Awesome. Else, we just travelled the other direction, right? So we'll call it, else if node new, node.value is this, then we can go the other side, right?

[00:05:53]
Insert, and we'll take in a node v, not node v, what am I doing? A node left and the value. But there is one problem that I left here on purpose. We have to make a decision here. What do we do in the null case? We need to do something in the null case.

[00:06:15]
We have to be putting something either in the function signature or we have to create a node as we go there, right? It'd probably be easier to add in something into the function signature. So if we added in parent, we'd be able to go, hey, we've hit a null point, go back to the parent, and let's add ourselves in at this point.

[00:06:35]
Or b, we could check right here and be like, hey, we want to go to the right hand side. But the right hand, or is this, yeah, we want to go to the right hand side but the right hand side is null. Therefore, we insert ourselves in. So this kinda breaks the first two base case, then due to the recurse check, this is just kinda broken in that way cuz you have to make this decision at the base case point to mutate the tree.

[00:07:00]
And so it kinda causes this goofiness that's a little bit harder to do. So if I were to rewrite this in a sense that does that that mixes both the base case plus this, it would look something more like this. If node value is greater than or, oopsies, is less than value, then I'd have to check if not node right, then actually do the insertion, right?

[00:07:30]
Which would involve creating a node, setting the right hand pointer to be this node, etc. Or we traverse again, we recall, traverse, right? Or else we call this whole insert function again and walk. And so it's a little bit different in the sense that we have to mix the base case with the recursion step.

[00:07:50]
You don't really like it, it gets a little bit more complicated. Hence, the reason like I said, why this gets really hairy really, really fast is you start running into these weird kinda conditions.