红黑树的特性？

红黑树（Red-Black Tree）是自平衡二叉搜索树的一种，特点是在插入、删除后通过**变色 + 旋转**保持树的高度平衡，从而保证**查找、插入、删除的时间复杂度都是 O(log n)**。 ## 1. 红黑树的 5 条特性 假设每个节点要么是 **红色**，要么是 **黑色**： 1. **节点要么是红色，要么是黑色**（二元着色）。 2. **根节点必须是黑色**。 3. **所有叶子节点（NIL/空节点）都是黑色**（实现中通常用哨兵节点表示）。 4. **红色节点的两个子节点必须是黑色**（不能有两个连续的红色节点，即不能出现“红红相连”）。 5. **从任意节点到其所有后代叶子节点的路径上，黑色节点的数量相同**（黑高一致性）。 ## 2. 这些特性保证了什么？ * 通过限制红色节点不能相邻 + 黑色高度一致，保证树的高度接近 log₂(n)。 * 在最坏情况下，红黑树的高度不超过 **2 × log₂(n+1)**，比普通二叉搜索树好很多（普通 BST 可能退化成链表）。 ## 3. 平衡维护方式 * **插入**：新节点着色为红色 → 如果违反规则（比如出现连续两个红节点），通过**变色**或\*\*旋转（左旋/右旋）\*\*修复。 * **删除**：如果删除的是黑节点，可能破坏黑高一致性 → 通过**兄弟节点颜色判断** + **旋转 + 变色**修复。 ## 4. 应用场景 * Java `TreeMap`、`TreeSet`、`ConcurrentSkipListMap`（早期 JDK 实现） * Linux 内核的调度器、内存管理 * C++ STL 的 `map`、`set` ### 记忆口诀 1. **根黑叶黑**：根节点黑色，空节点也黑色。 2. **红不连**：红节点子节点一定是黑的。 3. **黑路等长**：任意节点到叶子的黑色节点数一样。