Binary Search Tree Q&A

[00:00:00]
>> All right, so how do we feel about that? Do we have any quick questions, or slow questions, or moderate questions? Question in the back?
>> After addition will it still be balanced?
>> Say that, after addition? After insertion? After insertion will it still be balanced? No, there's no guarantee that things are gonna be balanced after insertion.

[00:00:22]
Insertion inherently unbalances a tree, right? That is where these rotation algorithms come into play. ADL versus red black, .I don't know red black by heart, obviously involves coloring like you can't have two reds touching each other. I forget the exact way you do the balancing, .but an AVL effectively defines four things that you can see, and it goes over each one of the possible cases and how you rotate it.

[00:00:49]
So if you insert something, you walk back up the tree. If you run into a situation in which you have a parent and a child, and they're both on the left hand side, then you can do a rotation in which will make this a shorter tree. And it does this recursively back up the tree.

[00:01:05]
And that's an AVL algorithm, it does that on insertion and helps bring everything back up and closer. And it actually causes an extremely balanced tree. It's like almost always perfectly balanced. It's a very impressive algorithm, but it leads to more rotations, more rotations, slower algorithm. You have to be able to say, hey, if I don't find that often but I insert a lot, it's better to have red black, but if I say find a lot and insert rarely, perhaps AVL is a better choice.

[00:01:32]
So there's no one straight answer, again, as always it's just this constant, well, it depends. All right, we have another question?
>> So basically, it's possible to remove the same node but while choosing a different strategy, we can end up with a different tree.
>> Yeah, exactly. So as I said, the deletion I left it open to you, I gave you two separate pathways to walk.

[00:01:55]
You find the largest on the small side or the smallest on the large side, and then you replace that parent node in which you were removing or the removal node. So that will fundamentally lead to two separate trees. Right, they gonna be different in shape So in this case, if we were to do it over here, say we didn't have this one, we would have put 37 right here.

[00:02:21]
If we would have gone the other direction, we would have put 100 right here. And yes, the shape of the tree would have been preserved in both cases, everything would have been great, everything on this side of 100 would have been larger, everything on this side would have been smaller.

[00:02:35]
If we would have put 37 there, everything would have been larger cuz it's 100 on the other side, everything would have been smaller cuz it's 25 on the other side. So both cases preserve the shape of the tree, they just lead to two different trees
>> Larger than and less than the value, is that the only way you can make a tree?

[00:02:49]
>> Ooh, okay, yes so the question was this whole larger than less than thing is this the only way you can make a tree? No, we're actually gonna be doing a week ordered tree next, and it's gonna be slightly different. But for a binary search tree, there is only really one configuration.

[00:03:04]
It's meant to mimic a binary search of an array or quicksort where we have this strong ordering to things, right? Meaning that if you were to look at this, so check this out, so don't mind all the crossing out. Let's just print out the tree in order. So in order remember, we go left, print out the value, go right.

[00:03:25]
So we go left, go left, go left to 4, go back up cuz there's no more children, print out 7. Go back up 15, go down, go left 25, right? Go that little extra right 37, go back up 51, go to the right 100, right? So it actually prints it out in order.

[00:03:50]
There's a very strict ordering to this tree and in order traversal produces an in order array. It's cool property, right? So, that's why you put this up more in the strict ordering phase than the weak ordering phase or strong ordering, might be a better term than strict.