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 heights of left subtree and right subtree differ by not more than 1. This ensures that the tree does not lean too much on either side so that data can be efficiently searched.
Each node in a Red-Black binary search tree stores an extra bit if information which indicates 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 re-structuring is done in order to make the red-black tree to adhere to the below constraints:
- Every node is either red or black
- All
NULLnodes 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.