数据结构之红黑树

红黑树是一种自平衡的二叉查找树，在业务中也应用广泛。

红黑树的特性包括：

1. 节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL 节点，也称为外部节点）都是黑色的。
4. 如果一个节点是红色的，那么它的两个子节点都是黑色的。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些特性确保了红黑树的平衡性，使得其查找、插入和删除操作的时间复杂度都能保持在 O(log n)，其中 n 是树中节点的数量。

在插入和删除节点时，可能会破坏红黑树的特性，此时需要通过旋转（左旋和右旋）和颜色重涂等操作来重新调整树的结构，以恢复红黑树的特性。

红黑树常用于需要高效查找、插入和删除操作，同时要求数据有序存储的场景，例如在许多编程语言的标准库中用于实现关联容器（如 Java 中的 TreeMap ）。