Red Black Trees

This data structure is a type of Binary Search Tree that stay balanced

RBT Properties

• Each node is either red or black
• The root node is black
• No red nodes have red children
• Every path from root to a null child has the same number of black nodes

More info on Red Black trees here Wikipedia page.