how can we fix things so rule isn' violatedan obvious approach is to change one of the offending nodes to black let' try changing the child node position the red arrow on it and press the / button the node becomes black the good news is we fixed the problem of both parent and child being red the bad news is that now the message says errorblack heights differ the path from the root to node has three black nodes in itwhile the path from the root to node has only two thus rule is violated it seems we can' win this problem can be fixed with rotation and some color changes how to do this will be the topic of later sections more experiments experiment with the rbtree workshop applet on your own insert more nodes and see what happens see if you can use rotations and color changes to achieve balanced tree does keeping the tree red-black correct seem to guarantee an (almostbalanced treetry inserting ascending keys ( and then restart with the start button and try descending keys ( ignore the messageswe'll see what they mean later these are the situations that get the ordinary binary search tree into trouble can you still balance the treethe red-black rules and balanced trees try to create tree that is unbalanced by two or more levels but is red-black correct as it turns outthis is impossible that' why the red-black rules keep the tree balanced if one path is more than one node longer than anotherthen it must either have more black nodesviolating rule or it must have two adjacent red nodesviolating rule convince yourself that this is true by experimenting with the applet null children remember that rule specifies all paths that go from the root to any leaf or to any null children must have the same number of black nodes null child is child that non-leaf node might havebut doesn' thus in figure the path from to to the right child of (its null childhas only one black nodewhich is not the same as the paths to and which have this arrangement violates rule although both paths to leaf nodes have the same number of black nodes