A RedBlackTree is an extended type of BinaryTree which satisfies the following conditions:
- Every node is coloured either red or black
- Every leaf node is coloured black
- If a node is red, then both of its children are black
- Every path from the root to a leaf contains the same number of black nodes. This number is called the black-height of the tree.
They guarantee O(log n) time per access.
