VietMX Staff asked 3 years ago
A red-black tree is a binary search tree in which
- each node has a color (red or black) associated with it (in addition to its key and left and right children). This can be saved in memory as a single bit (e.g. ‘red’ = 1, ‘black’ = 0).
- the following 3 properties hold:
- (root property) The root of the red-black tree is black
- (red property) The children of a red node are black.
- (black property) For each node with at least one null child, the number of black nodes on the path from the root to the null child is the same. This is sometimes known as the black-depth.
- The height of the red-black tree is at most
2*log(n + 1)
Red-black trees maintain a slightly looser height invariant than AVL trees. Because the height of the red-black tree is slightly larger, lookup will be slower in a red-black tree. However, the looser height invariant makes insertion and deletion faster. Also, red-black trees are popular due to the relative ease of implementation.
