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