Afrikaans
Akan
Albanian
Amharic
Armenian
Azerbaijani
Basque
Belarusian
Bemba
Bengali
Bihari
Bosnian
Breton
Bulgarian
Cambodian
Catalan
Cebuano
Cherokee
Chichewa
Chinese (Simplified)
Chinese (Traditional)
Corsican
Croatian
Czech
Danish
Dutch
English
Esperanto
Estonian
Ewe
Faroese
Filipino
Finnish
French
Frisian
Ga
Galician
Georgian
German
Greek
Guarani
Gujarati
Haitian Creole
Hausa
Hawaiian
Hebrew
Hindi
Hmong
Hungarian
Icelandic
Igbo
Indonesian
Interlingua
Irish
Italian
Japanese
Javanese
Kannada
Kazakh
Kinyarwanda
Kirundi
Kongo
Korean
Krio (Sierra Leone)
Kurdish
Kurdish (Soranî)
Kyrgyz
Laothian
Latin
Latvian
Lingala
Lithuanian
Lozi
Luganda
Luo
Luxembourgish
Macedonian
Malagasy
Malay
Malayalam
Maltese
Maori
Marathi
Mauritian Creole
Moldavian
Mongolian
Myanmar (Burmese)
Montenegrin
Nepali
Nigerian Pidgin
Northern Sotho
Norwegian
Norwegian (Nynorsk)
Occitan
Oriya
Oromo
Pashto
Persian
Polish
Portuguese (Brazil)
Portuguese (Portugal)
Punjabi
Quechua
Romanian
Romansh
Runyakitara
Russian
Samoan
Scots Gaelic
Serbian
Serbo-Croatian
Sesotho
Setswana
Seychellois Creole
Shona
Sindhi
Sinhalese
Slovak
Slovenian
Somali
Spanish
Spanish (Latin American)
Sundanese
Swahili
Swedish
Tajik
Tamil
Tatar
Telugu
Thai
Tigrinya
Tonga
Tshiluba
Tumbuka
Turkish
Turkmen
Twi
Uighur
Ukrainian
Urdu
Uzbek
Vietnamese
Welsh
Wolof
Xhosa
Yiddish
Yoruba
Zulu
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.
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.