A Red$-$Black tree is a type of Binary tree in which each node is either red or black. The trees are

self$-$balancing and as such, maintain consistent logarithmic complexity for insert, delete, and search

methods. Red$-$Black trees have several basic rules:

$$ The root must be black

$$ Each node is either red or black

$$ Red nodes cannot have red children

$$ Black Property: Every path from a node to its descendant null nodes $($leaves$)$ has the same number

of black nodes.

$$ Leaf Property: All leaves $($NIL nodes$)$ are black.