A Red-Black Tree (RBT) is a type of Binary Search tree with one extra bit of storage per node, i.e. its color that can either be red or black. Now the nodes can have any of the color (red, black) through root to leaf node. These trees are such that they guarantee O(log n) time in the worst case for searching.
Each node of a red black tree contains field color, key, left, right and p (parent). If a child or a parent node does not exist, then the pointer field of that node has NULL value.