A red-BLACK tree is a self-balancing binary search tree with one extra bit at each node, which is commonly read as the colour (red or black). These colours are used to keep the tree balanced as insertions and deletions are made. The tree's balance isn't ideal, but it's good ENOUGH to cut down on searching TIME and keep it around O(log N), where n is the total number of nodes in the tree. Rudolf Bayer invented this tree in 1972.

It's worth noting that, because each node only needs 1 bit of memory to store the colour information, these trees have the same memory footprint as a traditional (uncoloured) binary search tree.

Points to remember:

• Every node of a red-black tree has a colour, which is either red or black.
• The tree's root is always black.
• There are no red nodes that are NEXT to one other (A red node is not allowed to have a red parent or red child).
• There is the same number of black nodes on every path from a node (including root) to any of its descendant's NULL nodes.