What is a red-black tree?

A red-black tree is a type of self-balancing binary search tree where each node has a color—red or black. It guarantees that the path from the root to any leaf is no more than roughly twice as long as the shortest path, ensuring insertion, deletion, and search operations run in O(log n) time.

Main properties of a red-black tree:

• Each node is either red or black.
• The root is always black.
• All leaves (NIL nodes) are considered black.
• If a node is red, then both its children are black (no two red nodes in a row).
• For each node, all paths to its descendant leaves contain the same number of black nodes.

An example of its use in Java is the TreeMap class, which is based on a red-black tree, providing ordered storage of keys with efficient access.