A binary tree is an efficient way to store and retrieve ordered data if the tree is balanced. However keeping a binary tree balanced is not a trivial task. With a simple binary tree it simply degrades to a linked list if the data is entered in an ordered fashion. Various strategies exist for keeping a tree balanced. Insertion does not require two phases, unlike the AVL tree, another self-balancing binary search tree, so it is much more efficient.
Every node is colored either red or black.
Every red node that is not a leaf has only black children. Every path from the root to a leaf contains the same number of black nodes. The root node is black. We have have developed a Java applet to show the workings of a Red-Black tree. A dichromatic framework for balanced trees.