Sphinx's Notes

Appearance

进阶数据结构 ​

1. Trie（前缀树/字典树） ​

核心思想 ​

将字符串的公共前缀存储在树的路径上，每个节点代表一个字符。

结构示意 ​

root
 ├── 'a'
 │    └── 'p'
 │         ├── 'p' (ends "app")
 │         └── 'l' → 'e' (ends "apple")
 └── 'c'
      └── 'a'
           └── 't' (ends "cat")

Python 实现 ​

python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find_node(prefix) is not None

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

复杂度 ​

操作时间复杂度空间复杂度
插入O(m)O(m)
查找O(m)O(1)
前缀匹配O(m)O(1)

其中 m 为字符串长度

典型应用 ​

  • 搜索建议/自动补全
  • IP 路由（前缀匹配）
  • 词典查找
  • 字符串分类

2. Skip Lists（跳表） ​

核心思想 ​

在有序链表上建立多层索引，实现类似二分查找的效果。

结构示意 ​

Level 2:  [HEAD] -----> [1] -----------------> [9] -------> NULL
Level 1:  [HEAD] -> [1] -> [3] -> [5] -> [7] -> [9] -> NULL
Level 0:  [HEAD] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> NULL

复杂度 ​

操作平均时间复杂度最坏时间复杂度
查找O(log n)O(n)
插入O(log n)O(n)
删除O(log n)O(n)

空间复杂度：O(n log n)

应用场景 ​

  • Redis Sorted Set 的底层实现
  • LevelDB、MemTable 的索引
  • 需要有序且支持高效查找的场景

3. 平衡搜索树 ​

3.1 AVL 树 ​

特点：

  • 任意节点的左右子树高度差 ≤ 1
  • 插入/删除后通过旋转保持平衡
  • 查询效率高，适合读多写少

旋转操作：

单旋（LL/RR）：
    x                    z
   / \      -->         / \
  z   T3               y   x
 / \                     / \
y   T2                   T1 T3
   /
  T1

双旋（LR/RL）：
    x                    y
   / \      -->         / \
  z   T3               z   x
 / \                   / \ / \
T1  y                 T1 T2 T3
   / \
  T2 T3

3.2 红黑树 ​

特点：

  • 每个节点非红即黑
  • 根节点是黑色
  • 叶子节点（NIL）是黑色
  • 红节点的子节点都是黑色
  • 从任一节点到其每个叶子节点的路径上都有相同数量的黑色节点

应用：

  • C++ STL 中的 map/set
  • Java 的 TreeMap/TreeSet
  • Linux 内核的调度器

3.3 B-Tree 与 B+Tree ​

B-Tree：

  • 多叉平衡搜索树
  • 所有节点都存储数据
  • 每个节点的子节点数有上下界

B+Tree：

  • 只有叶子节点存储数据
  • 叶子节点形成有序链表
  • 更适合范围查询

应用：

  • 数据库索引（MySQL InnoDB 使用 B+Tree）
  • 文件系统

对比 ​

特性AVL红黑树B-TreeB+Tree
查找效率O(log n)O(log n)O(log n)O(log n)
插入效率O(log n)O(log n)O(log n)O(log n)
删除效率O(log n)O(log n)O(log n)O(log n)
平衡度严格宽松严格严格
高度较低较高低最低
范围查询一般一般一般优秀
应用读多写少通用数据库索引数据库索引

4. 并查集 (Union-Find / Disjoint Set) ​

核心思想 ​

处理不相交集合的合并与查询问题。

基本操作 ​

  • find(x) - 找到 x 所属集合的代表
  • union(x, y) - 合并 x 和 y 所在的集合

优化：路径压缩 + 按秩合并 ​

python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return

        # 按秩合并
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

复杂度 ​

操作时间复杂度
findO(α(n)) ≈ O(1)
unionO(α(n)) ≈ O(1)

α(n) 是 Ackermann 函数的反函数，增长极慢

典型应用 ​

  • 岛屿数量问题
  • 图的连通分量
  • Kruskal 最小生成树算法
  • 并行计算中的任务调度

5. 线段树 ​

核心思想 ​

用于高效处理区间查询问题（如区间求和、区间最大值）。

结构 ​

数组: [1, 3, 5, 7, 9, 11]
树:
           [1, 11] = 36
         /            \
    [1, 5] = 16      [6, 11] = 20
    /      \          /       \
[1,3]=9  [4,5]=16  [6,8]=22  [9,11]=20
/    \    /    \     /    \    /     \
[1,2]=4 [3,3]=5 [4,4]=7 [5,5]=9 [6,7]=17 [8,8]=11 [9,10]=20 [11,11]=11
/ \
[1,1]=1 [2,2]=3

Python 实现 ​

python
class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 0, 0, self.n - 1)

    def _build(self, arr, node, l, r):
        if l == r:
            self.tree[node] = arr[l]
        else:
            mid = (l + r) // 2
            self._build(arr, 2*node+1, l, mid)
            self._build(arr, 2*node+2, mid+1, r)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

    def query(self, ql, qr):
        return self._query(0, 0, self.n-1, ql, qr)

    def _query(self, node, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        res = 0
        if ql <= mid:
            res += self._query(2*node+1, l, mid, ql, qr)
        if qr > mid:
            res += self._query(2*node+2, mid+1, r, ql, qr)
        return res

复杂度 ​

操作时间复杂度空间复杂度
建树O(n)O(n)
区间查询O(log n)-
单点更新O(log n)-

典型应用 ​

  • 区间求和/区间最大值
  • 区间修改（加法、赋值）
  • 动态数据的区间统计

6. 树状数组 (Binary Indexed Tree / Fenwick Tree) ​

核心思想 ​

利用二进制的性质，用 O(log n) 时间维护前缀和。

结构 ​

数组: [1, 3, 5, 7, 9, 11]
BIT:
index:  1   2   3   4   5   6
BIT:   1   4   5  16   9  20

Python 实现 ​

python
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # 移动到下一个管辖节点

    def prefix_sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)  # 移动到父节点
        return res

    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

对比 ​

特性线段树树状数组
功能区间查询/更新前缀和/单点更新
实现复杂简单
灵活性更通用受限
空间O(n)O(n)

相关资源 ​

基于 VitePress 构建

Copyright © 2024-present Sphinx