First I thought this explanation was going bad because the quality of the picture you put is low. But that's actually one of best explanations I've seen, thank you.
Excellent video ... Best way to learn is to sit patiently, watch and practice the mind along with the video (pausing video at various points to do self analysis)..... Reply ·
Very succinct and to the point. Good video! I loved also the style for representing the different cases so I can rebuild the algorithm my own head without need to memorize anything else.
Great! This was a really clear review. Except for case 3 you only talked about finding the min of the right subtree. One can also replace the target node with the max of the left subtree. Either method works in keeping the tree in order.
But what happens to nodes labeled 34 and 36 when we remove their father( when we replaced 30 by 32) Now 34 and 36 should be placed on the left subtree of 40 and not on its right, how to deal with it algorithmically?
When we replaced 30 with 32 we had to have deleted 32 so it is only in the tree once! To see what happens to 34 and 36 in that case, you can watch the video at 2 minutes and 50 seconds (ruclips.net/video/wcIRPqTR3Kc/видео.htmlm50s) where I had shown 32 being removed. Node 34 would be the new left child of node 40 (and node 40 would be the parent of node 34). Does that make sense?
if I implement the remove method recursively, how can I remove a leaf ? Since by the time the recursion gets to the leaf, we lose access to the parent node
If we start with the tree at the very beginning of the video and delete 32, then we're deleting a node that has only one child. That's a simpler case (than if it had two children) and we can just make 40's left child be 34, which effectively removes 32. We just keep the same connection between 34 and 36, because in general we try to avoid restructuring binary search trees. Does that help?
colleen lewis yes. so while deleting 30 why do u choose to swap 32 in place of 30? we can choose 20. that can work too? while deleting 70 we can replace by 65. which is next smaller that too maintain tree property.? does it always have to be next bigger element?
That's just a convention for what you do when you delete a node with two children. I have chosen to use the next biggest rather than the next smallest, but either would work just fine. Does that make sense?
Two answers: Usually we'd just implement either the next biggest or the next smallest. Not both. We never have duplicate keys in our BST - so that never comes up. If we try to add a key that is already in the BST, we would just replace the old value associated with that key.
If i built a tree in order to get to any element in log(n) operations, is it possible to insert an element the way not to break this feature. (in case, n!=2^k)
Q: If i built a tree in order to get to any element in log(n) operations, is it possible to insert an element the way not to break this feature. A: Yes :-) If you can access any element in O(log(n)) operations, you can also add one element in O(log(n)) operations. What do you mean by: (in case, n!=2^k) - Colleen
Oh, you missunderstand me. I mean we can get any element in log(n). And what I want to do, I want to insert an element in any amount of operations (better minimal) and still be able to get any element in log(n). If we have a tree of the only node 1 and insert 2,3,4..., n, we are going to get a line with kinda n elements. But I want it to be a binary search tree after every insert. And, ofc, if we have 2^k nodes, we can get any element in k operations, but inserting one node, there will be 2^k+1, so there will probably be at least 1 node, we get in k+1.
I think you're talking about delete. I think you're on the right track. We can decide to replace the node with the thing that is "just smaller than it" (biggest in the left subtree) OR "just bigger than it" (smallest in the right subtree)- What part of the video are you asking about?
@@ColleenMLewis I was asking about the what nodes we can choose when we are deleting a node that has 2 children e.g. the root node if that is what i am deleting. I wanted to know does it matter if I choose the to replace the root node with either the smallest node on the right subtree or the biggest node on the left subtree? (I was revising for my test at the time so please excuse my the wording of my initial comment. Your video did help me out a lot tho so thank you so much).
@@As-iy2ki Thanks for clarifying! Yep - it doesn't matter which of those: either the smallest node on the right subtree or the biggest node on the left subtree!
@@ColleenMLewis Just wanted to say thank you. I got 80% in my test. Thank you! You are very good teacher. You saved me from getting the big mark questions wrong lol.
Great question! The tree stores pointers to the content that they're storing. Here our keys (the things we search for) were numbers, but you could imagine that they could be something where we'd naturally store a pointer to the thing (like a String). When we remove 32 (which has one child) we remove the whole node! When we remove a node with two children, we'd typically just update the pointers in that node and remove the node that has the key we'll use to replace the node with two children. Does that help? - Colleen
Very helpful tutorial :) but I have a question: Can we find the biggest element in the left subtree rather than the smallest in the right subtree in different version of this algorythm?
To all future students: There are two ways to do this. You either select the maximum value from left side, or the minimum value from right side. Colleen selects 75 here, but most visualizers will select 65 since it's the maximum from left side. Hence my confusion above
Here's a hint. We can traverse between nodes with just 1 step, and we can remove a leaf with one step, and we can remove a node with only a single child with one step. Can you come up with a case that would require only 1 step to remove the node you're hoping to delete? Can you come up with a case where it would require N steps to remove the node you're hoping to delete? (Assume that N is the number of nodes in the tree). I bet you can figure these questions out :-)
What would need to be true of the node you remove if it is O(log(N)). It could take only one step - what would be true of the node you remove in that case. It could be N steps, what would be true of the node you remove in that case? The best way to think about this is as different cases. Can you draw a really "good" tree. Or a really "good" node to try to remove that would make it easy? Or a really "bad" tree/node to remove?
:-) Consider a tree with only 1 node - and then you try to remove that node! :) What about if I have the nodes 1, 2, 3, 4, 5 .... 99,999, 100,000 and I added them in that order such that I got something that really didn't look like a tree - it looked like a list. where each node had only a right child! How many steps would it take to remove the 1? How many steps would it take to remove the 100,000? :-)
this is probably the best tutorial on RUclips
First I thought this explanation was going bad because the quality of the picture you put is low. But that's actually one of best explanations I've seen, thank you.
This is the best explanation of BST methods I've seen
Thanks! :-)
video from 2013 helping me 6 years later.... thanks!
Glad to hear it! :-) - Colleen
And here for me 11 years later. I hope you achieved your goal from back then!
What my professor couldn't make clear lecture after lecture after lecture, nor could my TA, you did in 6 minutes. Thank you so much for sharing this.
Damn ! Tree operations are so easy ! This 6 min video taught me what I couldn't learn in 3 hour class. U r amazing ...thx ...muaahhh :)
Awesome! clear and concise explaination! İ came here from the Odin project
Glad it was helpful!
Of all videos on RUclips, you posted the best tutorial on BST
Thank you! I'm glad it was helpful to you!
concise and clear, such a beautiful presentation ma'am
This is the best explanation I ever came across. short and up to the point. Thank you.
Thanks Vishnu!
best explaination , simple language and covering all the cases . THANKS A LOT
Glad it was helpful! Thanks for the note!
I have checked many insertion and deletion videos, but yours is best one. Sweet, short ,simple and effective though. Thanks.
This was one of the best explanations I have seen yet, so simple, so concise. Thank you, Colleen
The way you explained is brilliant!!! It's marvellous that you manage the whole thing within 6 minutes. Job well done!!!
thank you so much for that simple explanation!. i was so confused about this all the time
I'm glad it is helpful to you!
The best video ever.. Made the deletion look so much easier.. I wish you were my teacher
Small and concise. To the point. Loved it. Thanks alot.
amazing explanation. I used to always get stuck in the removal of a node, but now everything is clear.
Learning for my exams at the moment so thank you very much for this video!
TheXHypex Thanks! I hope the exams went well!
i have my exam in 1 hour, and was getting confused in delete and insert. U made it look very easy. thanks a lot . #awesome
+Abhijeet Joshi Good luck! :) Thanks for the comment!
It took you 6minutes to explain something our teacher failed to do in 2 hours, thx
Binary Search Tree Delete: 1:45
Excellent video ... Best way to learn is to sit patiently, watch and practice the mind along with the video (pausing video at various points to do self analysis).....
Reply ·
Algo and Data structures exams in 2 hours. Thanks for saving my life.
Thanks for the note - I'm happy it was helpful! - Colleen
This video might be old but it was so useful and effective!
Thanks a lot! Wish you all the best!
Very succinct and to the point. Good video! I loved also the style for representing the different cases so I can rebuild the algorithm my own head without need to memorize anything else.
Great! This was a really clear review. Except for case 3 you only talked about finding the min of the right subtree. One can also replace the target node with the max of the left subtree. Either method works in keeping the tree in order.
That's correct. And we only need to replace it with one of those - and we should be consistent about which one we choose.
👍🏿
nice
best explination i could find on the subject, thank you a lot
Thank you so much your explanation is very good and easy to understand....hope you will be uploading such types of explanation in next topics
This clears up everything I only 6 minutes!
I'm glad the video is helpful to you! - Colleen
Using your video to prepare for an interview. Thanks for your help.
But what happens to nodes labeled 34 and 36 when we remove their father( when we replaced 30 by 32) Now 34 and 36 should be placed on the left subtree of 40 and not on its right, how to deal with it algorithmically?
When we replaced 30 with 32 we had to have deleted 32 so it is only in the tree once! To see what happens to 34 and 36 in that case, you can watch the video at 2 minutes and 50 seconds (ruclips.net/video/wcIRPqTR3Kc/видео.htmlm50s) where I had shown 32 being removed. Node 34 would be the new left child of node 40 (and node 40 would be the parent of node 34). Does that make sense?
Yeah! Now I see it clearly! Thanks
your video is best than other countries RUclipsr video
professor dude from my uni took 2 hrs to explain this 6 mins and this female wibba explains a whole lot better, thanks a lot madam.
This video is really helpful and effective to learn about trees.I am from Bangladesh.Thanks Colleen Lewis ♥
Thanks for the note :-)
Thank you so much for making such an awesome video that explains the whole idea clearly. It helps me a lot
I'm glad it was helpful! Thanks for the comment!
Finally. English. thank you so much!!!
I can't believe I understand this now better than after a 2 hours class at the uni
Glad to hear it was helpful!
if I implement the remove method recursively, how can I remove a leaf ? Since by the time the recursion gets to the leaf, we lose access to the parent node
Useful and clear, thanks. BSTs seem like a very useful invention.
Best explaination
Amazing explanation, thank you
Very clear tutoriial and nice voice too thanks sweety!
THANKYOU SO MUCH😭💓
Thanks for the comment! I'm glad it was helpful! :-)
Thank you so much for this video!
i never thought it was this easy
Very helpful, thank you! I also liked the way you explained it.
Greetings from odin!
thanks, that was a simple, but very clear explanation.
Extremely useful! Thanks for uploading.
Thanks! :-) I'm glad it is helpful!
Awesome thanks understood it within a time span of 6 mins :D
this helps me. I understand BSTs really well, but removing nodes continues to stump me. thank you for the clarification.
So when removing 32. 34 and 36 just points to 40 on its left side, correct?
Yes. that's correct!
short and effective !!
BomBamBum Thanks! And thanks for the ascii art below! :-)
thank you so freaking much!
I'm glad it is helpful to you!
what happens after deleting 32?
what happens to 34 and 36?
If we start with the tree at the very beginning of the video and delete 32, then we're deleting a node that has only one child. That's a simpler case (than if it had two children) and we can just make 40's left child be 34, which effectively removes 32. We just keep the same connection between 34 and 36, because in general we try to avoid restructuring binary search trees. Does that help?
colleen lewis yes. so while deleting 30 why do u choose to swap 32 in place of 30?
we can choose 20. that can work too?
while deleting 70 we can replace by 65. which is next smaller that too maintain tree property.? does it always have to be next bigger element?
That's just a convention for what you do when you delete a node with two children. I have chosen to use the next biggest rather than the next smallest, but either would work just fine. Does that make sense?
colleen lewis yes. now the main question is how to decide which one choose to swap so that least cost is inccured.
does it also work for equal keys?
Two answers:
Usually we'd just implement either the next biggest or the next smallest. Not both.
We never have duplicate keys in our BST - so that never comes up. If we try to add a key that is already in the BST, we would just replace the old value associated with that key.
Thank you so much! This is very clear and easy to follow!
If i built a tree in order to get to any element in log(n) operations, is it possible to insert an element the way not to break this feature. (in case, n!=2^k)
Q: If i built a tree in order to get to any element in log(n) operations, is it possible to insert an element the way not to break this feature.
A: Yes :-) If you can access any element in O(log(n)) operations, you can also add one element in O(log(n)) operations.
What do you mean by: (in case, n!=2^k)
- Colleen
Oh, you missunderstand me. I mean we can get any element in log(n). And what I want to do, I want to insert an element in any amount of operations (better minimal) and still be able to get any element in log(n). If we have a tree of the only node 1 and insert 2,3,4..., n, we are going to get a line with kinda n elements. But I want it to be a binary search tree after every insert.
And, ofc, if we have 2^k nodes, we can get any element in k operations, but inserting one node, there will be 2^k+1, so there will probably be at least 1 node, we get in k+1.
Fastest and best video -)
What an awesome explanation! Thank you a lot :)
Given a list of number that you are going to insert, how do you decide which one is the root? The first one ?
Since we never restructure things in a binary search tree - if we insert a list of numbers, the first one will always end up as the root!
Is there a similar explanation on red black trees insertion and deletion.....help much appreciated :)
can somebody tell me if the binary ratio 2:2 and what will be the structure under this system
I'm sorry - I don't understand your question. Can you say a bit more?
This was really good, thank you!
For the left subtree, wouldn't it be that we choose the largest node in the left subtree and smallest node in the right subtree?
I think you're talking about delete. I think you're on the right track. We can decide to replace the node with the thing that is "just smaller than it" (biggest in the left subtree) OR "just bigger than it" (smallest in the right subtree)- What part of the video are you asking about?
@@ColleenMLewis I was asking about the what nodes we can choose when we are deleting a node that has 2 children e.g. the root node if that is what i am deleting.
I wanted to know does it matter if I choose the to replace the root node with either the smallest node on the right subtree or the biggest node on the left subtree?
(I was revising for my test at the time so please excuse my the wording of my initial comment. Your video did help me out a lot tho so thank you so much).
@@As-iy2ki Thanks for clarifying! Yep - it doesn't matter which of those: either the smallest node on the right subtree or the biggest node on the left subtree!
@@ColleenMLewis Just wanted to say thank you.
I got 80% in my test. Thank you! You are very good teacher. You saved me from getting the big mark questions wrong lol.
@@As-iy2ki Congrats! :-)
When you removed 32, is it the node itself or the pointer?
Great question! The tree stores pointers to the content that they're storing. Here our keys (the things we search for) were numbers, but you could imagine that they could be something where we'd naturally store a pointer to the thing (like a String). When we remove 32 (which has one child) we remove the whole node! When we remove a node with two children, we'd typically just update the pointers in that node and remove the node that has the key we'll use to replace the node with two children. Does that help? - Colleen
colleen lewis yes it’s does, thank you!
awesome..it helped a lot...lucid explanation
So what happens if you try to the number 33? does that get added as a leaf too?
Yes! We only ever add things as leaves. And 33 would end up as the left subtree of 34.
colleen lewis Awesome! I thought so, but I wasn’t quite sure. Thank you for replying!
Thank you soooooo muuuuuuch.
I'm glad this was helpful for you!
colleen lewis you have no idea. I passed my course because of your video. I cant even thank you enough.
its 2024 and this's still a great explanation
Thanks so much! :)
what a badass teacher
Pretty concise and clear. Thanks!
so when I replace 30 with 32. do 34 and 36 stay as children of 40? or they follow 32 and 40 becomes a child of 36?
I think it's easier if they follow 32. You can add an extra method to transplant the whole subtree, and 40 becomes the child of 36.
Awesome simple video!
Very helpful tutorial :) but I have a question:
Can we find the biggest element in the left subtree rather than the smallest in the right subtree in different version of this algorythm?
racmo1000 Yes! That is equivalent to pick the biggest element in the left subtree :-)
colleen lewis Thanks for such quick response!
Tried to plot these numbers into a visualizer, and on deletion it selected 65 instead of 75. OP is this a self-balancing tree? WTF?
To all future students:
There are two ways to do this. You either select the maximum value from left side, or the minimum value from right side.
Colleen selects 75 here, but most visualizers will select 65 since it's the maximum from left side.
Hence my confusion above
Clearly explained. Thanks!
Herrroooo from The Odin Project
Brilliant video, thanks!
Amazing explanation thank you!
Super good explanation
what approach is this? right-left?
thankss..
Sorry - I don't understand your question. Can you rephrase it?
Amazing video! Thank you
Thanks :-)
awesome explanation
Thanks! :-)
what would be the T(N) analysis? I am curious to know
Here's a hint. We can traverse between nodes with just 1 step, and we can remove a leaf with one step, and we can remove a node with only a single child with one step. Can you come up with a case that would require only 1 step to remove the node you're hoping to delete? Can you come up with a case where it would require N steps to remove the node you're hoping to delete? (Assume that N is the number of nodes in the tree).
I bet you can figure these questions out :-)
colleen lewis O(log(N)) ?
What would need to be true of the node you remove if it is O(log(N)). It could take only one step - what would be true of the node you remove in that case. It could be N steps, what would be true of the node you remove in that case?
The best way to think about this is as different cases. Can you draw a really "good" tree. Or a really "good" node to try to remove that would make it easy? Or a really "bad" tree/node to remove?
colleen lewis I really appreciate your quick responses . I think I just need more time to study on this material . Thank you for your time
:-) Consider a tree with only 1 node - and then you try to remove that node! :)
What about if I have the nodes 1, 2, 3, 4, 5 .... 99,999, 100,000 and I added them in that order such that I got something that really didn't look like a tree - it looked like a list. where each node had only a right child! How many steps would it take to remove the 1? How many steps would it take to remove the 100,000? :-)
Nicely explained!!!.... subscribed... :)
Thanks Colleen..
So so much
thanks.. the best.. helped me alot..
Very Very Very effective thank you so much
Thank you!! You're amazing:)
Thanks for the note Hanna!
This helped a lot thank you. I did something wholly different than this.
Can u make a video of avl trees? Thanks
Good explaination. Thanks!
awesome video !
thanks!
Thank you professor! You helped me a lot! \o/
Ok but suppos we have to insert one more 32 element in binary search tree then where would we insert it plssass rply me
I shouldn't be inserted in that case
ma'am you are just perfect :*
Thanks...this was very helpful
Thanks a lot for your help.
Nice explanation :) like it ..