red-black trees black either grandchild apossibility is black red grandchild outside bpossibility is redand is outside red inside grandchild cpossibility is redand is inside figure three post-insertion possibilities possibility is black if is blackwe get free ride the node we've just inserted is always red if its parent is blackthere' no red-to-red conflict (rule and no addition to the number of black nodes (rule thusno color rules are violated we don' need to do anything else the insertion is complete possibility is red and is outside if is red and is an outside grandchildwe need single rotation and some color changes let' set this up with the rbtree workshop applet so we can see what we're talking about start with the usual at the rootand insert and you'll need to do color flip before you insert the now insert which is xthe new node figure shows the resulting tree the message on the workshop applet says errorparent and child both redso we know we need to take some action