红黑树

一、红黑树基础定义

红黑树（Red Black Tree）是一种自平衡的二叉搜索树（BST），也被称为对称二叉B树。它通过颜色标记（红/黑）和特定规则维持树的平衡，避免普通二叉搜索树退化为链表，保证操作效率稳定。

---

二、红黑树五大核心性质

1. 节点颜色：每个节点只能是红色或黑色
2. 根节点性质：根节点必须为黑色
3. 叶子节点性质：所有叶子节点（NULL节点）均为黑色
4. 红色节点约束：红色节点的两个子节点必须为黑色（即不存在两个连续的红色节点）
5. 路径黑节点数：从任一节点到其叶子节点的所有路径，包含的黑色节点数量相同

这些性质共同保证了红黑树的平衡性，最长路径的高度不超过最短路径的2倍。

---

三、平衡机制与调整方式

当红黑树进行插入或删除操作时，可能会破坏上述性质，此时需通过以下两种方式调整：

• 变色：修改节点颜色，消除连续红色节点或调整路径黑节点数
• 旋转：包括左旋、右旋操作，改变树的结构，维持平衡

调整操作的时间复杂度为O(1)，不会影响整体操作效率。

---

四、时间复杂度分析

• 查找操作：O(log n)，红黑树作为二叉搜索树，查找效率与树高相关，平衡状态下树高为log₂n
• 插入操作：O(log n)，查找插入位置需O(log n)，后续调整为O(1)
• 删除操作：O(log n)，查找删除位置需O(log n)，后续调整为O(1)

所有操作的时间复杂度均稳定为O(log n)，不会出现普通二叉搜索树退化为链表时的O(n)最坏情况。

---

五、面试高频问题解析

1. 问：红黑树的定义是什么？为什么需要红黑树？答： 红黑树是自平衡的二叉搜索树，通过颜色标记和五大性质维持平衡。普通二叉搜索树在数据有序时会退化为链表，操作效率降为O(n)，红黑树通过平衡机制保证树高稳定，使操作时间复杂度始终为O(log n)。

2. 问：红黑树的五大性质是什么？答： ①节点为红或黑；②根节点为黑；③叶子节点（NULL）为黑；④红色节点的子节点为黑；⑤任一节点到叶子的所有路径黑节点数相同。这些性质保证了树的平衡性。

3. 问：红黑树如何维持平衡？调整方式有哪些？答： 红黑树通过变色和旋转两种方式维持平衡。变色用于消除连续红色节点，旋转（左旋/右旋）用于调整树的结构，两者结合可快速恢复红黑树的五大性质，调整操作时间复杂度为O(1)。

4. 问：红黑树和AVL树的区别是什么？答： 红黑树通过颜色标记和路径黑节点数维持平衡，树高最长不超过最短路径的2倍；AVL树通过左右子树高度差≤1维持平衡，平衡更严格。红黑树的插入删除调整次数更少，更适合频繁增删的场景，如Java的TreeMap、HashMap均采用红黑树实现。s