A RedBlackTree is an extended type of BinaryTree which satisfies the following conditions:

  • Every node is coloured either red or black
  • Every leaf node is coloured black
  • If a node is red, then both of its children are black
  • Every path from the root to a leaf contains the same number of black nodes. This number is called the black-height of the tree.

They guarantee O(log n) time per access.