trees and external storage atree bred-black tree black node red node figure tree and its red-black equivalent operational equivalence not only does the structure of red-black tree correspond to treebut the operations applied to these two kinds of trees are also equivalent in tree the tree is kept balanced using node splits in red-black tree the two balancing methods are color flips and rotations -node splits and color flips as you descend tree searching for the insertion point for new nodeyou split each -node into two -nodes in red-black tree you perform color flips how are these operations equivalentin figure we show -node in tree before it is splitfigure shows the situation after the split the -node that was the parent of the -node becomes -node in figure we show the red-black equivalent to the tree in the dotted line surrounds the equivalent of the -node color flip results in the redblack tree of figure now nodes and are black and is red thus and its parent form the equivalent of -nodeas shown by the dotted line this is the same -node formed by the node split in figure