树

一、树的第一性原理

1. 树解决的本质问题

从抽象层看，树并不是一种具体结构，而是一类问题的解空间表达。

树用于解决以下四类稳定问题：

1. 层级关系的表达（Hierarchy）
2. 局部有序性的维护（Local Order）
3. 动态集合的增删查（Dynamic Set）
4. 在全局约束下进行局部调整（Local Fix under Global Invariant）

任何被称为“树”的结构，本质上都在维护某种不变量（Invariant）。

2. 树的统一抽象模型

所有树结构都可以抽象为：

节点集合 + 约束规则 + 维护策略

后续所有具体树，都是该模型的不同实例化。

二、搜索树问题域（Ordered Set）

1. 问题定义

搜索树要解决的不是“存储”，而是：

如何在动态变化的数据集中，持续维护一个有序集合。

核心操作：

• 查找（Search）
• 插入（Insert）
• 删除（Delete）

核心指标：

• 操作时间复杂度
• 平衡维护成本

三、二叉查找树（BST）——最小约束模型

1. 不变量

• 左子树所有键 < 当前节点
• 右子树所有键 > 当前节点

这是有序性最小约束。

2. 特点

• 结构完全由插入顺序决定
• 不保证平衡
• 最坏情况退化为链表

3. 定位

BST 是理论基线模型，而非工程最终方案。

它回答的是：

如果只维护有序性，会发生什么？

四、失衡问题与“平衡”这一设计目标

1. 核心矛盾

• 有序性需要结构约束
• 动态插入破坏结构

因此引出一个核心设计问题：

是否、以及在多大程度上，应该为“平衡”付出代价？

五、AVL 树 —— 强平衡解

1. 不变量

• 任意节点左右子树高度差 ≤ 1

2. 维护策略

• 单旋 / 双旋

3. 代价与取舍

AVL 追求的是结构最优，而非工程最优。

六、2-3 树 —— 完全平衡的理想模型

1. 不变量

• 所有叶子节点深度一致
• 节点可包含 1 或 2 个键

2. 设计意义

• 理论上的完美平衡
• 插入时通过“分裂”维护结构

3. 局限

• 不适合直接用二叉指针实现

2-3 树更多是概念模型，而非工程结构。

七、红黑树 —— 工程折中解

1. 核心思想

用颜色编码 2-3 树结构，在不改变二叉结构的前提下近似平衡。

2. 不变量（抽象层）

• 黑高一致
• 不存在连续红节点

3. 工程价值

红黑树牺牲“极致平衡”，换取“稳定性能”。

八、搜索树的演进总结

九、堆 —— 极值优先的问题域

1. 问题定义

如何在动态集合中，高效获取最大或最小元素？

2. 不变量

• 父节点 ≥ / ≤ 子节点

3. 特点

• 不维护全序
• 只保证极值正确

堆是放弃有序性以换取性能的典型代表。

十、并查集 —— 连通性抽象

1. 问题定义

元素是否属于同一集合？

2. 不变量

• 每个集合存在唯一代表元

3. 优化本质

• 按秩合并：控制树高
• 路径压缩：延迟优化

并查集是“树思想”在图连通问题中的特化应用。

十一、树结构的选型心智模型

1. 问题 → 结构映射

2. 设计哲学总结

• 没有“最优结构”
• 只有“最合适的约束”