Class Notes (836,147)
Canada (509,656)
CSC148H1 (92)
Paul Gries (18)
Lecture

feb27c.docx

2 Pages
128 Views
Unlock Document

Department
Computer Science
Course
CSC148H1
Professor
Paul Gries
Semester
Winter

Description
 delete o Case 1: leaf node  simply delete o Case 2: Node with one subtree  replace the node with the root of its subtree o Case 3: Node with two subtrees  swap node to be deleted with either:  largest node in the left subtree (in-order predecessor)  the smallest node in the right subtree (in-order successor)  1. find the in-order predecessor, the in-order predecessor will not have a right subtree  2. copy value of the in-order predecessor into the node to delete  3. delete the in-order predecessor, might have a left subtree, refer to case 2 1. def delete(root, k): 2. '''(BSTNode, int) -> BSTNode 3. Ensure that k is not in the tree rooted at root, and return the root of 4. the resulting tree. 5. ''' 6. if not root: 7. return None 8. elif root.key == k: 9.
More Less

Related notes for CSC148H1

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit