red-black trees you can see how the rules work by using the rbtree workshop applet we'll do some experiments with the applet in momentbut first you should understand what actions you can take to fix things if one of the red-black rules is broken duplicate keys what happens if there' more than one data item with the same keythis presents slight problem in red-black trees it' important that nodes with the same key are distributed on both sides of other nodes with the same key that isif keys arrive in the order you want the second to go to the right of the first oneand the third to go to the left of the first one otherwisethe tree becomes unbalanced distributing nodes with equal keys could be handled by some kind of randomizing process in the insertion algorithm howeverthe search process then becomes more complicated if all items with the same key must be found it' simpler to outlaw items with the same key in this discussion we'll assume duplicates aren' allowed fixing rule violations suppose you see (or are told by the appletthat the color rules are violated how can you fix things so your tree is in compliancethere are twoand only twopossible actions you can takeyou can change the colors of nodes you can perform rotations in the appletchanging the color of node means changing its red-black border color (not the center colora rotation is rearrangement of the nodes thatone hopesleaves the tree more balanced at this point such concepts probably seem very abstractso let' become familiar with the rbtree workshop appletwhich can help to clarify things using the rbtree workshop applet figure shows what the rbtree workshop applet looks like after some nodes have been inserted (it may be hard to tell the difference between red and black node borders in the figurebut they should be clear on color monitor there are quite few buttons in the rbtree applet we'll briefly review what they doalthough at this point some of the descriptions may be bit puzzling