Red Black Trees!

RBT image

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:

Click here to learn more!