All language subtitles for 20 - How to Delete a Node from a Red Black Tree English

High in this video we're going to go through how to delete notes from a red black tree.

If you watch the previous video on the properties of red black trees and how to insert that would be

a good basis for understanding how to remove these nodes because it's very important to understand the

properties of the red black tree because if you don't know that then you're not going to know what steps

we need to take in order to rebalance after a node has been deleted.

And so I'm going to go through some exercises here and we can see exactly how the process works on an

animated basis.

So first I'm going to show you what happens when we delete the root node.

So you can see that root node is 16.

And so when we delete this you can see it looks at 16 and then it traverses the tree all the way down

to 15 and then readjusts and now it makes 14 be connected to a node leaf and then it readjusts at all

so that it restores the balance and brings that 12 up so now 12 points to 10 which is less than 12 and

14.

And you can see how that automatically balances.

Now if we want to remove 21 which you can see is the parent to 18 and 25 you can probably guess how

it's going to work but it's going to start at the root then iterate through and find 21.

It's going to swap places with 18 and 17.

And now you know that you have to swap out the colors because you can't have any red nodes connected

to any other red nodes and so that was a pretty easy one right there.

And now let's take 55 out.

So we'll delete 55.

It goes to 15 then it finds 55 and it goes down the list to find the highest value closest to it.

It swaps that out.

You can't see it in animation but it you know puts a no leaf connected to 25.

And so you can see with each deletion the tree automatically rebalances and a user uses a recursive

algorithm to make that possible.

And so now we're going to take down 95 and you'll see 95 is a red Knodell all the way are almost all

the way the right.

So let's go look at ninety five.

Then it's go.

Compare that with 66.

Swap out those values and readjust itself.

And see we'll just do two more we'll take out the root note again and see how that works.

It's going to do the same thing it did before where it looks at 15 goes to the left side of the tree

swaps it with 14.

And now we're going to have 14 12 and 10 and it's going to swap out 10 so that's a red note.

And now because we wouldn't want to have a tree just with a single line like that you can see the entire

tree gets completely reassembled 18 becomes the new root node and you have a much more balanced tree.

If you noticed you were going to have 14 12 and 10 all in the line together.

And that's definitely not you know those by themselves with 14 being a root would not be considered

a well-balanced tree.

So that's why the entire tree did a switch when the recoloring process happened.

And so that's that's essentially the whole key to understanding deleting from a red black tree is simply

to understand the properties of that tree.

You have to know that the black nodes.

There is always going to be a black node at the root no black or I'm sorry no red node is ever going

to have any black children.

And then also just understand that the whole goal of the red black tree is to continually bring balance.

And so when you are deleting any items especially take 18 for example we've done it a few times in this

exercise so you should probably know if I was good to lead 18 it would go to 14 to 17 and then it would

swap the value of 17 to 18.

It would give a pointer to a null value which is also called a sentinel value to 14 and then the entire

tree would merge over again.

And so we can go through that.

This last one so you can see that.

So do 18 delete 18 goes down to 14 to 17 swaps that value out and then it does the single rotate.

Right.

And there you go.

We're rebalanced.

So good job you now know how to delete nodes from a red black tree.

Please let me know if you have any questions whatsoever.

And in our final video for red black trees we're going to go over how to find elements in the tree.