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