数据结构与算法(六)：各种数据结构(线性与非线性结构)

计算机科学中常见的数据结构类型，我们可以将其分为两大类：线性结构和非线性结构。

好的，我们来详细梳理一下计算机科学中常见的数据结构类型，特别是那些属于“树结构”的类型。

首先，我们可以将数据结构分为两大类：线性结构和非线性结构。

---

非树形结构

在了解树之前，先看看主要有哪些不是树的结构，以便对比。

线性结构

元素之间存在一对一的线性关系。

• 数组：内存中连续的存储空间，通过下标直接访问。
• 链表：由节点组成，每个节点包含数据和指向下一个节点的指针。
• 栈：后进先出（LIFO）的线性表，只能在表尾进行插入和删除。
• 队列：先进先出（FIFO）的线性表，在队尾插入，队头删除。
• 哈希表：通过哈希函数将键映射到数组中的一个位置，以实现快速查找。它本身不是线性存储，但其底层通常依赖数组。

非线性结构（非树形）

• 图：比树更一般的结构，节点（顶点）间是多对多的关系，可以有环，并且不要求连通。树是一种特殊的图（无环、连通的无向图）。

---

树形结构

树形结构是重要的非线性数据结构，它描述的是层级化的“一对多”关系。以下是各种常见的树形结构：

二叉树

• 定义：每个节点最多有两个子节点，称为左子节点和右子节点。

• 适用场景：作为更复杂树结构的基础，用于实现二叉搜索树、二叉堆等。本身也可用于表达式树、哈夫曼编码等。

• 举例：

  • 表达式树：用于编译器和计算器。运算符作为内部节点，操作数作为叶子节点。

    例如，表达式 (1 + 2) * 3 的树结构为：

    / \

  • 3
    /
    1 2

二叉搜索树

• 定义：一种特殊的二叉树，对于任意节点，其左子树所有节点的值都小于它，其右子树所有节点的值都大于它。
• 适用场景：用于实现动态集合的查找、插入、删除操作，平均时间复杂度为 O(log n)。是许多高级数据结构的基础。
• 举例：
  5
  /
  3 7
  / \
  1 4 9
  • 查找 4：从根节点5开始，4<5 -> 左转到3；4>3 -> 右转到4 -> 找到。

平衡二叉搜索树

• 定义：二叉搜索树在频繁插入和删除后可能会退化成链表（查找效率降为O(n)）。平衡BST通过旋转操作（如AVL树、红黑树）自动保持树的平衡，即左右子树高度差不超过一个常数。
• 适用场景：需要保证最坏情况下查找、插入、删除效率仍为 O(log n) 的场景。广泛应用于所有对性能有稳定要求的标准库中。
• 举例：
  • AVL树：通过严格的旋转保持高度平衡，查询密集型应用性能极佳。
  • 红黑树：通过一些约束（节点颜色、从根到叶子的路径上黑节点数相同）来近似平衡，插入删除效率比AVL树更高，是现代系统的主流选择（如Java的TreeMap， C++的std::map， Linux的进程调度）。

B树 & B+树

• 定义：一种多路平衡搜索树，每个节点可以有多个子节点（数量通常远大于2）。B树的所有节点都存储键和值。B+树是B树的变种，只有叶子节点存储数据值，内部节点只存键，且叶子节点之间通过指针链接成链表。
• 适用场景：数据库和文件系统的索引结构。因为数据量巨大，无法全部装入内存，需要与磁盘交互。B树/B+树通过增加节点的分支数（阶）来降低树的高度，从而减少磁盘I/O次数。
• 举例：
  • 数据库（如MySQL的InnoDB存储引擎）的索引就是基于B+树。B+树的叶子节点链表便于进行范围查询（如WHERE id BETWEEN 10 AND 100）。

堆

• 定义：一种特殊的完全二叉树。根据堆序性质分为：
  • 最大堆：父节点的值大于或等于所有子节点的值。
  • 最小堆：父节点的值小于或等于所有子节点的值。
• 适用场景：快速访问最大值或最小值、优先队列、堆排序。
• 举例：
  • 任务调度：操作系统使用优先队列（常用堆实现）来调度进程，优先级最高的任务先执行。
  • 堆排序：不断从最大堆中取出根节点（最大值），再调整堆结构，从而完成排序。

Trie树（字典树、前缀树）

• 定义：一种专门用于处理字符串的树。节点的每个子节点代表一个字符。从根到某个节点的路径代表一个字符串前缀。
• 适用场景：字符串的快速检索、前缀匹配、自动补全、拼写检查。
• 举例：
  • 搜索引擎的自动补全：当输入“app”时，Trie树可以快速找到所有以“app”开头的单词，如“apple”, “application”。
  • 通讯录检索：快速查找所有以“Li”开头的姓名。

线段树

• 定义：一种用于处理区间/段查询的二叉树。每个节点代表一个区间，叶子节点代表单位区间。节点存储的是该区间的某种聚合信息（如区间和、最大值、最小值）。
• 适用场景：需要对数组进行多次区间查询和区间更新。
• 举例：
  • 查询数组[1, 3, 5, 7, 9]中下标从i=1到j=3的元素之和。线段树可以在O(log n)时间内返回结果（3+5+7=15），而普通数组的区间求和需要O(n)时间。

树状数组（Fenwick Tree）

• 定义：同样是用于高效计算前缀和的数据结构。它利用二进制索引的特性，以树形结构存储部分和，代码实现比线段树更简洁。
• 适用场景：频繁计算数组前缀和、支持单点更新和前缀查询。
• 举例：计算一个不断变化的数组中前i个元素的和。

总结对比表

树结构类型	主要特点	核心应用场景
二叉树	每个节点最多有两个子节点	基础结构，用于构建更复杂的树
二叉搜索树	左子节点 < 父节点 < 右子节点	快速查找、插入、删除（平均O(log n)）
平衡BST（AVL/红黑树）	保持树平衡，防止退化成链表	需要稳定O(log n)性能的系统库（Map/Set）
B树 / B+树	多路平衡，节点存储大量键	数据库、文件系统索引
堆	父节点 >（或 <）所有子节点，是完全二叉树	优先队列、堆排序、任务调度
Trie树	每个节点代表一个字符，路径代表字符串	前缀匹配、自动补全、字典
线段树	每个节点代表一个区间，存储聚合信息	区间查询、区间更新
树状数组	利用二进制索引高效计算前缀和	前缀和查询、单点更新