树与红黑树基础

一句话定义

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

代码索引

主题	Lab 说明	源码
树的遍历方式 / BST 基本操作	tree-traversal-and-bst	TreeTraversalAndBstDemo.kt
HashMap 桶内树化延伸	map-concurrency-compare	HashMapIndexAlgorithmDemo.java

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

为什么要学

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

树的基本概念

先把树想成“组织架构图”或“文件夹层级”：

顶层入口只有一个根节点（root）
每个节点可以往下连若干子节点
节点之间天然形成“父 → 子”的层次关系
适合表达分层结构、范围缩小、递归问题

text

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

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

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

二叉树 vs 二叉搜索树（BST）

这两个概念很容易混：

概念	约束	是否要求有序
二叉树	每个节点最多 2 个孩子	不要求
二叉搜索树（BST）	先是二叉树，再满足左小右大	要求

也就是说：

所有 BST 都是二叉树
不是所有二叉树都是 BST

例如下面这个结构是二叉树，但不是 BST，因为左边节点比根大、右边节点比根小：

text

    10
   /  \
  99   3

树的几种遍历方式

对应 Lab：tree-traversal-and-bst · TreeTraversalAndBstDemo.kt

遍历就是“按某种顺序，把整棵树的节点访问一遍”。

深度优先遍历（DFS）

深度优先的特点是：先沿一条路走到底，再回头。最常见有三种。

1. 前序遍历（Preorder）

顺序：根 → 左 → 右

text

        A
       / \
      B   C
     / \   \
    D   E   F

前序：A B D E C F

适合什么：

复制树结构
序列化树
先处理当前节点，再处理子树的场景

优劣：

优点	缺点
根节点最先拿到，适合“先做当前节点决策”	对 BST 来说不能直接得到有序结果

2. 中序遍历（Inorder）

顺序：左 → 根 → 右

text

        A
       / \
      B   C
     / \   \
    D   E   F

中序：D B E A C F

适合什么：

BST 最重要：中序遍历结果天然升序
验证 BST 实现是否正确

优劣：

优点	缺点
对 BST 能直接得到升序结果，最适合验证“左小右大”	对普通二叉树只是某种顺序，不一定有额外业务意义

3. 后序遍历（Postorder）

顺序：左 → 右 → 根

text

        A
       / \
      B   C
     / \   \
    D   E   F

后序：D E B F C A

适合什么：

删除树
先处理完子节点，再汇总父节点的场景
计算目录大小、表达式求值等

优劣：

优点	缺点
子问题先算完，再处理父节点，适合释放/汇总类逻辑	不能像前序那样立刻拿到根，也不能像中序那样天然有序

广度优先遍历（BFS / 层序遍历）

顺序：按层一层层访问，通常借助队列。

text

        A
       / \
      B   C
     / \   \
    D   E   F

层序：A B C D E F

适合什么：

看层级关系
最短层数问题
UI 树、组织树、评论树的逐层展示

优劣：

优点	缺点
最符合“层级展示”直觉，便于看树是不是歪了	需要额外队列；对 BST 排序帮助不大

怎么选

目标	更适合的遍历
先处理当前节点	前序
拿到 BST 升序结果	中序
先处理完孩子再处理父节点	后序
按层看结构	层序

对 BST 学习来说，中序遍历最重要，因为你写完插入 / 删除后，最快的验证方法就是看中序结果是不是升序。

二叉搜索树（BST）

对应 Lab：tree-traversal-and-bst · TreeTraversalAndBstDemo.kt

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

text

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

上面是 BST，因为对每个节点都满足：

左边都更小
右边都更大

BST 为什么比普通二叉树更适合查找

普通二叉树只有“最多两个孩子”的结构，不保证顺序；查某个值时，很多时候只能整棵树挨个看。

BST 多了“左小右大”这条规则，所以查找时可以像二分一样排除一半方向：

目标值小于当前节点 → 只去左边
目标值大于当前节点 → 只去右边
相等 → 直接命中

所以 BST 的核心价值不是“长得像树”，而是它的有序性可以剪枝。

BST 的实现直觉：查找 / 插入 / 删除

1. 查找

从根开始比较：

