June 29, 2021 11:12 pm GMT
Original Link: https://dev.to/ayabouchiha/part-5-deletion-in-binary-search-tree-4j8d
part 5: deletion in binary search tree
hi, this is part 5 of tree data structure, and the #day_17 of algorithms and data structure, In the last posts, we talked about the binary search tree, its advantages, disadvantages, time and space complexity of its basic operations such as searching, insertion, and also their implementation using python
In this post, we'll discuss deletion :)
last posts:
+ insertion, searching in binary search tree
+ introduction to binary search tree
Deletion in the binary search tree
there are 3 cases in deletion in binary search tree (reference):
- if the node to be deleted is the leaf, this is the easiest case, we will only remove it without moving anything :)
- if the node to be deleted has one child, in this case, we will replace the child with the node and delete the child
- if the node to be deleted has two children, in this case, we need to find a successor (the min of right sub-tree) or a predecessor (the max of left sub-tree), and copy it to the node to be deleted,then delete the successor (or the predecessor)
Deletion implementation
before the implementation of deletion, we need to create a function that returns to us a successor.
getSuccessor function
def getSuccessor(currentNode): while currentNode.left: currentNode = currentNode.left return currentNode
Delete function
def delete(value: int, root): """ [code is from] => https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/ """ # if the tree is empty if root is None: return root # if value is smaller than the root's value if value < root.value: root.left = delete(value , root.left) # if value is greater than the root's value elif(value > root.value): root.right = delete(value, root.right) else: #! case1 or case2 (node has not children or has only one) if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp #! case: node has 2 children # getting successor temp = getSuccessor(root.right) # Copy the successor's value to the node's value root.value = temp.value # Delete the successor root.right = delete(temp.value, root.right) return root
References and useful resources
- https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
- https://www.geeksforgeeks.org/deletion-binary-tree/
- https://www.javatpoint.com/deletion-in-binary-search-tree
- https://www.techiedelight.com/deletion-from-bst/
- https://www.youtube.com/watch?v=g0mjZwYRErM
Thank you for your time!
Happy coding :)
Original Link: https://dev.to/ayabouchiha/part-5-deletion-in-binary-search-tree-4j8d
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To