红黑树：高效自平衡二叉查找树

红黑树（Red-Black Tree）是一种自平衡二叉查找树（BST），它保证了在最坏情况下插入、删除和查找操作的时间复杂度都是O(log n)。

红黑树的每个节点都被涂上红色或黑色。除此之外，红黑树还满足以下五个性质：

1. 根节点是黑色的；
2. 每个节点要么是红色的，要么是黑色的；
3. 每个叶子节点（NIL节点，空节点）都是黑色的；
4. 如果一个节点是红色的，则其子节点必须是黑色的；
5. 从任意一个节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

这些性质保证了红黑树的平衡性，使得它的高度不超过2log(n+1)。

红黑树常用于实现关联数组、集合和映射等数据结构，以及在STL中的set和map容器的实现中。