说说红黑树的结构和特点？

**红黑树的结构** 红黑树是一种 **自平衡二叉查找树**，在插入、删除时通过一系列的 **变色（color flip）** 和 **旋转（rotation）** 操作，保持树的平衡，从而保证查找、插入、删除的时间复杂度为 `O(log n)`。 每个节点包含： * **key / value**（存储数据） * **color**（红色或黑色） * **left / right / parent**（指针） **红黑树的 5 条性质** 1. 每个节点是 **红色** 或 **黑色**。 2. 根节点是 **黑色**。 3. 所有叶子节点（NIL 空节点）都是 **黑色**。 4. 如果一个节点是 **红色**，则它的两个子节点必须是 **黑色**（不能出现连续红节点）。 5. 对于每个节点，从该节点到所有叶子节点的路径上，**黑色节点数量相同**（黑高一致）。 **红黑树的特点** * **平衡性**：不是完全平衡，但保证最长路径不超过最短路径的两倍。 * **查找效率**：`O(log n)`，比普通二叉查找树更稳定。 * **适用场景**：需要频繁插入、删除，同时保持查询高效的场景（如 Java 中 `TreeMap`、`TreeSet`、`HashMap` 树化）。 **插入与删除的自平衡机制** * **插入**：新节点默认为红色，可能破坏红黑树性质，需要通过： * 变色（Color Flip） * 左旋（Left Rotate） * 右旋（Right Rotate） 恢复平衡。 * **删除**：删除黑色节点时可能破坏黑高平衡，需要通过： * 双重黑（Double Black）调整 * 旋转与变色 修复树的结构。 **结构示意**（颜色标注） ``` [10B] / \ [5R] [15R] / \ / \ [3B] [7B] [12B] [18B] ``` B = 黑色，R = 红色