A red black tree is a binary search tree where each node has a color attribute  the value of which is either red or black  In addition to the ordinary requirements imposed on binary search trees  the following requirements apply to red black trees 
   A node is either red or black 
   The root is black   This rule is sometimes omitted from other definitions  Since the root can always be changed from red to black  but not necessarily vice versa  this rule has little effect on analysis  
   All leaves are the same color as the root 
   Both children of every red node are black 
   Every simple path from a given node to any of its descendant leaves contains the same number of black nodes 
   
Notably  maximizing the average fill factor in a structurally equivalent B tree is the same as reducing the total height of the multicolored tree  by increasing the number of non black nodes 
   
Words  Red  and  Black  can be changed to   and