计算机科学中的数据结构分类（以逻辑结构为主轴, 无法分类的单列，不能穷尽）

1 线性结构元素间一对一1.1 顺序存储数组类数据结构一句话描述数组 (Array)内存连续、大小固定的元素集合O(1) 随机访问。动态数组 (Dynamic Array)可自动扩容的数组如 Cvector、Pythonlist。Gap Buffer在光标处维护一段空隙专门优化文本编辑器中光标附近的插入与删除。块状数组 (Block List)将数组分成 √n 大小的块O(√n) 完成区间修改与查询实现简单。持久化数组 (Persistent Array)通过路径复制实现修改后保留旧版本的数组查询/修改 O(log n)。1.2 链式存储链表类数据结构一句话描述单向链表 (Singly Linked List)每个节点持有数据和指向下一节点的指针只能单向遍历。双向链表 (Doubly Linked List)每个节点同时持有前驱和后继指针支持双向遍历和 O(1) 删除已知节点。循环链表 (Circular Linked List)尾节点指回头节点形成环的链表可单向或双向。XOR 链表 (XOR Linked List)用前驱与后继地址的异或值代替两个指针节省空间的双向链表。展开链表 (Unrolled Linked List)每个节点存储一个小数组而非单个元素兼顾链表灵活性和数组缓存友好性。Cons List函数式编程中以头元素 尾列表递归定义的不可变单链表。1.3 受限线性表1.3.1 栈数据结构一句话描述栈 (Stack)后进先出LIFO的线性结构只能在栈顶进行插入和删除。最小栈 (Min Stack)额外维护当前最小值O(1) 查询栈内最小元素。单调栈 (Monotonic Stack)维护栈内元素单调递增或递减的栈常用于求下一个更大/更小元素。无锁栈 (Lock-Free Stack)使用 CAS 原子操作实现的无锁并发栈如 Treiber Stack。1.3.2 队列数据结构一句话描述队列 (Queue)先进先出FIFO的线性结构队尾入队、队首出队。双端队列 (Deque)两端都可进行插入和删除操作的队列。循环队列 / 环形缓冲区 (Circular Buffer)用固定大小数组首尾相接实现的队列避免数据搬移常用于生产者-消费者模型。优先队列 (Priority Queue)每次出队优先级最高的元素抽象数据类型通常用堆实现。单调队列 (Monotonic Queue)维护元素单调性的双端队列O(1) 获取滑动窗口最值。无锁队列 (Lock-Free Queue)使用 CAS 实现的无锁并发队列如 Michael-Scott Queue。1.4 串存储结构数据结构一句话描述Rope用二叉树管理字符串片段高效支持超长字符串的拼接、插入和删除。Piece Table用原始缓冲区 追加缓冲区 片段描述表管理文本适用于文本编辑器如 VS Code。1.5 索引线性表数据结构一句话描述跳表 (Skip List)通过多层随机索引加速查找的有序链表期望 O(log n) 各操作。无锁跳表 (Lock-Free Skip List)支持并发读写的跳表如 JavaConcurrentSkipListMap。稀疏表 (Sparse Table)O(n log n) 预处理后 O(1) 回答静态区间最值等幂等查询的二维数组结构。2 树形结构元素间一对多2.1 基础树与二叉树数据结构一句话描述二叉树 (Binary Tree)每个节点最多有两个子节点的树。满二叉树 / 完美二叉树 (Perfect Binary Tree)每一层节点都被完全填满的二叉树节点总数 2ʰ⁺¹−1。完全二叉树 (Complete Binary Tree)除最后一层外全部填满且最后一层从左到右连续排列的二叉树。真二叉树 / 正则二叉树 (Full Binary Tree)每个节点要么有 0 个子节点要么恰好有 2 个子节点的二叉树。线索二叉树 (Threaded Binary Tree)将空指针改为指向中序前驱/后继的线索无需栈或递归即可遍历。多叉树 / N 叉树 (N-ary Tree)每个节点可拥有任意多个子节点的通用树。森林 (Forest)若干棵互不相交的树的集合。2.2 搜索树2.2.1 二叉搜索树及其自平衡变体数据结构一句话描述二叉搜索树 (BST)满足左子 根 右子的二叉树支持有序操作。AVL 树任意节点左右子树高度差不超过 1 的严格平衡 BST。红黑树 (Red-Black Tree)通过红/黑着色与旋转维持近似平衡最长路径 ≤ 2×最短路径的 BST。左偏红黑树 (LLRB Tree)限制红色链接只能向左倾斜的红黑树简化变体。伸展树 (Splay Tree)每次访问都把目标节点旋转到根的自调整 BST摊还 O(log n)。Treap同时满足 BST 性质键和堆性质随机优先级的随机化平衡树。隐式 Treap (Implicit Treap)以子树大小隐含下标的 Treap用作可分裂/合并的序列容器。替罪羊树 (Scapegoat Tree)子树不平衡超过阈值时暴力重建该子树来恢复平衡无需旋转。AA 树只允许右孩子为红色的红黑树简化变体。权重平衡树 (Weight-Balanced Tree / BB[α] Tree)用左右子树节点数之比定义平衡条件的 BST。Size Balanced Tree (SBT)利用子树大小关系维持平衡的 BST。WAVL 树 (Weak AVL Tree)结合 AVL 和红黑树优点减少再平衡旋转次数的平衡树。顺序统计树 (Order Statistics Tree)增加子树大小字段的平衡 BSTO(log n) 查询第 k 小和排名。笛卡尔树 (Cartesian Tree)同时满足 BST 性质下标和堆性质值的二叉树与 RMQ 等价。持久化平衡树 (Persistent Balanced BST)每次修改只复制路径上的节点保留所有历史版本的平衡 BST。2.2.2 多路搜索树B 族及外存树数据结构一句话描述B 树 (B-Tree)每个节点存多个键、拥有多个子节点的自平衡多路搜索树适合磁盘 I/O。B 树 (B Tree)数据全在叶子且叶子用指针串联的 B 树变体广泛用于数据库和文件系统索引。B树 (BTree)**要求非根节点至少 2/3 满的 B 树变体空间利用率更高。2-3 树每个节点有 2 或 3 个子节点的特殊 B 树阶为 3。2-3-4 树每个节点有 2、3 或 4 个子节点的特殊 B 树与红黑树结构同构。LSM 树 (Log-Structured Merge Tree)写入先缓存在内存再批量合并到磁盘多层有序结构写入吞吐极高LevelDB、RocksDB。分形树 / Bε 树 (Fractal Tree / Bε-Tree)在 B 树内部节点附加写缓冲区将随机写转为顺序写。T 树 (T-Tree)为内存数据库设计的平衡树节点内存储一段有序数据以减少指针开销。2.3 字典树族含后缀结构与字符串索引数据结构一句话描述字典树 / 前缀树 (Trie)按字符逐层分支的树O(键长) 完成前缀查找与自动补全。压缩字典树 / 基数树 (Radix Tree / Patricia Trie)将只有单个子节点的路径压缩为一条边的 Trie大幅节省空间。三叉搜索树 (Ternary Search Tree, TST)每个节点有小于/等于/大于三个子指针的 Trie 变体空间效率更优。双数组字典树 (Double-Array Trie, DAT)用 base/check 两个数组紧凑表示 Trie兼顾速度与空间。HAT-Trie结合哈希桶和 Trie 的缓存友好字符串容器实际性能常超过哈希表。后缀树 (Suffix Tree)将一个字符串所有后缀构建成压缩 TrieO(模式长度) 子串匹配。广义后缀树 (Generalized Suffix Tree)同时容纳多个字符串所有后缀的后缀树用于多串公共子串等问题。后缀数组 (Suffix Array)所有后缀按字典序排序后的索引数组后缀树的空间高效替代底层为数组。回文树 / 回文自动机 (Palindrome Tree / Eertree)O(n) 在线构建存储字符串中所有本质不同回文子串的树形结构。FM-Index基于 BWT 的压缩全文索引O(模式长度) 查询空间接近信息熵下界底层为数组。Hash Array Mapped Trie (HAMT)用哈希值逐级索引的宽分支 Trie函数式语言中持久化 Map/Set 的核心实现。持久化字典树 (Persistent Trie)路径复制的 Trie每次修改生成新版本旧版本仍可查询。2.4 堆数据结构一句话描述二叉堆 (Binary Heap)用完全二叉树数组实现的堆O(log n) 插入和取最值。d 叉堆 (d-ary Heap)每个节点有 d 个子节点的堆增大 d 可减少堆高度优化 decrease-key。索引堆 (Indexed Heap)额外维护元素位置映射的堆支持按索引修改任意元素优先级。二项堆 (Binomial Heap)由一组二项树组成的可合并堆合并 O(log n)。斐波那契堆 (Fibonacci Heap)懒惰合并 标记剪切的可合并堆decrease-key 摊还 O(1)。左偏堆 (Leftist Heap)保持左子树零路径长 ≥ 右子树的可合并堆合并 O(log n)。斜堆 (Skew Heap)每次合并无条件交换左右子树的自调整可合并堆无需额外字段。配对堆 (Pairing Heap)结构极简的可合并堆insert/merge 均 O(1)实际性能优异。软堆 (Soft Heap)允许少量键被人为增大以换取 O(1) 摊还 insert用于最小生成树线性算法。空心堆 (Hollow Heap)用 DAG 结构避免级联剪切的堆decrease-key 最坏 O(1)。秩配对堆 (Rank-Pairing Heap)结合配对堆和斐波那契堆优点decrease-key 摊还 O(1)结构更简单。Brodal 队列 (Brodal Queue)所有操作最坏 O(1)除 delete-min 为 O(log n)的理论最优堆。最小-最大堆 (Min-Max Heap)奇偶层交替最小/最大的堆O(1) 同时获取最小值和最大值。胜者树 (Winner Tree)每个内部节点存子节点中较小者的完全二叉树常用于多路归并。败者树 (Loser Tree)每个内部节点存比赛败者的完全二叉树更新时只需沿单路径重赛。2.5 区间与统计查询树数据结构一句话描述线段树 (Segment Tree)区间递归二分建树配合懒标记 O(log n) 完成区间查询与修改。持久化线段树 / 主席树 (Persistent Segment Tree)每次修改只新建路径上的节点保留所有历史版本的线段树。李超线段树 (Li Chao Segment Tree)维护一组线段/直线O(log n) 查询某 x 处最值的线段树变体。Segment Tree Beats吉老师线段树引入区间取 min/max操作的线段树扩展通过势能分析保证复杂度。二维线段树 (2D Segment Tree)外层线段树每个节点挂一棵内层线段树支持二维区间查询。树状数组 / 二叉索引树 (Fenwick Tree / BIT)利用 lowbit 运算支持 O(log n) 前缀和查询与单点修改代码极简。二维树状数组 (2D Fenwick Tree)树状数组的二维推广支持二维前缀和查询与单点修改。区间树 (Interval Tree)存储区间集合高效查询与给定点或区间重叠的所有区间。范围树 (Range Tree)多层嵌套平衡树用于多维正交范围查询d 维查询 O(logᵈ n)。优先搜索树 (Priority Search Tree)结合堆和 BST 性质用于二维三面正交范围查询。小波树 (Wavelet Tree)在值的位表示上逐位分治建树支持区间第 k 小、区间频率等丰富查询。归并排序树 (Merge Sort Tree)线段树每个节点存对应区间排序数组支持区间排名等查询。2.6 空间划分树数据结构一句话描述K-D 树 (K-D Tree)交替按不同维度切分空间的二叉树用于多维最近邻和范围查询。K-D-B 树 (K-D-B Tree)K-D 树与 B 树的混合适合外存上的多维范围查询。四叉树 (Quadtree)将二维空间递归划分为四个象限的树常用于图像处理、碰撞检测和 GIS。八叉树 (Octree)将三维空间递归划分为八个卦限的树用于 3D 渲染和物理模拟。R 树 (R-Tree)用最小外接矩形组织空间对象的平衡树广泛用于空间数据库索引。R树 (R-Tree)**优化了插入和分裂策略的 R 树变体查询性能更优。Hilbert R 树 (Hilbert R-Tree)利用 Hilbert 空间填充曲线排序的 R 树变体提升节点聚集度。BSP 树 (Binary Space Partitioning Tree)用超平面递归将空间一分为二常用于 3D 游戏的可见性判断与碰撞检测。VP 树 (Vantage-Point Tree)基于到参考点距离划分数据的树适用于度量空间最近邻搜索。Ball Tree用超球体层层嵌套包裹数据点的树适合中高维最近邻查询。Cover Tree为一般度量空间设计的多尺度层次树复杂度与固有维度相关。BK 树 (BK-Tree)基于离散度量如编辑距离的多叉树常用于拼写纠错的模糊查找。M 树 (M-Tree)面向度量空间的平衡多路树支持范围和 k 近邻查询适合数据库外存。2.7 整数域搜索树数据结构一句话描述van Emde Boas 树 (vEB Tree)在值域 [0, U) 上支持插入、删除、前驱、后继均 O(log log U) 的整数集合。X-fast Trie用哈希加速层级查找O(1) 查找、O(log log U) 前驱/后继空间 O(n log U)。Y-fast Trie在 X-fast Trie 桶层使用平衡 BST空间降至 O(n)保持 O(log log U) 操作。融合树 (Fusion Tree)利用字长级位并行技巧实现 O(log n / log w) 查找w 为字长理论意义重大。2.8 动态树数据结构一句话描述Link-Cut Tree基于 Splay 树的动态森林结构O(log n) 路径查询、树的切割与连接。Euler Tour Tree (ETT)用欧拉遍历序列表示树将子树操作转化为序列操作支持动态连接与切断。Top Tree对树的路径和子树进行簇分解压缩的动态树结构可维护任意路径/子树信息。点分树 (Centroid Decomposition Tree)重心分解后得到的虚树任意两点 LCA 路径经过 O(log n) 层用于全局路径查询。2.9 其他特殊树数据结构一句话描述哈夫曼树 (Huffman Tree)基于字符频率构造的带权路径长度最短的二叉树用于最优前缀编码。默克尔树 (Merkle Tree)叶子存数据哈希、父节点存子哈希之哈希的树用于区块链和数据完整性校验。Finger Tree两端访问 O(1)、中间拼接 O(log n) 的函数式通用序列结构。3 图形结构元素间多对多数据结构一句话描述邻接矩阵 (Adjacency Matrix)用 n×n 矩阵表示图matrix[i][j] 表示 i→j 是否有边或边权适合稠密图。邻接表 (Adjacency List)每个顶点维护一个邻居列表空间 O(VE)适合稀疏图。边集数组 (Edge List)直接存储所有边 (u, v, w) 的列表结构最简单。关联矩阵 (Incidence Matrix)用顶点×边的矩阵表示图行为顶点、列为边。链式前向星 (Chained Forward Star)用数组模拟邻接表的紧凑存储方式无需动态内存分配竞赛中常用。十字链表 (Orthogonal Linked List)每条弧同时挂在起点出弧链和终点入弧链上适合有向图快速遍历入/出边。邻接多重表 (Adjacency Multilist)每条边只存一份同时挂在两端点链上适合无向图避免边的重复存储。4 集合结构元素间无序关注归属与映射4.1 散列结构哈希表族数据结构一句话描述哈希表 (Hash Table / Hash Map)通过哈希函数将键映射到桶平均 O(1) 查找、插入和删除。哈希集合 (Hash Set)基于哈希表实现的不允许重复元素的集合。链地址哈希表 (Chained Hash Table)用链表或红黑树解决冲突的哈希表。开放寻址哈希表 (Open Addressing Hash Table)冲突时按探测序列线性/二次/双重哈希在数组内寻找空槽。Robin Hood 哈希表插入时将探测距离短的元素位置让给探测距离长的元素使分布更均匀。Hopscotch 哈希表限制每个元素只能存在其哈希桶附近固定邻域内兼顾缓存和并发友好性。布谷鸟哈希表 (Cuckoo Hash Table)使用两个或多个哈希函数冲突时踢走原有元素保证最坏 O(1) 查找。可扩展哈希 (Extendible Hashing)用目录 可分裂桶实现动态扩容无需整表重建常用于数据库外存。线性哈希 (Linear Hashing)按线性顺序逐桶分裂的动态哈希方案不需要全局目录。一致性哈希 (Consistent Hashing)键和节点映射到哈希环上节点增减时仅影响相邻区间数据用于分布式系统。哈希链表 (Linked Hash Map/Set)哈希表 双向链表O(1) 查找的同时维护插入顺序。并发哈希表 (Concurrent Hash Map)通过分段锁或无锁技术支持多线程并发读写的哈希表。Ctrie (Concurrent Hash Trie)基于 CAS 的无锁并发哈希字典树支持一致快照。4.2 并查集数据结构一句话描述并查集 (Disjoint Set / Union-Find)管理不相交集合的合并与查询路径压缩 按秩合并后接近 O(α(n)) ≈ O(1)。带权并查集 (Weighted Union-Find)在并查集边上维护权值信息可追踪元素间的相对关系如距离、倍率。可持久化并查集 (Persistent Union-Find)结合可持久化数组实现的并查集可回溯到任意历史版本。4.3 位图、位集与紧凑集合数据结构一句话描述位数组 / 位图 (Bit Array / Bitmap)用每一位表示一个布尔值极致节省空间用于标记和集合运算。位集 (Bitset)位数组的封装支持集合的交AND、并OR、异或XOR等批量位运算。Roaring Bitmap自适应选择数组/位图/行程编码压缩每个分区的高效压缩位图。稀疏集合 (Sparse Set)用稠密稀疏两个数组交叉验证在有界整数域 O(1) 插入/删除/查找/清空。简洁数据结构 (Succinct Data Structure)用信息论下界空间存储数据同时支持 O(1) Rank/Select 等查询。5 跨维度结构无法被单一逻辑关系严格归类5.1 概率 / 近似结构底层多为数组/位图但语义上是概率判定或近似统计不属于传统线性/树/图/集合中的任何一种。数据结构一句话描述布隆过滤器 (Bloom Filter)用多个哈希函数和位数组判断元素可能存在或一定不存在有假阳性无假阴性。计数布隆过滤器 (Counting Bloom Filter)每一位扩展为计数器的布隆过滤器支持删除操作。布谷鸟过滤器 (Cuckoo Filter)基于布谷鸟哈希思想的过滤器支持删除且空间效率更优。商过滤器 (Quotient Filter)将哈希值分为商和余数存储的紧凑过滤器支持合并、调整大小和删除。Count-Min Sketch用多个哈希函数和计数矩阵估计数据流中元素频率只会高估不会低估。Count Sketch与 Count-Min Sketch 类似但使用 ±1 随机符号提供无偏频率估计。HyperLogLog用极少内存约 12 KB估计海量数据的基数不同元素个数标准误差约 0.81%。T-Digest用聚类思想近似存储数据分布高效计算分位数如 P99尾部精度更高。Space-Saving用固定数量计数器追踪数据流中的高频元素Top-K / Heavy Hitters。5.2 自动机底层是有向图但属于形式语言理论而非传统图论。数据结构一句话描述后缀自动机 (Suffix Automaton, SAM)接受一个字符串所有子串的最小状态 DFAO(n) 构建可做子串计数、最长公共子串等。AC 自动机 (Aho-Corasick Automaton)在 Trie 上添加失败指针构成的自动机实现多模式串同时匹配。5.3 组合结构由多种基础结构拼合而成整体不属于单一逻辑关系。数据结构一句话描述LRU 缓存 (LRU Cache)哈希表 双向链表O(1) 读写淘汰最近最久未使用的元素。LFU 缓存 (LFU Cache)哈希表 频率桶链表淘汰使用频率最低的元素。Dancing Links (DLX)基于双向十字链表的结构O(1) 行/列删除与恢复用于精确覆盖问题。倒排索引 (Inverted Index)从词项到包含该词的文档列表的映射搜索引擎的核心数据结构。Zipper用上下文 焦点表示数据结构中某位置的函数式导航方式可高效局部更新。5.4 内存管理结构更接近系统机制介于数据结构与操作系统之间。数据结构一句话描述内存池 (Memory Pool)预分配大块内存切割为固定大小块消除频繁 malloc/free 的碎片和系统调用开销。空闲链表 (Free List)将空闲内存块用链表串联管理的分配器分配/释放 O(1)。伙伴系统分配器 (Buddy Allocator)按 2 的幂次分割/合并内存快速找到合适大小块用于 Linux 内核。Slab 分配器 (Slab Allocator)为特定大小对象预缓存内存块避免反复初始化用于 Linux 内核对象分配。栈式分配器 (Stack Allocator)以栈方式线性分配内存只能按逆序释放速度极快。竞技场分配器 (Arena Allocator)从大块内存中顺序分配最后一次性整体释放适合生命周期一致的批量对象。5.5 多维数组与矩阵线性结构向高维的推广超出一对一的线性定义但也非树或图。数据结构一句话描述多维数组 (Multi-dimensional Array)连续内存存储的多维表格矩阵、张量按行优先或列优先布局。稀疏矩阵 - COO (Coordinate List)用 (行, 列, 值) 三元组列表只存储非零元素适合构建和转换阶段。稀疏矩阵 - CSR (Compressed Sparse Row)按行压缩非零元素用行指针列索引值三数组表示适合矩阵向量乘。稀疏矩阵 - CSC (Compressed Sparse Column)按列压缩非零元素与 CSR 对偶适合高效列遍历。对角存储 (DIA / Diagonal)仅存储有非零元素的对角线适合带状矩阵。杨氏矩阵 (Young Tableau)行和列均有序的矩阵结构O(√n) 查找与排列组合理论密切相关。