All language subtitles for 18 - Red Black Tree Traversal English

In this video we're going to review how to find nodes or find node elements in a red black search tree.

And if you're familiar with binary search trees you know how to do this and it's pretty straightforward.

However if you're studying this for the first time it may be helpful in It'll also good to always review

it.

So we have a tree in front of us right here and to find an element we always start with the root node

which in this case is 17.

And then depending on if whatever we're looking for is greater than or less than 17 we will go to the

left or the right hand side.

So if the node we're looking for is the value 23 we'd start at 17.

We know 23 is greater than that.

So we go to the right.

We compare it with 24.

We know it's less than 24.

Go to the left.

We compare it with 22.

We know it's greater than 22.

And then we find it.

So you can see we found it in just one two three hops which is pretty impressive because if we started

in say a sorted array that would have take taking 23 iterations to get to it if you had numbers 1 through

23.

So it's one of the big reasons why binary search trees or red black trees are very important.

And also it's a huge reason why red black trees or rebalancing type of structures like this make searching

much more efficient.

And so we talked in the first video on red black trees.

Whenever you try to find an element you're always going to have a time complexity of order of log in

which is very fast.

So I'm going to go through a few searches here.

A few animated searches.

Just so you can get a hang of it.

So let's search for 21.

It starts at 17 goes to 24 22 and then 21.

You can see it's very very straight forward.

You're just looking at each node comparing it with the value you're searching for.

If it's greater than it you move to the right.

If it's less then you move to the left and we'll go with a couple more and search for 25.

So is that right.

This time it's greater than 24.

Less than 66.

Less than 33.

And there it is.

Found it.

And the last one will look for the smallest node and are the smallest value which is 10.

So it starts at 17 moves to the left moves to the left again and there found it.

Now to actually traverse a tree a black red tree is red black tree.

You can do it pretty easily and I'll show you how that works so I'm going to start this all the way

to the left because we know that's the lowest value.

It goes to its parent which then goes all the way to the left of its child back up to its parent and

then all the way to the right you can see that the way to and then there's your route.

The way to traverse it is simply to look first for the lowest value of every tree structure even some

tree structure and then move your way up to that respective parent and then to the right and then back

again to the greater nodes.

You can see that it's the same exact pattern.

And if we were to have a lot more nodes it would be the same thing which is one of the great reasons

for using recursive type algorithms with trees because they allow for you to scale your approach and

use the same method calls again and again.

And so you can see that's how you traverse a red black tree.

So good job you now have a much better understanding of how red black trees work how you reverse them.

How do insert elements how to delete elements and then how to find them.