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
So far we've talked quite a bit about how to construct binary search trees how to search through them
how to traverse them and different facets like that.
Now what we're going to do is talk about one of the more challenging things in learning about how binary
search trees work and that's how to delete a node from the tree.
So the very first thing I'm going to do is show how it works when you delete the root node.
So we have a root node of 5.
So when we delete that we're gonna take 5 out.
But before we can do that we need to find what we're going to put in first.
And so when you take the root node out you traverse down the left hand side of the tree and you find
whatever the highest of value is.
So say Just so you can see that again if we want to take three out again or take the root node out again
take three hit delete.
You'll see that we go down and we swap it out with two.
And so two is now the root node.
So another one that we can show how how the tree would tend to get reordered is low key as you want
to make sure that you maintain the not the proper balance because this is a balancing tree.
Just make sure that you maintain all the correct properties of a binary search tree.
If we want to take 15 now
we're going to first find 15 that's the first part of the algorithm and then from there because it only
has one child you can just take it out and move the pointer right to whatever its child is.
That's a very easy delete.
Now if we want to delete nine this is going to be slightly more complex because you can see Nine has
a child and 14 as a child.
So when we say we want to take out nine we go down the tree find nine and then we swap it out with eight
because eight is greater than seven but it's less than 14.
So we are able to keep all of the same properties of a binary search tree.
The very easiest thing that you can do when removing an item from a tree is to remove one of the leaf
nodes so we could take 14.
We take 14 or we have to do is traverse down the tree find 14 and then simply remove it.
If you were doing this in code you'd have to remove the pointer from 8 to 14 but when you're just doing
it visually like this you essentially can just pop it right off.
So that's all you have to do.
I showed you how to remove the root node and you know that in order to do that you find whatever value
is highest on the left hand side.
You swap those values and then you point that value to these other nodes it becomes the parent and then
becomes a parent of both sides.
And that's when you need to swap out the root node when you want to delete an item that only has one
child.
You can simply remove it and point directly to that child.
And then if you want to delete a node that has two children you go down to the left hand side and you
swap places with that one and then that has a pointer to the next one and then the last if you want
to remove the leaf then you simply pop it off and that's all you have to do.
So please let me know if you have any questions.
If that doesn't make any sense to you the first time you see it watch the video over once or twice.
It took me a while to become familiar with how binary search tree deletions worked.
It's not the most intuitive thing in the very beginning but the more you see it happen and the more
you play around with it the more it makes sense.
So please let me know if you have any questions whatsoever in the comments section and I'll see in the
next video.
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.