Red-Black Trees                                     

Overview:

             

A Red-Black tree is a type of binary search tree where each node is given a color, red or black.

        
        

Here is a link to more information: Red-Black Trees: Geeks for Geeks

        

Here is an image:             
            

        

Rules:

        
                
  1. Nodes are either red or black
    2.             
  2. Root/leaf/null nodes are always black
    3.             
  3. If a node is red, then its 2 children must be black
    4.             
  4. The # of black nodes from the root to a null node must be the same for all paths
    5.         
        
        

Key Algorithms:

                
                            
  1. Insert
    2.                         
  2. Rotate
    3.                         
  3. Remove
    4.