小了往左
大了往右
相等就返回

这和数组二分的共同点是“每次都缩小范围”，但 BST 缩小的是子树范围，不是数组下标区间。

2. 插入

插入其实就是“按查找路径一路往下，找到空位挂上去”：

比当前节点小 → 继续找左子树的空位
比当前节点大 → 继续找右子树的空位
找到 null → 新节点就放这里

3. 删除

删除是 BST 最难的一步，因为要分 3 种情况：

删除目标	做法
叶子节点	直接删
只有一个孩子	让孩子顶上来
有两个孩子	用右子树最小节点（中序后继）或左子树最大节点替换，再删那个替换节点

一个最小 Kotlin 思路（方便你自己实现）

kotlin

class IntNode(
    var value: Int,
    var left: IntNode? = null,
    var right: IntNode? = null,
)

kotlin

fun search(node: IntNode?, target: Int): IntNode? {
    var current = node
    while (current != null) {
        current = when {
            target < current.value -> current.left
            target > current.value -> current.right
            else -> return current
        }
    }
    return null
}

kotlin

fun insert(node: IntNode?, value: Int): IntNode {
    node ?: return IntNode(value)
    when {
        value < node.value -> node.left = insert(node.left, value)
        value > node.value -> node.right = insert(node.right, value)
    }
    return node
}

这两段代码最值得你先自己手写，因为它们直接体现了 BST 的核心规则：左小右大 + 递归下降。

BST 的优劣

维度	BST
优点	结构清楚、容易实现、查找/插入/删除思路直观
缺点	不保证平衡，输入有序时容易退化
平均复杂度	`O(log n)`
最坏复杂度	`O(n)`

BST 最大问题：有序输入会退化

如果连续插入 1,2,3,4,5，BST 会变成：

text

这时它已经很像单链表：

查找最坏 O(n)
插入最坏 O(n)
删除最坏 O(n)

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

红黑树（面试够用版）

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

“红”和“黑”是什么意思

“红 / 黑”不是业务意义，也不是排序依据，而是每个节点额外带的状态位：

节点要么红色，要么黑色
颜色是给“平衡修复”用的辅助标记
插入 / 删除后，通过看颜色关系决定是变色还是旋转

你可以把它理解成：

BST 只有“值”和“左右孩子”
红黑树 = BST + 一个颜色字段 + 一套修复规则

五条性质（背大意即可）

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

红黑树和 BST 的区别

维度	BST	红黑树
本质	有序二叉树	自平衡 BST
排序规则	左小右大	左小右大
是否维护平衡	不维护	维护“不要太歪”
有序输入	容易退化成链	会通过修复保持 `O(log n)` 高度
实现复杂度	低	高

红黑树是如何构建的

红黑树不是“先算出完美结构再一次性建好”，而是：

先按 BST 规则插入
插入后检查是否违反红黑规则
若违规，通过 变色 + 左旋 / 右旋 局部修复

所以红黑树的本质是：

查找路径像 BST
插入 / 删除后多了一步平衡修复

形象理解：为什么它不容易退化成链

BST 像“只管左小右大、不管站队形状”的队伍；如果输入一直递增，所有人都往右边站，最后排成一条长队。

红黑树像“有管理员盯着队伍”：

允许你偏一点
但不允许连续一边长太多
一旦局部拉成长杆，就把中间的人提上来（旋转）或重新分配颜色（变色）

例如插入 10, 20, 30：

普通 BST 会变成 10 → 20 → 30 的右斜链
红黑树会在局部修复后变成更矮的结构，例如：

text

   20(B)
  /    \
10(R) 30(R)

为何够用

增删后若破坏规则，通过 变色 + 左旋/右旋 局部修复，均摊 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+ 树在讲数据库/缓存落盘时顺带了解即可。

和后续专题的关系

复习检查题

