在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

kdn251/面试

菜单

树和图

相关源文件

本页详细介绍了树和图数据结构、它们的各种实现以及时间复杂度。这些数据结构是计算机科学的基础，并在技术面试中占有重要地位。有关使用这些结构实现的算法，请参阅算法参考和图算法。

树数据结构

树是一种无向、连通、无环的图。在计算机科学中，树是一种分层数据结构，由通过边连接的节点组成，具有单个根节点且无循环。

树的术语

  • 根（Root）：树的最顶层节点
  • 父/子（Parent/Child）：当远离根节点移动时，直接连接到另一个节点的节点
  • 叶节点 (Leaf)：没有子节点的节点
  • 高度（Height）：从根到叶子的最长路径的长度
  • 深度（Depth）：从根到特定节点的路径长度

来源: README.md95-104

二叉树

二叉树是一种树数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的类型

  • 满二叉树（Full Binary Tree）：每个节点都有0个或2个子节点的树
  • 完全二叉树（Perfect Binary Tree）：所有内部节点都有两个子节点且所有叶子节点都在同一深度的二叉树
  • 完全二叉树（Complete Binary Tree）：除了最后一层外，所有层都是满的，并且最后一层的所有节点都尽可能靠左排列的二叉树

来源: README.md98-104

二叉搜索树 (BST)

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它保持以下特性：

  • 每个节点的值必须大于或等于其左子树中存储的任何值
  • 每个节点的值必须小于或等于其右子树中存储的任何值

这种排序特性使得搜索、插入和删除操作效率很高。

BST 时间复杂度

  • 访问: 平衡树中为O(log(n))，最坏情况下为O(n)
  • 搜索: 平衡树中为O(log(n))，最坏情况下为O(n)
  • 插入: 平衡树中为O(log(n))，最坏情况下为O(n)
  • 删除: 平衡树中为O(log(n))，最坏情况下为O(n)

该仓库包含了各种 BST 实现和操作，例如：

来源: README.md106-115

字典树 (前缀树)

Trie，有时称为基数树或前缀树，是一种用于存储动态集或关联数组的搜索树，其中键通常是字符串。节点在树中的位置定义了它所关联的键。一个节点的所有后代都与该节点关联着一个共同的前缀，而根节点则与空字符串关联。

Trie 在以下方面特别有用：

  • 自动补全功能
  • 拼写检查
  • IP路由（最长前缀匹配）
  • 字符串搜索

该仓库在 Trie/implementTrie.java 中实现了 Trie，并将其用于解决诸如单词搜索设计 Trie/addAndSearchWordDataStructureDesign.java 和单词方块 Trie/wordSquares.java 等问题。

来源: README.md118-124

特殊树结构

Fenwick 树 (Binary Indexed Tree)

Fenwick 树是一种数据结构，可以高效地更新数组中的元素和计算前缀和。虽然被称为树，但它通常使用数组实现。节点父或子的索引是通过对其索引的二进制表示进行位运算来计算的。

时间复杂度

  • 区间和: O(log(n))
  • 更新: O(log(n))

来源: README.md126-136

线段树

线段树是一种用于存储区间或线段的树数据结构。它允许查询哪些线段包含给定点。它对范围查询问题特别有用。

时间复杂度

  • 范围查询: O(log(n))
  • 更新: O(log(n))

来源: README.md138-145

树的遍历和操作

树的遍历是访问树中每个节点的基本操作。主要的遍历方法有：

  1. 深度优先遍历:

    • 中序遍历 (左、根、右)
    • 前序遍历 (根、左、右)
    • 后序遍历 (左、右、根)

  2. 广度优先遍历:

    • 层序遍历

该仓库包含了各种树的遍历和操作的实现：

来源: README.md417-422 README.md424-431

图数据结构

图是一个有序对 G = (V, E)，由一组顶点或节点 V 和一组边或弧 E 组成，其中边是 V 的2元素子集。换句话说，图是由边连接的节点集合。

图的类型

  1. 无向图（Undirected Graph）：边没有方向的图。如果存在从节点 u 到节点 v 的边 (u → v)，那么也存在从节点 v 到节点 u 的边 (v → u)。

  2. 有向图（Directed Graph / Digraph）：边有方向的图。如果存在从节点 u 到节点 v 的边 (u → v)，这并不意味着存在从节点 v 到节点 u 的边 (v → u)。

  3. 加权图（Weighted Graph）：每条边都有相关联的权重（成本）的图。

  4. 连通图（Connected Graph）：任意一对顶点之间都有路径的图。

  5. 循环图（Cyclic Graph）：包含至少一个循环（起点和终点相同的路径）的图。

来源: README.md175-186

图的表示方法

表示图的两种常用方式

1. 邻接矩阵

一个 V×V 的二维数组，其中 V 是顶点数量。如果从顶点 i 到顶点 j 存在边，则 adjacency[i][j] = 1，否则 adjacency[i][j] = 0。

优点:

  • 对于稠密图的简单实现
  • 边查找为 O(1)
  • 删除边为 O(1)

缺点:

  • 占用更多空间 O(V²)
  • 添加顶点成本高

2. 邻接表

一个列表数组，其中每个列表描述图中一个顶点的邻居集合。

