红黑树

红黑树是一种自平衡二叉搜索树，其特点是能够在最坏情况下保持相对均衡，从而确保基本的动态操作（插入、删除、查找）时间复杂度为 (O(\log n))。它广泛用于实现许多计算机系统中的关联数组、符号表、集合和映射等数据结构，如 Java 的 TreeMap 和 C++ 的 STL 中的 map 和 set。

红黑树的主要特点有以下几点：

1. 节点颜色

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

2. 根节点是黑色

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

3. 叶子节点是黑色

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

4. 红色节点的子节点是黑色

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

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

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

6. 自平衡性

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

7. 时间复杂度

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

红黑树的优势：

• 相较于其他平衡树（如 AVL 树），红黑树通过牺牲部分平衡性，减少了调整操作的复杂度。它适用于插入和删除操作频繁的场景，因为插入和删除操作后的重新平衡操作（颜色翻转、旋转）相对较少。

红黑树的旋转和颜色调整：

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