No video :(

Binary Search Tree (BST): Deletion Function

Подписаться 13 тыс.

Просмотров 24 тыс.

50% 1

Code below... In this second part in our two videos covering the Binary Search Tree, we'll cover the only part omitted from our prior lesson; the Deletion Function. In the beginning of the video, we'll introduce some background and the underlying idea and later we'll return to our code from the last video and add in the Deletion Function.
(PYTHON 2)
► Code for this lesson: github.com/bfaure/Python_Data...
(PYTHON 3)
► Code for this lesson: github.com/bfaure/Python3_Dat...
► Original Binary Search Tree lesson • Python Data Structures...
► BST Validator Function • Binary Search Tree (BS...
****
► Video series covering various common/useful algorithms:
• Python Algorithms
► Video series covering GUI development in Python (WIP): • Python GUI Development...
References:
[1]: en.wikipedia.org/wiki/Binary_...
[2]: www.geeksforgeeks.org/binary-s...

Опубликовано:

10 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 33

@chintanvibhakar9979 6 лет назад

Hi Brian, amazing series of videos. Just wanted to understand that when node with value 5 is deleted, why does node with value 9 becomes parent of node with value 10? Why change node with value 10 at all?

@BrianFaure1 6 лет назад

Hello Chintan. Thanks! So I've just realized the visualization is wrong! I apologize for any confusion this must have caused. After deleting the 5 node the tree should actually look like this... (6) | \ | \ (4) (10) | \ | \ (9) (11) ...then after deleting the 4... (6) | \ \ (10) | \ | \ (9) (11) ...then after deleting the 11... (6) | \ \ (10) | \ | (9) ...then after deleting the 9... (6) | \ \ (10) Thanks for pointing this out to me, I will pin this comment so future viewers are aware of my mistake. I really wish RU-vid still had annotations so I could point this out on the video...

@servicebasedtoproductbased9359 4 года назад

@@BrianFaure1 nice efford

@duinterweb 2 месяца назад

This got me passed my bootcamp. I watched as many as 5 different binary search tree node remove videos but I could not figure out how how to do it. I stumbled onto this video and I watched it multiple times. It finally clicked. Thank you. I would still be sitting at my computer without this.

@Antinormanisto 3 месяца назад

Broooo, thank you very much. I search how to delete a node for 2-3 hours. You saved me

@nackyding 4 года назад

I tip my hat to once again. You killed it with the BST implementation/walk through now you're adding the cherry on top with the delete function. Thank you so much!

@Lexaire 4 года назад

These two videos on BST were enlightening, thank you for sharing them! And especially thank you for going back to make this one on the deletion method. I had no idea how it was going to work with two children and didn't realize you'd need to run that min search which cleared things right up!

@jimmorrisshen 6 лет назад

Thanks for adding the deletion function part.

@YorozuyaNeesan2010 3 года назад

This is a great solution. My only worry is if you're given some coding exercise through Leetcode or such where you have to just write the delete function and the way they set up their nodes doesn't keep track of the parent node. This doesn't work for that, so I think it'd be good to teach people the alternate way too. Thanks for the hard work.

@AdrianMei 5 лет назад

your code is beautifully written

@AmitDube15 6 лет назад

Hi Brian, Thanks for the amazing tutorial. Deletion Function alone had more line of code than the bst ;-)

@TheSSB007 3 года назад

Amazing!!! best content on Trees

@ards5161 5 лет назад

Great vids

@current1710 4 года назад

thx man!

@BrianFaure1 6 лет назад

Part 1 of the Binary Search Tree lesson can be found here: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-f5dU3xoE6ms.html

@dijkstra4678 4 года назад

Just one small thing for people like me who need to make sense of everything. At 5:48 thats not how the tree actually looks. 10 is the right child of 6 and 9 is the left child of ten, it prints the same so while editing he may have gotten confused, no biggie. Apart from that absolutely amazing tutorial, well done!

@apoorvgarg0204 4 года назад

The explanation was great. I think that there will be a problem if we wish to delete the root node of the tree and the only remaining node is the root.

@ridhibansal2923 2 года назад

Hi Brian, Thank you for the video! Could you please explain why do we need two checks (if node == None or self.find(node.value) == None) inside delete_node function? Isn't node==None enough?

@tianhanjie3308 6 лет назад

Amazing BST series videos, everything is cleared and easy to understand, but I have a question, in terms of _find function, if you return cur_node, is the output a memory address?

@BrianFaure1 6 лет назад

Hey Tian, thanks for the nice remarks! The returned 'cur_node' is technically an instance of the node class, so it would have a memory address, but the pointers in Python are handled from a higher level so you just get back the actual node object itself. However, if you do pass the _find function a value that isn't found in the tree, you'll be returned a None object rather than a node object.

@tianhanjie3308 6 лет назад

Kk, thank you man

@jingyuchang1885 6 лет назад

Hi Brian, this is an excellent video!! I have a question about the successor of the deleted node! From your code: successor = min_value_node(node.right_child) I can tell that the deleted node's successor is the node which exists in the right sub-tree of the deleted node and has the smallest value. Is this correct? If it's correct, my question is that if this is the rule of how to find the successor? With this rule, after we delete node, the tree is still a binary tree, right? Can we set the successor the node which exists in the left sub-tree of the deleted node and has the greatest value? It seems the tree still will be a binary tree after deleting! So is there any advantage to use successor = min_value_node(node.right_child) rather than successor = max_value_node(node.left_child)? Thanks a lot!

@BrianFaure1 6 лет назад

Hi Jingyu! Yes you can actually use either the min_value_node of the right child or the max_value_node of the left child (the inorder successor or inorder predecessor). In terms of the advantage to either approach, I would assume they are equivalent, unless you knew a lot about the structure of the rest of the tree. As you can see in this post ( stackoverflow.com/questions/26898354/deleting-a-node-in-a-b-tree-using-inorder-predecessor-vs-successor-as-the-rep ) on Stack Overflow, the decision between inorder successor or inorder predecessor *will* have an effect on the resulting BST, but which to choose would be hard to tell unless you could perform both and compare which was more balanced after the fact, or had a fancy algorithm to inform you of which to choose.

@jingyuchang1885 6 лет назад

Thank you very much Brian!! This really helped me a lot!

@nanayang3736 4 года назад

wait Where did you get that scary typing speed

@siddharth-gandhi 4 года назад

I think it's sped up so the videos won't be twice as long

@igortelles6779 3 года назад

3:34 tooooodddleeeees

@harongachanja257 3 года назад

When deleting the parent node the code does not return anything....But for the other nodes, it works as expected. What could be the bug in the code?

@BrianFaure1 6 лет назад

ATTENTION: From 5:47 on the visualization of the Binary Search Tree is incorrect, see my response to Chintan Vibhakar for a corrected version.

@BegForMyMercy 8 месяцев назад

doesn't work if you repeat deletion of the same value fyi For the function delete_value, we need to catch this edge case. def delete_value(self, value): if self.find(value) == None: #if we can't find the value return None return self.delete_node(self.find(value))