红黑树，以及其在C++的set、map等数据结构中应用

红黑树介绍：

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在插入和删除操作后通过一系列的旋转和着色操作来维持平衡。红黑树的命名来自于节点上的额外颜色属性，每个节点要么是红色，要么是黑色。

---

红黑树的特性：

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

这些特性保证了红黑树的关键性质：任意节点到其子孙节点的最长简单路径不超过其他路径的两倍，从而确保了红黑树的平衡性。

---

在C++的标准库中，`std::set`和`std::map`：

这两种容器都是基于红黑树实现的

- `std::set`是一个有序的集合容器，它存储唯一的值。在`std::set`中，元素按照从小到大的顺序进行排序，并且插入、查找、删除操作的平均时间复杂度为O(logN)。通过使用红黑树作为底层数据结构，`std::set`能够高效地支持这些操作。

- `std::map`是一个有序的键-值对容器，它存储唯一的键，并根据键的顺序进行排序。在`std::map`中，键值对按照键的从小到大的顺序进行排序，并且插入、查找、删除操作的平均时间复杂度为O(logN)。`std::map`的实现使用红黑树来维护键值对的有序性。

红黑树的自平衡特性确保了在插入和删除元素时，树的高度保持相对较小，从而保证了高效的查找和遍历操作。红黑树的平衡性是通过旋转和节点着色来维持的。旋转操作用于调整树的结构，而着色操作用于满足红黑树的特性。