This is an implementation of a red black tree which is a self-balancing binary search tree.
After each insert/delete operation, There are specific rules that must be respected to enforce the balance. If they have been violated, they must be restored by recoloring and rotations.
-
Each node is either black or red.
-
The root is always black.
-
A red node must not have red children.
-
All paths from a node to the leaves contain the same number of black nodes.