A red-black tree is a self-balanced binary search tree with some extra properties, which is the color. Each node in the binary tree stores one extra bit of information, which is known as color and can have either red or black as values. Like an AVL tree, a red-black tree is also used for real-time applications as the average and worst case complexity is also logarithmic. A sample red-black tree looks like this: