Red Black Trees

Red Black Trees are self-balancing Binary Search Trees with special properties. Red Black Tree insertion and deletion require additional steps to maintain these properties.

Properties

• all nodes are red or black
• the root node is black
• red nodes cannot have red children
• the black height is the same on all paths from the root to a leaf node