A red-black tree is a type of self-balancing binary search tree, a data structure used in computing science, typically used to implement associative arrays.
From Wikipedia, Red–black tree:
A red-black tree is a special type of binary tree, used in computer science to organize pieces of comparable data, such as text fragments or numbers.
The leaf nodes of red-black trees do not contain data. These leaves need not be explicit in computer memory — a null child pointer can encode the fact that this child is a leaf — but it simplifies some algorithms for operating on red-black trees if the leaves really are explicit nodes. To save memory, sometimes a single sentinel node performs the role of all leaf nodes; all references from internal nodes to leaf nodes then point to the sentinel node.
Red-black trees, like all binary search trees, allow efficient in-order traversal in the fashion, Left-Root-Right, of their elements. The search-time results from the traversal from root to leaf, and therefore a balanced tree, having the least possible tree height, results in O(log n) search time.
