一、树结构基础
1. 二叉查找树（BST）
- 核心规则：左子树所有节点值 < 当前节点值 < 右子树所有节点值，无重复节点。
- 添加规则：小值存左、大值存右、等值不存。
- 遍历方式：
- 前序：当前节点 → 左子节点 → 右子节点
- 中序：左子节点 → 当前节点 → 右子节点
- 后序：左子节点 → 右子节点 → 当前节点
- 层序：按层次从上到下、从左到右遍历
2. 平衡二叉树（AVL 树）
- 核心规则：任意节点左右子树高度差 ≤ 1。
- 旋转机制：添加节点破坏平衡时，通过左旋 / 右旋恢复平衡：
- 左左型：一次右旋
- 左右型：先左旋后右旋
- 右右型：一次左旋
- 右左型：先右旋后左旋
3. 红黑树
- 核心特性：自平衡二叉查找树，通过 “红黑规则” 实现平衡（非高度严格平衡）。
- 红黑规则：
- 节点颜色仅为红 / 黑；
- 根节点必为黑；
- 叶节点（NIL）为黑；
- 红节点的子节点必为黑；
- 任意节点到其叶节点的路径黑节点数相同。
- 添加规则：
- 新节点默认红色（减少规则冲突）；
- 根节点直接设为黑色；
- 父节点为黑：无需操作；
- 父节点为红：根据叔叔节点颜色调整（变色 / 旋转）。
二、Set 系列集合
1. 核心特性
- 无序（LinkedHashSet 除外）、不重复、无索引。
- 无索引：不能用普通 for 循环遍历，无索引操作方法。
2. 实现类对比
表格
| 实现类 | 核心特点 | 底层结构 | 适用场景 |
|---|---|---|---|
| HashSet | 无序、去重、效率最高 | 哈希表（数组 + 链表 + 红黑树） | 普通去重场景（默认选择） |
| LinkedHashSet | 有序（存取一致）、去重 | 哈希表 + 双向链表 | 去重且需保证存取顺序 |
| TreeSet | 可排序、去重 | 红黑树 | 去重且需对元素排序 |
3. 哈希表底层原理
- 结构：JDK8 前为数组 + 链表，JDK8 后为数组 + 链表 + 红黑树（链表长度 > 8 且数组长度≥64 时转红黑树）。
- 存储流程：
- 计算元素哈希值，确定数组存储位置；
- 位置为空则直接存入；
- 位置非空则调用
equals()比较：- 属性值相同：不存入（去重）；
- 属性值不同：JDK8 前新元素存数组，老元素挂其后；JDK8 后新元素挂老元素后。
- 关键要求：存储自定义对象时，必须重写
hashCode()和equals()保证去重逻辑正确。
4. TreeSet 排序规则
表格
| 排序方式 | 实现方式 | 特点 |
|---|---|---|
| 自然排序 | 实体类实现Comparable接口，重写compareTo方法 | 规则绑定实体类（侵入式） |
| 比较器排序 | 创建 TreeSet 时传入Comparator比较器 | 规则与实体类解耦（更灵活） |
- 默认排序规则：
- 数值类型：从小到大；
- 字符 / 字符串：按 ASCII 码升序。
三、集合选择指南
- 元素可重复：
- 默认选
ArrayList（查询快）； - 增删多选
LinkedList（增删快）。
- 默认选
- 元素去重：
- 默认选
HashSet（效率最高）； - 需有序选
LinkedHashSet； - 需排序选
TreeSet（或 List + 排序方法）。
- 默认选
