All language subtitles for 12 - Searching Through a Binary Search Tree English

af Afrikaans
ak Akan
sq Albanian
am Amharic
ar Arabic Download
hy Armenian
az Azerbaijani
eu Basque
be Belarusian
bem Bemba
bn Bengali
bh Bihari
bs Bosnian
br Breton
bg Bulgarian
km Cambodian
ca Catalan
ceb Cebuano
chr Cherokee
ny Chichewa
zh-CN Chinese (Simplified)
zh-TW Chinese (Traditional)
co Corsican
hr Croatian
cs Czech
da Danish
nl Dutch
en English
eo Esperanto
et Estonian
ee Ewe
fo Faroese
tl Filipino
fi Finnish
fr French
fy Frisian
gaa Ga
gl Galician
ka Georgian
de German
el Greek
gn Guarani
gu Gujarati
ht Haitian Creole
ha Hausa
haw Hawaiian
iw Hebrew
hi Hindi
hmn Hmong
hu Hungarian
is Icelandic
ig Igbo
id Indonesian
ia Interlingua
ga Irish
it Italian
ja Japanese
jw Javanese
kn Kannada
kk Kazakh
rw Kinyarwanda
rn Kirundi
kg Kongo
ko Korean
kri Krio (Sierra Leone)
ku Kurdish
ckb Kurdish (Soranî)
ky Kyrgyz
lo Laothian
la Latin
lv Latvian
ln Lingala
lt Lithuanian
loz Lozi
lg Luganda
ach Luo
lb Luxembourgish
mk Macedonian
mg Malagasy
ms Malay
ml Malayalam
mt Maltese
mi Maori
mr Marathi
mfe Mauritian Creole
mo Moldavian
mn Mongolian
my Myanmar (Burmese)
sr-ME Montenegrin
ne Nepali
pcm Nigerian Pidgin
nso Northern Sotho
no Norwegian
nn Norwegian (Nynorsk)
oc Occitan
or Oriya
om Oromo
ps Pashto
fa Persian
pl Polish
pt-BR Portuguese (Brazil)
pt Portuguese (Portugal)
pa Punjabi
qu Quechua
ro Romanian
rm Romansh
nyn Runyakitara
ru Russian
sm Samoan
gd Scots Gaelic
sr Serbian
sh Serbo-Croatian
st Sesotho
tn Setswana
crs Seychellois Creole
sn Shona
sd Sindhi
si Sinhalese
sk Slovak
sl Slovenian
so Somali
es Spanish
es-419 Spanish (Latin American)
su Sundanese
sw Swahili
sv Swedish
tg Tajik
ta Tamil
tt Tatar
te Telugu
th Thai
ti Tigrinya
to Tonga
lua Tshiluba
tum Tumbuka
tr Turkish
tk Turkmen
tw Twi
ug Uighur
uk Ukrainian
ur Urdu
uz Uzbek
vi Vietnamese
cy Welsh
wo Wolof
xh Xhosa
yi Yiddish
yo Yoruba
zu Zulu

Original subtitles

‫In this tutorial we're going to walk through how binary search actually works.

‫And before we get into that we need something to compare it to.

‫And so what we're going to compare it to is something called linear search on the page right now.

‫We have a standard array and its array of integers going from 1 to 25.

‫The order doesn't matter at all because all we're concerned with right now is searching for an item.

‫So let's do a sample search.

‫The first thing we're going to search for is 15 and we're going to see how many times we have to iterate

‫through the array which means to go through each element in the array before we get to 15.

‫So we start out at the zero element which actually is one is the value.

‫And so we go one two three four five six.

‫So we actually have six things that we have to go through in order to get to that 15 value.

‫Now if we want to go to 25

‫in this case we would go one two three four five six seven eight nine 10 and 11.

‫And what if there was nothing the element we were looking for wasn't even in the array.

‫So say we had ninety nine.

‫It would be what we call and there would be in you know which is similar to 25 except in this case it's

‫considered the worst case time complexity because the element isn't even in the array which means we

‫would go through the entire array without finding an element and then returning that we couldn't find

‫it.

‫So this is not a good way to search because right here we only have 11 elements.

‫What would happen if we had a thousand elements or a million elements or 10 million elements.

‫If you think about when you're using Google it's not going through every single site on the web to find

‫what you're looking for.

‫It has an algorithm that makes it a much much more efficient.

‫And what we're going to look at is not exactly what Google uses but we're going to look at a way to

‫make searching a lot more efficient than this.

‫If you're taking this for an algorithm class you'd one know the worst case time complexity is going

‫to be big go of and for a linear search through an array like this.

‫And if you're not taking it for our algorithm classes you know what it's talking about.

‫Don't worry it's just called Big O notation.

‫So we're going to do the same thing here.

‫We're going to go 15 25 and the

‫you get now to know how search works on a binary search tree it's very important to know the structure.

‫So if you've not watched my previous video on showing how to set up a binary search tree you may want

