红黑树是一种自平衡二叉搜索树，其特点是能够在最坏情况下保持相对均衡，从而确保基本的动态操作（插入、删除、查找）时间复杂度为 (O(\log n))。

它广泛用于实现许多计算机系统中的关联数组、符号表、集合和映射等数据结构，如 Java 的 TreeMap 和 C++ 的 STL 中的 map 和 set。

一、主要特点

①、节点颜色

红黑树中的每个节点不是红色就是黑色，节点的颜色是红黑树平衡性质的关键。

②、根节点是黑色

红黑树的根节点总是黑色的。这个性质确保根节点平衡。

③、叶子节点是黑色

这里的叶子节点是指树中所有的空节点（NIL），它们不包含数据，表示子树的结束。

④、红色节点的子节点是黑色

红色节点不能有两个红色子节点。换句话说，红色节点的子节点必须是黑色（即不能有连续的红色节点）。这叫做“红色节点的约束”。

⑤、从任意节点到其所有子叶的路径包含相同数量的黑色节点

对于任意节点，从该节点到其后代叶子节点的所有路径，必须包含相同数量的黑色节点（称为“黑色高度”相同）。

⑥、自平衡性

虽然红黑树的结构不像 AVL 树那样严格平衡，但它通过颜色规则，确保了树的高度在 (2 \log n) 之内，保证了操作的高效性。

⑦、时间复杂度

在红黑树上，常见操作（如插入、删除、查找）的时间复杂度为 (O(\log n))，因为树的高度最多为 (2 \log n)。

二、优势

相较于其他平衡树（如 AVL 树），红黑树通过牺牲部分平衡性，减少了调整操作的复杂度。

它适用于插入和删除操作频繁的场景，因为插入和删除操作后的重新平衡操作（颜色翻转、旋转）相对较少。

三、旋转和颜色调整

当插入或删除节点后破坏了红黑树的性质，必须通过旋转（左旋、右旋）和颜色变换来恢复红黑树的平衡。