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

1. Search: O(log n)
2. Insertion: O(log n)
3. 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