树结构

树是计算机编程中最重要、最核心的一种数据结构。

在日常生活中，树状结构也是广泛存在的，例如家族的族谱、公司部门结构图等。在计算机编程中，树更是无处不在，你平时接触到的二叉查找树、堆、并查集、线段树、树状数组、前缀树、红黑树，这些都是属于树这种数据结构的一种。

• 数据库索引就是 B+ 树
• 编译器的语法树
• 操作系统的文件系统

基本概念

1. 节点：是树的基本单位，一棵树就是由一个一个节点组成的。
2. 根节点：整颗树的顶端节点，它上面没有父节点。
3. 父节点：一个节点的上一级节点。
4. 子节点：一个节点派生出来的节点，只计算下一层。例如 A 节点的子节点就是 B、C，C节点的子节点就是 E、F
5. 兄弟节点：具备相同父节点的节点互称为兄弟节点。
6. 叶子节点：没有子节点的节点，称之为叶子节点，位于树的末端。
7. 深度：就是有多少层。上图中深度为 4，因为一共有 4 层。
8. 度：一个节点的子节点的个数称之为度。A 节点的度就为 2，D 节点的度为 3，C 节点的度也为 2.

树的表示法

1. 图形表示法

2. 符号表示法：用小括号先将根节点放入到括号里面，然后将子节点从左往右放入括号，对子节点的子节点也采用相同的方式。同层的子节点使用逗号隔开。

   (A(B(D(G, H, I)), C(E(J), F)))

树的分类

二叉树

• 定义：每个节点最多有 2 个子节点（左、右子节点）。
• 变种：
  • 满二叉树：所有非叶子节点均有 2 个子节点，且所有叶子在同一层。
  • 完全二叉树：除最后一层外，其他层均满，且最后一层节点左对齐。
  • 二叉搜索树(Binary Search Tree)：左子树所有节点值 < 根节点值 < 右子树所有节点值。用于快速查找、插入、删除
  • 平衡二叉搜索树：通过旋转操作保持树高平衡，确保操作效率稳定在 O(logn)。常见类型：
    • AVL树：严格平衡（左右子树高度差 ≤ 1），适合读密集型场景。
    • 红黑树：弱平衡（通过颜色标记规则），插入删除效率更高，广泛应用于系统级代码。
    • Treap：结合 BST 和堆特性，随机优先级保证平衡。
    • 伸展树(Splay Tree)：通过“伸展”操作将最近访问节点移至根，适合局部性访问。

多叉树

多叉树也存在多种类型：

• B 树(B-Tree)：每个节点可包含多个键和子节点，所有叶子在同一层。常用于数据库索引、文件系统

• B+ 树：针对 B 树的一种优化，非叶子节点仅存键，数据全存储在叶子节点，叶子节点通过指针链接。

• 字典树(Trie)： 每个节点存储字符，路径构成字符串，叶子节点标记单词结束。前缀匹配高效，常用于自动补全、拼写检查、IP路由表。

特殊用途树

• 堆(Heap)：一种完全二叉树，满足堆性质（最大堆/最小堆）

• 线段树(Segment Tree)：每个节点代表一个区间，支持区间查询与更新。常用于动态范围统计，例如区间最值、区间和。

• 哈夫曼树(Huffman Tree)： 构造带权路径最短的二叉树，用于无损数据压缩。常用于 zip 压缩、jpeg 编码。

• 并查集(Union-Find)： 森林表示集合，支持合并与查找操作。常用于连通性问题，例如社交网络好友关系。

• KD树(K-Dimensional Tree)：二叉树，交替按不同维度划分空间。常用于多维数据近邻搜索，例如地理坐标查询的场景。

其他变种

• 二叉线索树(Threaded Binary Tree)： 利用空指针记录前驱/后继，加速遍历（中序、先序、后序）。

• 后缀树(Suffix Tree)：压缩字典树，存储字符串所有后缀。常用于模式匹配、生物信息学中 DNA序列分析等场景。

• 决策树(Decision Tree)：机器学习中的分类与回归模型，通过树结构划分特征空间。

-EOF-