A red–black tree is a self-balancing binary search tree which supports the operation search, find predecessor, find successor, find minimum, find maximum, insertion and deletion in O(log n)-time. In addition to the requirements imposed on a binary search tree, the following must be satisfied to be a red–black tree: 1) A node is either red or black . 2) The root is black. 3) All leaves (NIL) are black. 4) If a node is red, then both its children are black. 5) Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. If there is a modification in RB tree due to insertion or deletion of any element, the new tree is then rearranged and repainted to restore the properties.