Class Notes (834,740)
Canada (508,705)
CMPT 225 (60)
John Edgar (28)
Lecture

CMPT 225 Week 9 Lecture 3

2 Pages
116 Views
Unlock Document

Department
Computing Science
Course
CMPT 225
Professor
John Edgar
Semester
Summer

Description
Node is not allowed to be "doubly black" - will see on Monday Insert as for a BST and make the new node red - from here, can violate properly that both a red node's children are black (is parent red), or could violate property that every path from node to leaf contains same # black nodes If this is the case, try colouring the new node black, colour both parent and uncle red. Only works if both were red, otherwise equal bh prop violated. If changing colours doesn't work, rotate. Get same answer if you count root as one, don't count leaves as if you ignore root, count leaves for bh. Code in lecture slides, USE FORASSIGNMENT. Uncle is "brother" of parent - node with same parent as parent. Assignments generally faster than comparisons, particularly for bools and ints. if (x.p == x.p.p.left) -> if x's parent is the left child of it's parent (x's grandparent) If x's parent is the root, x's parent is NOT red, so we won't look at it's grandparent, so no need to fear. Symmetric part: find and replace right with left, left with right. If uncle is red, same colour as x's parent. Therefore, can make grandparent red, make parent and uncle both black and preserve bh property. x's grandparent CANNOT be re
More Less

Related notes for CMPT 225

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