Red-Black Trees
Properties
Each node is red or black.
The root is black.
No two red nodes are touching.
More info on Red-Black Trees here
Valid Red-Black Tree