Class Notes (807,247)
Canada (492,669)
CMPT 225 (60)
John Edgar (28)

CMPT 225 Week 8 Lecture 2

2 Pages
Unlock Document

Simon Fraser University
Computing Science
CMPT 225
John Edgar

Insertion: BST properties must hold after insertion Roughly O(height), same as search. Finding correct position when inserting is really easy, just search for the value. Then put it at the null child where you want to insert it. Need to look ahead, however. Also might have issues where something of that value is already in tree. Little bit of extra constant work in building new node and attaching, but very minimal. Note that whatever you insert into a tree will be a leaf. Don't try and change internal structure of tree, although you could. Deletion: Must change internal structure of tree. Typically implement case by case. Cases: Node to be deleted is a leaf (no children): remove it - assign null to parent's reference Node to be deleted has one child: replace the node with its sub tree These first two cases can be kinda collapsed. (as the subtree of a leaf is null, which is what you want to give the parent anyway) Need to look ahead, and look at both children. Lots of stuff to check. Make sure node isn't null before attempting to access member variables. while (nd != target) { if (nd == null) { return; } if (target < nd->data) { parent = nd; nd = nd->left; isLeftChild = true; } else { parent = nd; nd = nd->right; isLeftChild = false; } } Might need a special case for root. Just make sure you don't deal with parent, which is a null pointer. Could be "lazy" and just check if its the root ahead of time. Very easy to identify (even if not to handle necessarily). Do want to keep track of whether it is a left or right child, so we attach to parent in right place. Deleting root: O(nlogn), but probably closer to O(n) Node to be deleted has two children: Which child should we replace the node with? What if the node we replace it with already has two children of its own? When a node has two children, instead of replacing with one of two children,
More Less

Related notes for CMPT 225

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


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.