Red-Black Tree (RBT) Introduction
- November 27, 2019
- Liu, An-Chi 劉安齊
¶ Red-Black Tree Overview
A red-black tree is a special data structure that can automatically balance itself, similar to an AVL tree.
A red-black tree has the following properties:
- Each node is either red or black
- The root must be black
- Every leaf (
NIL) is black - If a node is red, its children must be black
- Every path from the root to a leaf has the same number of black nodes
Following these rules ensures the tree stays balanced during insertions and deletions. A red-black tree guarantees that when the number of nodes is n, the height is at most 2log(n+1).
In practice, it is often used to implement sets and dictionaries. In C++, std::set and std::map are backed by red-black trees.