insert new node with value smaller than the rootsay by typing the number into the number box and pressing the ins button this doesn' cause any rule violationsso the message continues to say tree is red-black correct insert second node that' larger than the rootsay the tree is still red-black correct it' also balancedthere are the same number of nodes on the right of the only non-leaf node (the rootas there are on its left the result is shown in figure figure balanced tree notice that newly inserted nodes are always colored red (except for the rootthis is not an accident it' less likely that inserting red node will violate the red-black rules than inserting black one this is because if the new red node is attached to black oneno rule is broken it doesn' create situation in which there are two red nodes together (rule )and it doesn' change the black height in any of the paths (rule of courseif you attach new red node to red noderule will be violated howeverwith any luck this will only happen half the time whereasif it were possible to add new black nodeit would always change the black height for its pathviolating rule alsoit' easier to fix violations of rule (parent and child are both redthan rule (black heights differ)as we'll see later experiment let' try some rotations start with the three nodes as shown in figure position the red arrow on the root ( by clicking it with the mouse this node will be the top node in the rotation now perform right rotation by pressing the ror button the nodes all shift to new positionsas shown in figure figure following right rotation in this right rotationthe parent or top node moves into the place of its right childthe left child moves up and takes the place of the parentand the right child moves down to become the grandchild of the new top node notice that the tree is now unbalancedthere are more nodes to the right of the root than to the left alsothe message indicates that the red-black rules are violatedspecifically