树

一、树的第一性原理

1. 树解决的本质问题

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

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

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

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

2. 树的统一抽象模型

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

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

抽象维度 含义
节点 承载数据或状态
约束 必须始终成立的不变量
维护 插入、删除时的修复策略

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

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

1. 问题定义

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

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

核心操作：

核心指标：

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

1. 不变量

这是有序性最小约束。

2. 特点

3. 定位

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

它回答的是：

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

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

1. 核心矛盾

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

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

五、AVL 树 —— 强平衡解

1. 不变量

2. 维护策略

3. 代价与取舍

维度 结论
查找 极快
插入/删除 代价高
实现复杂度 高

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

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

1. 不变量

2. 设计意义

3. 局限

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

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

1. 核心思想

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

2. 不变量（抽象层）

3. 工程价值

维度 表现
平衡强度 中
操作成本 低
工程可维护性 高

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

八、搜索树的演进总结

结构 平衡策略 工程定位
BST 无 理论基线
AVL 强 特殊场景
2-3 完全 理论模型
红黑树 近似 工程主流

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

1. 问题定义

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

2. 不变量

3. 特点

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

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

1. 问题定义

元素是否属于同一集合？

2. 不变量

3. 优化本质

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

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

1. 问题 → 结构映射

问题特征 结构选择
有序集合 红黑树
极值频繁 堆
连通性 并查集

2. 设计哲学总结

关联内容（自动生成）