树、堆与图¶

学习目标¶

学完本章后，学习者应该能够：

理解树、堆、图的基本概念。
知道二叉搜索树、B+ 树、Trie、堆在工程中的应用。
掌握 BFS、DFS、拓扑排序的基本思想。
能把这些结构和数据库、缓存、调度、搜索等后端场景联系起来。

树¶

树是一种层级结构，由节点和边组成。一个节点可以有多个子节点。

常见术语：

根节点：没有父节点的节点。
叶子节点：没有子节点的节点。
深度：从根到当前节点的层数。
高度：从当前节点到最深叶子节点的距离。

树适合表达层级关系，例如组织架构、菜单、评论回复、文件目录。

二叉搜索树¶

二叉搜索树满足：

左子树所有节点小于当前节点。
右子树所有节点大于当前节点。

理想情况下，查询、插入、删除复杂度是 O(log n)。但如果数据接近有序，普通二叉搜索树可能退化成链表，复杂度变成 O(n)。

因此工程中更常见的是平衡树、红黑树、B 树、B+ 树等结构。

B 树与 B+ 树¶

B 树和 B+ 树常用于数据库和文件系统索引。

B+ 树适合数据库索引的原因：

多叉结构降低树高，减少磁盘 IO。
叶子节点有序，适合范围查询。
非叶子节点主要存索引，能容纳更多 key。

当你给数据库字段加索引时，背后通常不是“魔法”，而是通过合适的数据结构减少扫描范围。

Trie¶

Trie 又叫前缀树，适合处理字符串前缀问题。

应用场景：

自动补全。
敏感词匹配。
路由匹配。
字典查询。
IP 前缀匹配。

Trie 的查询复杂度通常和字符串长度有关，而不是和词库大小直接相关。

堆¶

堆是一种特殊的树结构，常见的是二叉堆。

最大堆：父节点大于等于子节点。
最小堆：父节点小于等于子节点。

堆适合：

Top K。
优先级队列。
定时任务调度。
合并多个有序流。

Go 标准库提供 container/heap。

// container/heap 需要实现 sort.Interface 以及 Push、Pop。

堆的插入和删除堆顶通常是 O(log n)，获取堆顶是 O(1)。

图¶

图由节点和边组成，可以表示任意关系。

常见场景：

服务依赖关系。
用户关系。
任务依赖。
路由网络。
权限继承。

图可以是有向图、无向图、带权图或无权图。

BFS 与 DFS¶

BFS：广度优先搜索，通常使用队列。适合找最短层级路径、层序遍历。

DFS：深度优先搜索，通常使用递归或栈。适合遍历所有路径、检测连通性、处理树形结构。

示例：用 BFS 遍历邻接表：

func BFS(graph map[string][]string, start string) []string {
    visited := map[string]bool{start: true}
    queue := []string{start}
    order := make([]string, 0)

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        for _, next := range graph[node] {
            if !visited[next] {
                visited[next] = true
                queue = append(queue, next)
            }
        }
    }
    return order
}

拓扑排序¶

拓扑排序用于有向无环图，解决依赖顺序问题。

应用场景：

任务编排。
构建系统。
数据迁移顺序。
服务启动依赖。
工作流节点执行顺序。

如果图中存在环，就无法得到合法拓扑序。这在工程中常用于检测循环依赖。

Go 后端实际应用例子¶

例子一：评论树组装¶

数据库里常用扁平结构保存评论：

type Comment struct {
    ID       int64
    ParentID int64
    Content  string
    Children []*Comment
}

接口返回时需要组装成树：

func BuildCommentTree(comments []*Comment) []*Comment {
    byID := make(map[int64]*Comment, len(comments))
    roots := make([]*Comment, 0)

    for _, comment := range comments {
        byID[comment.ID] = comment
    }

    for _, comment := range comments {
        if comment.ParentID == 0 {
            roots = append(roots, comment)
            continue
        }
        if parent, ok := byID[comment.ParentID]; ok {
            parent.Children = append(parent.Children, comment)
        }
    }
    return roots
}

这是树结构在评论、菜单、组织架构中的典型应用。

例子二：用堆做延迟任务调度¶

延迟任务可以用最小堆按执行时间排序。堆顶永远是最早需要执行的任务：

