树与红黑树基础

一句话定义

树是用父子节点组织数据的层次结构；红黑树是一种自平衡二叉搜索树，在插入/删除时通过染色与旋转把高度压在 O(log n)，HashMap 桶内冲突过长时会用它替代链表。

专题延伸（HashMap 树化阈值、CHM 同结构）：map-concurrency-compare §2.3

---

为什么要学

场景	和树的关系
HashMap / ConcurrentHashMap 单桶冲突	链表过长 → 红黑树（JDK 8+）
TreeMap / TreeSet	底层就是红黑树，key 有序
Android / 数据库索引	常听到 B 树、B+ 树（磁盘友好，面试知道区别即可）
算法题	BST、遍历、平衡树是高频背景

---

树的基本概念

        A          ← 根 root
       / \
      B   C        ← 内部节点
     /   / \
    D   E   F      ← 叶子（无子节点）

术语	含义
根	最顶层节点，入口
子 / 父	直接相连的上下级
叶子	没有子节点的节点
深度	从根到该节点的边数
高度	树中最深叶子的深度（决定查找最坏耗时）

二叉树：每个节点最多 2 个子节点（左、右）。

---

二叉搜索树（BST）

规则：左子树所有 key < 当前节点 < 右子树所有 key。

• 查找 / 插入 / 删除（平均）：沿比较向左或向右，类似二分。
• 问题：若 key 有序插入（1,2,3,4,5…），树退化成链表，高度 = n，复杂度变 O(n)。

所以需要 平衡树：在增删时自动调整形状，把高度控制在 O(log n)。

---

红黑树（面试够用版）

是什么：一种 BST + 颜色标记（红/黑）+ 固定规则 的自平衡树。不要求「完美平衡」，只保证最长路径不超过最短路径的 2 倍，从而高度 ≤ 2 log(n+1)。

五条性质（背大意即可）：

1. 节点非红即黑
2. 根是黑色
3. 叶子（NIL 空节点）视为黑色
4. 红节点的子节点必须是黑（不能连续红）
5. 从任意节点到其每个叶子的路径上，黑节点数量相同

为何够用：增删后若破坏规则，通过 变色 + 左旋/右旋 局部修复，均摊 O(log n)。

和 AVL 对比（一句话）：

	红黑树	AVL
平衡程度	较松	更严
查找	略慢一点点	略快
插入删除	旋转较少，写多场景常用	旋转更多
Java 集合	HashMap 树化、TreeMap	标准库少用

---

HashMap 里为什么用红黑树？

JDK 8+ 单桶结构：

形态	何时	查找复杂度
链表	冲突少、桶短	O(k)，k = 链长
红黑树	链表 > 8 且 table.length >= 64	O(log k)

树化阈值 8、退化阈值 6：泊松分布下，正常 hash 下链长到 8 的概率极低；设阈值避免「为极少数坏 hash 全程维持树」的开销。链又缩到 ≤6 时退化为链表，省内存。

恶意或极差 hashCode() 仍可能把很多 key 打进同一桶——树化是兜底，不能替代良好的 equals/hashCode。

---

其他「树」常听到但不深挖

名称	一句话	常见出处
B 树 / B+ 树	多路、矮胖，减少磁盘 IO	MySQL InnoDB 索引、文件系统
堆（完全二叉树）	父 ≤ 子（小顶堆）或反之	PriorityQueue、TopK
Trie 字典树	按字符串前缀分叉	自动补全、IP 路由
并查集（森林）	多棵树维护连通分量	算法题、网络合并

Android 日常业务代码里，红黑树 + 堆 出现频率最高；B+ 树在讲数据库/缓存落盘时顺带了解即可。

---

和后续专题的关系

---

复习检查题

1. BST 最坏情况为什么会退化？红黑树解决的是什么？

   答：BST 在有序或近似有序插入时变「斜链」，高度 = n。红黑树通过颜色规则与旋转限制高度为 O(log n)，避免单桶或 TreeMap 上查找/插入退化到线性。

2. HashMap 为什么在链表很长时转红黑树，而不是一开始就用树？

   答：正常 hash 下链很短，链表更省内存、常数小；只有冲突极端时才树化，用空间和时间换最坏情况下的 O(log k)。还有退化机制，避免树维护成本常驻。

3. TreeMap 和 HashMap 选型差异？

   答：需要 key 有序、范围查询、O(log n) 可接受 → TreeMap（红黑树）。只要快速定位、不要求序 → HashMap 均摊 O(1)。TreeMap 要求 key 可比较（Comparable 或 Comparator）。

4. 红黑树和 B+ 树分别更适合什么存储介质？

   答：红黑树适合 内存 中频繁增删查的 map/set。B+ 树叶子串链表、节点扇出大、树矮，适合 磁盘块 读写，减少随机 IO（数据库索引）。

速记

• 树 = 层次结构；BST = 左小右大。
• 红黑树 = 自平衡 BST，Java HashMap 桶内 / TreeMap 底层。
• 链表短用链，链 > 8 且表 ≥ 64 树化；树 ≤ 6 退回链。
• 要排序用 TreeMap；要快查用 HashMap。