‫to go watch it.

‫If not just follow along and it is pretty intuitive and easy to pick up.

‫So we're going to first do our very first search which is 15.

‫In this case 15 is the root node which means that our this only took one iteration we only had to search

‫through one item we found it and then we returned.

‫That's not always the case.

‫In fact it's very rarely going to be the case the item you're looking for is actually at the root.

‫But when it is that's what it's going to return.

‫Now let's look at what it would be if it was 25.

‫If you remember last time it took us 11 steps to get to 25 here.

‫Let's see how many steps it's going to be.

‫So we start at 15.

‫That's one then we realize that 25 is bigger than 15.

‫So we go to the right hand side.

‫So here we see okay we compares 25 bigger or smaller than 20.

‫We know it's bigger.

‫So we look at the right note again so so far this is we've taken two steps.

‫Now we're at 22.

‫Once again we compares 25 bigger than 22 or is it less than we know it's bigger and we arrive at 25.

‫That took us a total of one two three three steps until we got to it.

‫And if you want to include that last one it took four steps to get to it.

‫Ninety nine would actually be the same number it would only take us four steps because we would go from

‫15 to 20 20 to 25.

‫We'd realize that 25 is the leaf and there is nothing greater than 25.

‫And the system would return that 20 the 99 was not in the binary tree.

‫So you can see right there and compare these two.

‫This is dramatically faster than than having to go linearly and go through every single item.

‫It's very rare that you would actually find something using a linear search faster than using a binary

‫search tree.

‫Mainly because it's very rare you'll find your element on the second or third second or third iteration.

‫But the way to think about this is what really helped me understand this at least was being able to

‫think of opening up a phone book.

‫And when you have a phone book say that you start and you're using the white pages for example it's

‫sorted by last name and you have somebody that Star last name you're looking for starts with an M. you're

‫going to open it up somewhere in the middle doesn't matter where you look it up.

‫And then from there you're going to compare them or you could compare whatever page you opened up.

‫So let's say you opened it up and you open it up at the letter D and you know that you need to get to

‫em.

‫So you have a goal of getting to them now you look at the U.S. that is less than or greater than them.

‫We know it's less than them alphabetically.

‫So what do we do.

‫That means that we would go to the right and we would open that up again and then we would keep on doing

‫this over and over again until we find them.

‫And so it's a very similar thing with the binary search tree.

‫You take the number you're trying to find.

‫You go through every different stage every different level of the tree and you look either to the right

‫or to the left and then you make your decision based off that.

‫So just to practice it one more time.

‫This time we'll look for the number 21.

‫So we started 15 is 21 less than or greater than 15.

‫It's greater than we go to 20.

‫Now at 20 we do the same thing.

‫The comparison says that 21 is greater so we go down again and we have 22 there with 22.

‫When we compare coin one is less than 22 and we find it and it only took us four steps which is incredibly

‫fast.

‫Now the average time complexity is big.

‫So of blog base to event.

‫And so this is extremely fast if you're familiar with the principles logarithms.

‫Logarithms are kind of like exponents except backwards.

‫So if the other search was was N log in means it's dramatically faster.

‫That's on the average case which is very important to note.

‫This is an average case.

‫What makes something an average face when it comes to a binary search tree has a lot to do with how

‫balanced the tree is.

‫So that is something to remember.

‫You want to have your binary search trees balanced.

‫Very important the key to this is something I'm going to show you a binary search tree can actually

‫equal the same complexity as a regular linear search.

‫And do you know how that can happen.

‫It's actually relatively intuitive.

‫Here you can see are nodes.

‫You have the root and you can see this tree is actually completely symmetrical.

‫It's very rare to have it exactly like this but it's nice when it is because it makes searching through

‫it incredibly fast.

‫Now on this page you will see this is a horribly balanced tree.

‫There essentially is no tree and you will run into cases where this happens.

‫And so what you're going to have to deal with here when it comes to searching you're going to have a

‫complexity of big-O event which is actually identical to searching using a linear search method.

‫And the reason for that is this is actually the root node.

‫I know it doesn't even look like a tree.

‫So it's hard to see however.

‫This is the root.

‫So if we have a number we can simply say the number is 1.

‫We actually have to go through each element and it's the last element in the search tree that has that

‫total.

‫So this makes searching really kind of pointless or using this kind of data structure pointless if this

‫is what your tree looks like.

‫It works out much better if you have a well-balanced tree and there's some tutorials I'm going to create

‫that will talk about how you can balance your tree out if you happen to have something that looks like

‫this.

‫But this is this is where usually can have a way that you can randomize and balance out your tree so

‫that you can get back to those log in type of search complexities.

‫But it is important to know that the worst case performance of a binary search tree can be as bad as

‫big event.

‫So it's important to just always keep that in the back of your mind.

‫But that's a tutorial please let me know if you have any questions on this whatsoever.

‫And after this we're going to start learning how to insert and delete nodes off of a binary search tree.

Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.