二叉树和 BST 的区别是什么？答：二叉树只要求每个节点最多两个孩子，不要求有序；BST 则在二叉树基础上再满足“左小右大”，因此能沿比较路径快速查找。
树的遍历方式里，为什么中序遍历对 BST 最重要？答：因为 BST 满足左小右大，所以中序遍历结果天然升序；它既是最常用的输出顺序，也是验证插入/删除实现是否正确的最快方法。
BST 最坏情况为什么会退化？红黑树解决的是什么？答：BST 在有序或近似有序插入时变“斜链”，高度 = n。红黑树通过颜色规则与旋转限制高度为 O(log n)，避免单桶或 TreeMap 上查找/插入退化到线性。
HashMap 为什么在链表很长时转红黑树，而不是一开始就用树？答：正常 hash 下链很短，链表更省内存、常数小；只有冲突极端时才树化，用空间和时间换最坏情况下的 O(log k)。还有退化机制，避免树维护成本常驻。
TreeMap 和 HashMap 选型差异？答：需要 key 有序、范围查询、O(log n) 可接受 → TreeMap（红黑树）。只要快速定位、不要求序 → HashMap 均摊 O(1)。TreeMap 要求 key 可比较（Comparable 或 Comparator）。
红黑树和 B+ 树分别更适合什么存储介质？答：红黑树适合内存中频繁增删查的 map/set。B+ 树叶子串链表、节点扇出大、树矮，适合 磁盘块 读写，减少随机 IO（数据库索引）。

对应实验

Lab	说明	源码
tree-traversal-and-bst	二叉树四种遍历 + BST 查找/插入/删除	TreeTraversalAndBstDemo.kt
map-concurrency-compare	HashMap 桶内树化、链表与红黑树切换背景	HashMapIndexAlgorithmDemo.java

速记

树 = 层次结构；二叉树 = 每个节点最多两个孩子；BST = 左小右大。
遍历里最重要的是中序：对 BST 会得到升序结果。
红黑树 = 自平衡 BST，Java HashMap 桶内 / TreeMap 底层。
链表短用链，链 > 8 且表 ≥ 64 树化；树 ≤ 6 退回链。
要排序用 TreeMap；要快查用 HashMap。

树与红黑树基础 ​

一句话定义 ​

代码索引 ​

为什么要学 ​

树的基本概念 ​

二叉树 vs 二叉搜索树（BST） ​

树的几种遍历方式 ​

深度优先遍历（DFS） ​

1. 前序遍历（Preorder） ​

2. 中序遍历（Inorder） ​

3. 后序遍历（Postorder） ​

广度优先遍历（BFS / 层序遍历） ​

怎么选 ​

二叉搜索树（BST） ​

BST 为什么比普通二叉树更适合查找 ​

BST 的实现直觉：查找 / 插入 / 删除 ​

1. 查找 ​

2. 插入 ​

3. 删除 ​

一个最小 Kotlin 思路（方便你自己实现） ​

BST 的优劣 ​

BST 最大问题：有序输入会退化 ​

红黑树（面试够用版） ​

“红”和“黑”是什么意思 ​

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

红黑树和 BST 的区别 ​

红黑树是如何构建的 ​

形象理解：为什么它不容易退化成链 ​

为何够用 ​

和 AVL 对比（一句话） ​

HashMap 里为什么用红黑树？ ​

其他“树”常听到但不深挖 ​

和后续专题的关系 ​

复习检查题 ​

对应实验 ​

速记 ​

树与红黑树基础

一句话定义

代码索引

为什么要学

树的基本概念

二叉树 vs 二叉搜索树（BST）

树的几种遍历方式

深度优先遍历（DFS）

1. 前序遍历（Preorder）

2. 中序遍历（Inorder）

3. 后序遍历（Postorder）

广度优先遍历（BFS / 层序遍历）

怎么选

二叉搜索树（BST）

BST 为什么比普通二叉树更适合查找

BST 的实现直觉：查找 / 插入 / 删除

1. 查找

2. 插入

3. 删除

一个最小 Kotlin 思路（方便你自己实现）

BST 的优劣

BST 最大问题：有序输入会退化

红黑树（面试够用版）

“红”和“黑”是什么意思

五条性质（背大意即可）

红黑树和 BST 的区别

红黑树是如何构建的

形象理解：为什么它不容易退化成链

为何够用

和 AVL 对比（一句话）

HashMap 里为什么用红黑树？

其他“树”常听到但不深挖

和后续专题的关系

复习检查题

对应实验

速记