Red black tree
A red black tree is a binary tree.
Each edge is considered to be either »black« or »red«.
Properties of a red black tree
Edges:
- The number of black edges on every path from the root to a leaf is constant.
- No two red edges are adjacent.
Length of paths:
- If the number of nodes in a tree is n, the upper bound of a length of a path is O(log n).
- If p is the length of the shortest path, the maximum length of a path is 1 + 2p.
If a node has exactly one child, the edge from this node to this child is red.
Implementations with colored nodes instead of colored edges
Apparently, some implementation of red-black trees do not color the edges of the trees but the nodes. The color of this node is then to be interpreted as the color of the edge that leads to the node.
Thus, the color of the root node is meaningless. For convenience, it might be colored black, however.
Access times
The time it takes to search, insert or delete a node is O(log n) (n being the number of nodes).