type DelayedJob struct {
    ID    string
    RunAt int64
}

生产系统会考虑持久化、并发安全、失败重试和多节点抢占，但核心思想仍然是“按最早执行时间取任务”。

例子三：用拓扑排序安排数据迁移¶

如果迁移 B 依赖迁移 A，迁移 C 又依赖 B，就可以用有向图表示依赖，再用拓扑排序得到执行顺序。这样能避免手工维护顺序导致的遗漏和循环依赖。

常见误区¶

误区一：树和图只在算法题中出现。

数据库索引、权限树、菜单树、服务依赖、任务编排都在使用这些思想。

误区二：递归 DFS 永远安全。

数据很深时递归可能导致栈压力，工程中要考虑迭代写法或深度限制。

误区三：堆等于排序。

堆更常用于动态维护最大/最小值或 Top K，不一定需要完整排序。

实战任务¶

实现一个任务依赖检查器：

输入：

deps := map[string][]string{
    "deploy": {"test"},
    "test":   {"build"},
    "build":  {"lint"},
}

要求：

判断是否存在循环依赖。
如果没有循环，输出一种可执行顺序。
使用拓扑排序实现。

参考实现

这里假设 deps[task] 表示 task 依赖哪些前置任务。拓扑排序时先建立“前置任务 -> 后续任务”的图，并统计每个任务的入度。

func TopoSort(deps map[string][]string) ([]string, bool) {
    graph := make(map[string][]string)
    indegree := make(map[string]int)

    for task, pres := range deps {
        if _, ok := indegree[task]; !ok {
            indegree[task] = 0
        }
        for _, pre := range pres {
            graph[pre] = append(graph[pre], task)
            indegree[task]++
            if _, ok := indegree[pre]; !ok {
                indegree[pre] = 0
            }
        }
    }

    queue := make([]string, 0)
    for task, degree := range indegree {
        if degree == 0 {
            queue = append(queue, task)
        }
    }

    order := make([]string, 0, len(indegree))
    for len(queue) > 0 {
        task := queue[0]
        queue = queue[1:]
        order = append(order, task)

        for _, next := range graph[task] {
            indegree[next]--
            if indegree[next] == 0 {
                queue = append(queue, next)
            }
        }
    }

    return order, len(order) == len(indegree)
}

返回的第二个值表示是否不存在循环依赖。如果为 false，说明图里有环，无法得到合法执行顺序。

面试题¶

1. 为什么数据库索引常用 B+ 树？¶

参考答案

B+ 树是多叉平衡树，树高较低，可以减少磁盘 IO。它的叶子节点有序并通过链表连接，非常适合范围查询。非叶子节点主要存索引 key，可以让一个节点容纳更多索引项。

数据库索引的核心目标是减少扫描范围和磁盘访问次数，B+ 树正好适合这个场景。

2. 堆适合解决什么问题？¶

参考答案

堆适合动态维护最大值或最小值，例如 Top K、优先级队列、定时任务调度、合并多个有序流。获取堆顶是 O(1)，插入和删除堆顶通常是 O(log n)。

如果只需要前 K 个元素，不一定要对全部数据排序，使用堆通常更高效。

3. BFS 和 DFS 有什么区别？¶

参考答案

BFS 按层遍历，通常使用队列，适合找最短层级路径、层序遍历。DFS 沿着一条路径深入，通常使用递归或栈，适合遍历所有路径、检测连通性和处理树形结构。

两者时间复杂度通常都是 O(V+E)，区别主要在遍历顺序、空间使用和适用问题。

4. 什么是拓扑排序？有什么工程应用？¶

参考答案

拓扑排序是在有向无环图中，给节点排出一个满足依赖关系的顺序。如果 A 依赖 B，那么 B 应该排在 A 前面。

工程应用包括任务编排、构建系统、数据库迁移、服务启动顺序和工作流执行。它也可以用来检测循环依赖。

5. Trie 适合什么场景？¶

参考答案

Trie 适合前缀匹配类问题，例如搜索自动补全、敏感词匹配、路由匹配、字典查询和 IP 前缀匹配。

它的查询复杂度通常和字符串长度有关，而不是直接和词库大小成正比。但它可能占用较多内存，需要根据数据规模和字符集设计节点结构。