数据结构概要
Foreword
记录数据结构特点、适用场合。
| 一级类别 | 二级类别 | 存储类型 | 查询复杂度 | 更新复杂度 |
|---|---|---|---|---|
| 链表 | 单链表 | 链表 | O(n) | O(n) |
| 链表 | 双链表 | 链表 | O(n) | O(n) |
| 链表 | 环形链表 | 链表 | O(n) | O(n) |
| 树 | 树链 | 数组 | - | - |
| 树 | 树状数组 | 数组 | O(log(n)) | O(log(n)) |
| 树 | Trie | 数组 | - | - |
| 树 | Double Array Trie | 数组 | - | - |
| 树 | Ternary Search Tree | 数组 | - | - |
| 树 | 线段树 | 数组 | - | - |
| 数组 | 后缀数组 | 数组 | - | - |
| 数组 | 前缀数组 | 数组 | - | - |
链表
单链表
略。
双链表
略。
树
树链
树状数组
定义
用数组来模拟树形结构。
特性
修改和查询的复杂度都是O(log(n))，比传统数组要快，而且容易写。 缺点是遇到复杂的区间问题实现较复杂，功能有限。
适用场景
解决基于区间更新以及求和问题。
Comments powered by Disqus.