A RedBlack tree is a binary tree where each node have color as an extra attribute, either red or black. By constraining the coloring of the nodes it is ensured that the longest path from the root to a leaf is no longer than twice the length of the shortest path. This means that the tree is balanced. A RedBlack tree must satisfy these properties:
When nodes are removed or deleted, the tree must be transformed to keep these properties. This is done by repainting or rotating nodes.
A newly added node should be red by default. If the parent node is black, the tree is still valid. If both the parent node is red, and there exists a red uncle node, then they should be repainted black, and the grandparent node should be repainted red. (It may be necessary to continue repainting up to the root.) Otherwise, rotations are necessary. If the root ends up red, it should be repainted black.
Search Encyclopedia

Featured Article
