# Properties

- Every node is either RED or BLACK
- Root node is always BLACK
- Red nodes always have BLACK children
- All NULL nodes are considered BLACK
- Every path from ROOT node to LEAF nodes has equal amount of BLACK nodes

## Time Complexities

- Search: O(log n)
- Insertion: O(log n)
- Deletion: O(log n)

### Pros and Cons

Pros

- Faster insertion and removal operations than AVL trees
- Generally fewer rotations than AVL due to less strict balancing
- Pretty easy to implement

Cons

- Search operation is generally slower than Hashtables
- May require more rotations or recoloring than AVL trees for some operations
- Will be deeper than B-trees, which is disadvantageous for large data sets

### More information below

Wikipedia Page