Red Black Trees!

How they work:

There are only two rules that a RBT must follow:

1. A red node cannot have a red child.
2. The black height must be the same throughout the tree.

These are the Rule 1 violations that can happen when a node is inserted into a RBT:

• Red node with red aunt
• Red node with black aunt
• Red node with null aunt (this is actually handled the same as the previous case!)

Click here to learn more!