A red-black tree is a type of binary search tree which tries to balance itself after every insertion and deletion of a node. A binary tree is said to be balanced when the lenght of longest path between left and right subtrees under any node is less than 1. Each node in a Red-Black binary search tree stores an extra bit if information which indicated whether a node is of “red” color or “black” color. There are also a few constraints on how red and black nodes should be arranged. Every time a new node is inserted into the tree or a node is removed from the tree, a restructing is done in order to make the red-black tree to adhere to the below constraints:
- Every node is either red or black
- All NULL nodes are considered black
- A red node should not have a red child
- Every path from a given node to any of its descendant NULL nodes should go have the same number of black nodes
TODO: More info along with references.