Red-Black Properties

Source

These are the properties that need to be maintained for a Red-Black Tree to work correctly (from CLRS).

  1. Every Node is either Red or Black.
  2. The Root is Black.
  3. Every Leaf (Nil) is Black.
  4. If a Node is Red then both of its children are Black.
  5. For each Node, all simple paths from the node to descendant leaves contain the same number of Black Nodes.

When the properties are true the height of a tree with n nodes is \(O(\log(n))\).