Five Properties of Red-Black Trees

• Every node is red or black
• The root is black
• Null leaves are black (this concerns leaf nodes and nodes of degree one: degree 0 and degree 1)
• The children of a red node must be black (no simple path from the root to a null leaf contains consecutive red nodes)
• Every simple path from the root to any null leaf contains the same number of black nodes

Therefore, an all-black path is the shortest, and longest< 2*shortest

Building the Tree

• 1 A newly inserted node is red; first build the red-black tree using plain binary-search-tree insertion
• 2 After inserting, recolour and rotate

Cases When Building the Tree (inserted node is red)

• 1 If the inserted node is the root, simply colour it black
• 2 If the inserted node is a child and its parent is black, no adjustment is needed
• 3 If the inserted node is a child and its parent is red (there must be a grandparent, and it is black, because the parent is red), there is also always an uncle (a null leaf counts). If the uncle is red, colour the parent and uncle black, colour the grandparent red-> colouring it red may cause a violation, so treat the grandparent as the newly inserted node and repeat upwards
• 4 If the inserted node is a child and its parent is red (there must be a grandparent), there is also always an uncle (a null leaf counts). If the uncle is black,
  and the parent P’s value lies between the new node N and the grandparent G (N is on the same side as its parent, e.g. the parent is a left child and N is also a left child, or the parent is a right child and N is also a right child), rotate at G: if the left side is heavy (N inserted into the left subtree), rotate right; if the right side is heavy (N inserted into the right subtree), rotate left (skirt shape), and swap colours: swap the colours of G and P

  Right rotation: make the grandparent the right child of the parent
  Left rotation: make the grandparent the left child of the parent

• 5 If the inserted node is a child and its parent is red (there must be a grandparent), there is also always an uncle (a null leaf counts). If the uncle is black but N is on the opposite side from its parent, rotate P (in case 4 we rotated G). If the parent is a left child, rotate P left; if the parent is a right child, rotate P right. This brings us back to case 4, so just apply the case 4 method. E.g. if the parent is on the right and N is on the left, rotate right at the parent; now both the parent and N are on the right, and then apply the right-side operation from case 4 above

Summary

• If the inserted node is the root, colour it black.
• If the parent is black, just insert.
• If both the parent and the uncle are red, colour both of them black and the grandparent red, then treat the grandparent as the node being inserted and repeat recursively.
• If the parent and the inserted node are on the same side, colour the parent black and the grandparent red; both on the left: rotate right, both on the right: rotate left. This is done at the grandparent.
• If the parent is red and the uncle is black and N is not on the same side as its parent, convert to the same-side case (N on the right: rotate left at the parent; N on the left: rotate right at the parent), then perform step four.