js--18

一、树结构基础

1. 二叉查找树（BST）

• 核心规则：左子树所有节点值 < 当前节点值 < 右子树所有节点值，无重复节点。
• 添加规则：小值存左、大值存右、等值不存。
• 遍历方式：
  • 前序：当前节点 → 左子节点 → 右子节点
  • 中序：左子节点 → 当前节点 → 右子节点
  • 后序：左子节点 → 右子节点 → 当前节点
  • 层序：按层次从上到下、从左到右遍历

2. 平衡二叉树（AVL 树）

• 核心规则：任意节点左右子树高度差 ≤ 1。
• 旋转机制：添加节点破坏平衡时，通过左旋 / 右旋恢复平衡：
  • 左左型：一次右旋
  • 左右型：先左旋后右旋
  • 右右型：一次左旋
  • 右左型：先右旋后左旋

3. 红黑树

• 核心特性：自平衡二叉查找树，通过 “红黑规则” 实现平衡（非高度严格平衡）。
• 红黑规则：
  1. 节点颜色仅为红 / 黑；
  2. 根节点必为黑；
  3. 叶节点（NIL）为黑；
  4. 红节点的子节点必为黑；
  5. 任意节点到其叶节点的路径黑节点数相同。
• 添加规则：
  • 新节点默认红色（减少规则冲突）；
  • 根节点直接设为黑色；
  • 父节点为黑：无需操作；
  • 父节点为红：根据叔叔节点颜色调整（变色 / 旋转）。

二、Set 系列集合

1. 核心特性

• 无序（LinkedHashSet 除外）、不重复、无索引。
• 无索引：不能用普通 for 循环遍历，无索引操作方法。

2. 实现类对比

表格

3. 哈希表底层原理

• 结构：JDK8 前为数组 + 链表，JDK8 后为数组 + 链表 + 红黑树（链表长度 > 8 且数组长度≥64 时转红黑树）。
• 存储流程：
  1. 计算元素哈希值，确定数组存储位置；
  2. 位置为空则直接存入；
  3. 位置非空则调用equals()比较：
     • 属性值相同：不存入（去重）；
     • 属性值不同：JDK8 前新元素存数组，老元素挂其后；JDK8 后新元素挂老元素后。
• 关键要求：存储自定义对象时，必须重写hashCode()和equals()保证去重逻辑正确。

4. TreeSet 排序规则

表格

• 默认排序规则：
  • 数值类型：从小到大；
  • 字符 / 字符串：按 ASCII 码升序。

三、集合选择指南

1. 元素可重复：
   • 默认选ArrayList（查询快）；
   • 增删多选LinkedList（增删快）。
2. 元素去重：
   • 默认选HashSet（效率最高）；
   • 需有序选LinkedHashSet；
   • 需排序选TreeSet（或 List + 排序方法）。