All language subtitles for 17 - Properties of Red Black Trees English

High in this video we're going to review the properties of red black trees and also see how the process

of inserting into a red black tree works.

So right here I have a binary tree that's completely unbalanced.

So if you want to put values on this you could say something like this is a 10.

This is a nine eight seven and just keep going down the line.

It's possible for a tree to look like this even though this doesn't even resemble a tree.

And when this is the case the complexity for searching on a tree like this actually equals order of

n and which if you know your complexities you know that that's extremely slow.

And the reason for it is because the system will have to iterate through every single node looking for

the item that it wants.

And so there has been a ton of research on how to fix that.

And one of the procedures that people use is to create a red black tree and a red black tree what its

goal is to develop a well-balanced tree and trees which remain balanced and then they can guarantee

a search complexity of order of law again.

And in a dynamic environment they also can be rebalanced.

So as you insert the tree will actually rebalances self.

There is an additional complexity which also equals the order of law again.

While that's happening so you have to you have to kind of know that that's something that's required

however it is a great way of making sure that you do have a balance tree.

It's also important to know the properties of a red black tree.

Some of the properties are that every node is either red or black.

Every leaf null is black meaning that every single leaf whether it whether it be red or black has what's

called a sentinel node which is a node node which is a pointer to nothing.

It's essentially used just so you know when you've reached a leaf it's just something and this is not

something that is unique to red black trees.

Trees use something very similar as well.

So it's You'll come across quite a bit.

Another thing to know is that the root node is always covered black.

There is no path from the root to the leaf that has two consecutive red nodes nodes are inserted in

the same way initially just like a binary search tree.

And we're going to go through that process here in a minute.

And then the tree is fixed by recoloring which we're also going to go through a live animation to see

how this works.

And then when the last properties is at each of the paths from the root to the leaves have the same

number of black nodes.

So now we're going to go and see the way this actually works on a practical basis.

So I'm going to start by inserting a node and I'm going to give it a value of 10 and you'll see that

that node is colored black and by default that is the root.

Now I'm going to give it a 12 or add a 12.

So it looks at this at the root and realizes 12 is larger than 10 and it adds 12 to the right hand side.

If you know anything about binary search trees you know that that's the way they work as well.

Now I'm going to add on 11 and you'll see that when I add the 11 it's going to start by being inserted

to the left of the 12.

But the tree is going to recognize that now it's imbalanced and then it's going to fix itself.

So you'll see it looks at the 10 and then the 12 goes to the left and then realizes hey this imbalance

tree.

So it moves to the left and then it actually readjusts and you can see it makes the 11.

Now the root node.

So this is when now you get to go through the actual algorithm you'll see it's recursive which means

that it looks at every single parent option and then adjust the cell based off of that value and the

whole goal of a red black tree is to continually rebalance itself see the best form tree possible.

So now add.

Start adding some larger numbers and put a 100 in which is going to move all the way to the right.

Now the system knows that both of these are are that 12 and 100 were both red so it readjust because

remember that you can never have a red parent and a red child you have to readjust the coloring to ensure

it works.

So now we'll add a 95 95 will automatically go to the left of 100 but then you'll see as the system

adjusts.

And there you go.

And it readjusts again.

So you notice that this is a very dynamic type system that continually looks to find ways to make sure

that the the tree becomes balanced and it's looking with each iteration on different ways that it can

readjust itself and it uses the rest of the process it is called the recoloring.

And you can see when we add it at that number it got readjusted and we're back to making sure that we

have the black red black type of color scheme.

Now we're going to add 55 55 is going to look at the 11 realize it's greater 95 is less.

It's greater than 12 greater than 25.

So we'll start out by going to the right and then it's going to readjust.

And there you go.

We're balanced again.

And now I'll start adding a few to the left hand side.

So add in the 16.

Six teens going to realize it's greater than 11 so the right hand side.

But it's also greater than 12 and there you go so I'll readjust again

and they're perfect you.

Even though with the traditional just a plain tree that could have been a node that could have rebadge

or unbalance the whole tree with a red black system it will continually continually run through the

algorithm to make sure that it can remain balanced.

I'm going to put in a 19 now and you can see that's going to go all the way to the right of the 16 but

then you can watch and see as it as it readjust.

So

there you go.

So now 16 is the parent of both 12 and 19.

And we could do this for days.

I think you probably have a good sense of the way the system works.

A really important thing to know is that the root node can be changed.

And that's something that you that it took a little while for me to kind of understand the concept of

how the entire make up of the tree can actually change dynamically.

And the only some of the only constants are those properties.

So it's very important especially if you're taking this for an algorithm class or something like that

to memorize those properties and to become very familiar with them because those are really going to

help you understand the way the whole process works and as you analyze the algorithm it will really

help you because whenever you go through recursive algorithms knowing the formal semantics and knowing

the properties behind the system is what's going to help you understand it and analyze it a lot better.

So and once again just to reiterate the complexities if you have a red black tree you're going to see

complexities of order of log in and that's because just like with a traditional binary search tree That's

balance.

You're not going to have to iterate through that many values because you can see even though we may

have given a lot of different random numbers the system continually updated continually rebalanced and

so you're going to end up with those really nice order of log and type of complexity.

So in the next video we're going to go over how to delete or remove a node from a red black tree.