ignore that for the momentas an item is being insertedthe insertion routine checks that certain characteristics of the tree are not violated if they areit takes corrective actionrestructuring the tree as necessary by maintaining these characteristicsthe tree is kept balanced red-black tree characteristics what are these mysterious tree characteristicsthere are twoone simple and one more complicatedthe nodes are colored during insertion and deletionrules are followed that preserve various arrangements of these colors colored nodes in red-black treeevery node is either black or red these are arbitrary colorsblue and yellow would do just as well in factthe whole concept of saying that nodes have "colorsis somewhat arbitrary some other analogy could have been used insteadwe could say that every node is either heavy or lightor yin or yang howevercolors are convenient labels data fieldwhich can be boolean (isredfor example)is added to the node class to embody this color information in the rbtree workshop appletthe red/black characteristic of node is shown by its border color the center coloras it was in the tree applet in the last is simply randomly generated data field of the node when we speak of node' color in this we'll almost always be referring to its red-black border color in the figures (except the screen shot of figure we'll show black nodes with solid black border and red nodes with white border (nodes are sometimes shown with no border to indicate that it doesn' matter whether they're black or red red-black rules when inserting (or deletinga new nodecertain ruleswhich we call the red-black rulesmust be followed if they're followedthe tree will be balanced let' look briefly at these rules every node is either red or black the root is always black if node is redits children must be black (although the converse isn' necessarily true every path from the root to leafor to null childmust contain the same number of black nodes the "null childreferred to in rule is place where child could be attached to nonleaf node in other wordsit' the potential left child of node with right childor the potential right child of node with left child this will make more sense as we go along the number of black nodes on path from root to leaf is called the black height another way to state rule is that the black height must be the same for all paths from the root to leaf