1. Every node is either red or black.
2. Root of tree is always black.
3. Every leaf (NULL) is black.
4. If a node is red, then both its children are black.
5. Every path from root to a NULL node has same number of black nodes.

TreeMap implementation is not synchronized.

TreeSet is basically implementation of a self-balancing binary search tree like Red-Black Tree. Therefore operations like add, remove and search take O(Log n) time.