CSC148H1 Lecture Notes - Lecture 25: Mutation
CSC148: Lecture 25: BST Deletion
References: Code seen in the pictures can be found on the CSC148 website:
http://www.teach.cs.toronto.edu/~csc148h/winter/
Binary Search Tree Mutation: Deletion
- What return value?
o Return node for every call to delete
- What to do if node is None?
o If node is none, pass
- What if value to delete is less than that at node?
o Delete left node
- What if it’s more?
o Delete right node
- What if the value equals the node’s value?
o Neither is smaller
o 3 cases
▪ This node has no left child
• Node is equal to right node
▪ This node has no right child
• Node is equal to left node
▪ Both children:
• 1 way to note break BST definition
• Find max node in left tree and put it in place of deleted node
• Or find the min node in right tree and put in in place of deleted
node
BST Deletion
- Given an item to delete, use same approach as __contains__ to search for an item
- If item is found, it will be at root of a subtree, where we delete it
- Input:
o BST rooted at node
o a value we wish to delete from the tree (if it exists)
- Output
o If value found, return corresponding from the tree
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
References: code seen in the pictures can be found on the csc148 website: http://www. teach. cs. toronto. edu/~csc148h/winter/ What return value: return node for every call to delete. What if value to delete is less than that at node: delete left node. What if it"s more: delete right node. Given an item to delete, use same approach as __contains__ to search for an item. If item is found, it will be at root of a subtree, where we delete it. Input: bst rooted at node, a value we wish to delete from the tree (if it exists) If value found, return corresponding from the tree: this node gets disconnected / extracted / removed from tree. 3 possible scenarios: current has no child, easiest (just remove, current has 1 child, current has 2 children if node is none: If value is mode than node. value, delete it from right child and return the node.