优点:

  • 对于稀疏图节省空间 O(V+E)
  • 添加顶点更容易

缺点:

  • 边查找为 O(V)
  • 实现稍复杂

来源: README.md175-186

图算法

深度优先搜索 (DFS)

DFS 是一种图遍历算法，它在回溯之前尽可能深地探索每个分支。它使用栈（通常通过递归实现）来跟踪要探索的节点。

时间复杂度: O(|V| + |E|)，其中 |V| 是顶点数，|E| 是边数。

应用程序:

  • 查找连通分量
  • 拓扑排序
  • 解决迷宫等谜题
  • 检测环

该仓库包含了用于解决以下问题的 DFS 实现：

来源: README.md230-236 README.md424-431

广度优先搜索 (BFS)

BFS 是一种图遍历算法，它在进入下一深度层级的节点之前，探索当前深度层级的所有邻近节点。它使用队列来跟踪要探索的节点。

时间复杂度: O(|V| + |E|)

应用程序:

  • 在无权图中查找最短路径
  • 查找一个连通分量中的所有节点
  • 测试二分性

该仓库包含了用于解决以下问题的 BFS 实现：

  • 二叉树的层序遍历 ()
  • 克隆图 ()
  • 解决墙和门问题 ()

来源: README.md238-242 README.md417-423

拓扑排序

拓扑排序是一种用于对有向无环图（DAG）的顶点进行排序的算法，使得对于每条有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 之前。

时间复杂度: O(|V| + |E|)

应用程序:

  • 根据依赖关系调度任务
  • 确定软件项目中的构建顺序
  • 课程先修规划

来源: README.md244-249

最短路径算法

这些算法用于查找图中节点之间的最短路径。

Dijkstra 算法

在具有非负权重的加权图中，查找从单个源点到所有其他顶点的最短路径。

时间复杂度: 邻接矩阵为 O(|V|²)，带最小堆为 O(|E| + |V|log|V|)

来源: README.md250-254

Bellman-Ford 算法

计算加权图中从单个源点出发的最短路径。与 Dijkstra 算法不同，它可以处理带有负权重边的图。

时间复杂度:

  • 最佳情况：O(|E|)
  • 最坏情况：O(|V||E|)

来源: README.md256-265

Floyd-Warshall 算法

在加权图中查找所有顶点对之间的最短路径，该图可以有正边或负边权重（但不能有负循环）。

时间复杂度: O(|V|³)

来源: README.md266-274

最小生成树算法

这些算法找到边的子集，这些边形成一棵包含每个顶点的树，并且树中所有边的总权重最小。

普里姆算法

一种贪婪算法，用于查找加权无向图的最小生成树。

时间复杂度: 邻接矩阵为 O(|V|²)，带二叉堆为 O(|E|log|V|)

来源: README.md275-280

克鲁斯卡尔算法

另一种用于查找图的最小生成树的贪婪算法。与 Prim 算法不同，它不需要图最初是连通的。

时间复杂度：O(|E|log|V|)

来源: README.md282-286

面试中常见的树和图问题

树问题

  1. 树的遍历：实现不同的遍历方法
  2. BST 操作：插入、删除、搜索
  3. 平衡树：将不平衡的树转换为平衡树
  4. 路径查找：查找具有特定属性的路径（例如，最大和）
  5. 树验证：检查树是否为有效的 BST

图问题

  1. 图遍历：实现 DFS 和 BFS
  2. 连通性：查找连通分量或检查两个节点是否连通
  3. 最短路径：使用 Dijkstra 或其他算法查找最短路径
  4. 循环检测：确定图是否包含循环
  5. 拓扑排序：对有向无环图的顶点进行排序

示例：数独有效性作为图问题

数独有效性问题可以看作是一个图着色问题，其中每个单元格都是一个顶点，约束是边。该仓库中包含的实现包括：

该解决方案使用 HashSets 来检查数字是否已存在于行、列或 3x3 方块中，从而有效地验证了数独谜题的约束。

来源: company/apple/ValidSudoku.java9-29 company/snapchat/ValidSudoku.java9-29 company/uber/ValidSudoku.java9-29 leetcode/hash-table/ValidSudoku.java9-29

树和图的实现关系

下图展示了仓库中不同树和图概念的实现方式

来源: README.md499-506 README.md507-510 README.md416-423 README.md424-431

时间复杂度汇总表

数据结构 / 算法访问搜索插入删除附加操作
二叉搜索树O(log n)*O(log n)*O(log n)*O(log n)** 假定为平衡树
Trie树O(m)**O(m)**O(m)**O(m)**** m 为键长
Fenwick 树--O(log n)-范围求和: O(log n)
线段树--O(log n)-范围查询: O(log n)
DFS / BFS-O(V+E)---
Dijkstra 算法----最短路径: O(V²)
Bellman-Ford----最短路径: O(VE)
Floyd-Warshall----所有对最短路径: O(V³)
普里姆算法----MST: O(V²)
克鲁斯卡尔算法----MST: O(E log V)

来源: README.md106-145 README.md230-286

结论

树和图是计算机科学中具有广泛应用的基础数据结构。理解它们的属性、操作和算法对于技术面试和软件开发至关重要。该仓库提供了各种树和图问题的实现，以实践这些概念。