Red Black Tree

An example of a red-black tree is shown below:

Property and Operations

• Property:
  1. (root property) The root of the red-black tree is black
  2. (red property) The children of a red node are black.
  3. (black property) For each node with at least one null child, the number of black nodes on the path from the root to the null child is the same.
• RBT-Insertion
• RBT-Deletion