什么是鲜为人知但有用的数据结构？

尝试，也称为前缀树或爆裂树，已经存在了40多年，但仍然相对不为人知。“TRASH-动态LC-trie和哈希数据结构”中描述了尝试的一个非常酷的用法，它将trie与哈希函数结合起来。

张开的树怎么样？

此外，Chris Okasaki的纯函数式数据结构浮现在脑海中。

以下是一些：

• 后缀尝试。对几乎所有类型的字符串搜索都很有用（http://en.wikipedia.org/wiki/Suffix_trie#Functionality）。另见后缀数组；它们不像后缀树那么快，但要小得多。

• Splay树（如上所述）。它们很酷的原因有三个：

  • 它们很小：你只需要左和右指针，就像在任何二叉树中一样（不需要存储节点颜色或大小信息）
  • 它们（相对）非常容易实现
  • 它们为一大堆“测量标准”提供了最佳的摊销复杂性（log n lookup time是每个人都知道的）。

• 堆排序搜索树：你在一棵树中存储一堆（key，prio）对，这样它就是一个关于键的搜索树，并且关于优先级的堆排序。人们可以证明这样的树具有独特的形状（并且它并不总是完全向左包装）。对于随机优先级，它会给你预期的O（log n）搜索时间，IIRC。

• 一个小众的是具有O（1）邻居查询的无向平面图的邻接列表。这与其说是一种数据结构，不如说是组织存量数据结构的一种特殊方式。下面是你如何做到的：每个平面图都有一个度数最多为6的节点。选择这样一个节点，将其邻居放入邻居列表中，将其从图中删除，并递归直到图为空。当给定一对（u，v）时，在v的邻居列表中寻找u，在u的邻居列表中寻找v。两者的大小最多为6，所以这是O（1）。

通过上述算法，如果u和v是邻居，你不会同时拥有v列表中的u和u列表中的v。如果你需要这样做，只需将每个节点的缺失邻居添加到该节点的邻居列表中，但存储你需要查看多少邻居列表以快速查找。

空间指数，特别是R-树和KD树，有效地存储空间数据。它们适用于地理地图坐标数据和VLSI位置和路线算法，有时也适用于最近邻搜索。

位数组紧凑地存储单个位并允许快速位操作。

Van Emde-Boas树。我甚至有一个C++实施，最多2^20个整数。

Van Emde-Boas树

我认为知道为什么他们很酷会很有用。一般来说，“为什么”是最重要的问题；）

我的答案是，他们给你O（log log n）字典，其中包含{1… n}个键，与使用了多少个键无关。就像重复减半给你O（log n）一样，重复sqrting给你O（log log n），这就是vEB树中发生的事情。

• 实时光线追踪中使用的空间数据结构Kd-Trees有一个缺点，即交叉不同空间的三角形需要被裁剪。通常BVH更快，因为它们更轻量级。
• MX-CIF四叉树，通过在四边形的边缘组合常规四叉树和二叉树来存储边界框而不是任意点集。
• HAMT，分层哈希映射，由于所涉及的常量，访问时间通常超过O（1）哈希映射。
• 反向索引，在搜索引擎界非常有名，因为它用于快速检索与不同搜索词相关的文档。

其中大多数（如果不是全部）都记录在NIST算法和数据结构词典上

配对堆是一种堆数据结构，具有相对简单的实现和出色的实际摊销性能。

布隆过滤器：m位的位数组，最初都设置为0。

要添加一个项目，您可以通过k哈希函数运行它，该函数将在数组中为您提供k索引，然后将其设置为1。

要检查项目是否在集合中，请计算k索引并检查它们是否都设置为1。

当然，这给出了一些误报的概率（根据维基百科，大约是0.61^（m/n），其中n是插入项目的数量）。

删除一个项目是不可能的，但您可以实现计数布隆过滤器，由整数数组和增量/减量表示。

Splay树很酷。它们以一种将最常查询的元素移近根的方式重新排序。

我喜欢treaps，因为它简单而有效地将堆结构与随机优先级叠加在二叉查找树上以平衡它。

• 二进制决策图（我最喜欢的数据结构，用于表示布尔方程并求解它们。对很多事情都有效）
• 堆（节点的父节点总是与节点的子节点保持某种关系的树，例如，节点的父节点总是大于它的每个子节点（max-heap））
• 优先级队列（实际上只是最小堆和最大堆，用于维护那里的许多元素的顺序，例如具有最高值的项目应该首先被删除）
• 哈希表，（具有各种查找策略和存储桶溢出处理）
• 平衡的二叉搜索树（每种树都有自己的优势）
  • RB树（整体良好，以有序方式插入、查找、删除和迭代时）
  • Avl树（查找速度比RB快，但在其他方面与RB非常相似）
  • Splay-Tree（当最近使用的节点可能被重用时，查找速度更快）
  • Fusion树（利用快速乘法获得更好的查找时间）
  • B+树（用于数据库和文件系统中的索引，当读取/写入索引的延迟很大时非常有效）。
• 空间索引（非常适合查询点/圆/矩形/线/立方体是否彼此靠近或包含在彼此中）
  • bsp树
  • Quadtree
  • 八叉树
  • 范围树
  • 许多相似但略有不同的树，以及不同的维度
• 区间树（很好地找到重叠区间，线性）
• 图形
  • 邻接列表（基本上是边列表）
  • 相邻矩阵（表示图的有向边的表，每条边只有一位。对于图遍历非常快）

这些是我能想到的。维基百科上还有更多关于数据结构的内容

跳过列表非常漂亮。

维基百科
跳过列表是一种概率数据结构，基于多个并行的排序链表，效率与二叉查找树相当（大多数操作的顺序日志n平均时间）。

它们可以用作平衡树的替代方案（使用概率平衡而不是严格执行平衡）。它们易于实现，比红黑树更快。我认为它们应该出现在每个优秀的程序员工具箱中。

如果你想深入了解跳过列表，这里有一个麻省理工学院关于它们的算法导论讲座。

此外，这里是一个Java的小程序，直观地展示了跳过列表。

绳子：这是一个允许廉价前置、子字符串、中间插入和追加的字符串。我真的只使用过一次，但没有其他结构可以满足。常规字符串和数组前置对于我们需要做的事情来说太贵了，反转任何东西都是不可能的。

当您需要将一堆项目划分为不同的集合并查询成员资格时，我认为不相交集非常漂亮。联合和查找操作的良好实现导致摊销成本实际上是恒定的（与Ackermnan的函数相反，如果我没记错我的数据结构类）。

任何有3D渲染经验的人都应该熟悉BSP树。一般来说，它是通过构建一个3D场景来管理渲染的方法，知道相机坐标和方位。

二进制空间分区（BSP）是一个递归细分a的方法空间由超平面转化为凸集。这个细分产生了一个通过手段表示场景的树数据结构，称为BSP树。

换句话说，它是一种方法错综复杂地分裂多边形成凸集，或更小多边形完全由非反射角（角度小于180°）。对于更一般的描述空间划分，见空间分区。

最初，这种方法被提出在3D计算机图形中增加渲染效率。其他一些应用程序包括执行形状几何运算（构造立体几何）在CAD中，机器人和3D中的冲突检测电脑游戏和其他电脑涉及处理复杂的空间场景。

增强的哈希算法非常有趣。线性散列很简洁，因为它允许一次在哈希表中拆分一个“桶”，而不是重新哈希整个表。这对分布式缓存特别有用。然而，对于大多数简单的拆分策略，你最终会快速连续拆分所有桶，并且表的负载因子波动非常严重。

我认为螺旋散列也很整洁。就像线性哈希一样，一次拆分一个桶，桶中不到一半的记录被放入同一个新桶中。它非常干净和快速。然而，如果每个“桶”都由具有类似规格的机器托管，它可能会效率低下。为了充分利用硬件，你需要功能较小和功能较强的机器的混合。

二元决策图是我最喜欢的数据结构之一，或者实际上是简化有序二进制决策图（ROBDD）。

例如，这些类型的结构可用于：

• 表示项目集并对这些集合执行非常快速的逻辑操作。
• 任何布尔表达式，旨在找到表达式的所有解决方案

请注意，许多问题可以表示为布尔表达式。例如，suduku的解决方案可以表示为布尔表达式。为该布尔表达式构建BDD将立即产生解决方案。

霍夫曼树-用于压缩。

圆形或环形缓冲器-用于流式传输等。

计数未排序的平衡b树。

完美的文本编辑器缓冲区。

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html

我喜欢后缀树和数组用于字符串处理，跳过列表用于平衡列表，张开的树用于自动平衡树

看看Donald Knuth提出的横向堆。

http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx

哈希表的一个有趣变体称为布谷鸟哈希。它使用多个哈希函数而不仅仅是1来处理哈希冲突。冲突通过将旧对象从主哈希指定的位置移除并将其移动到备用哈希函数指定的位置来解决。Cuckoo哈希允许更有效地使用内存空间，因为您可以仅使用3个哈希函数将负载因子提高到91%并且仍然具有良好的访问时间。

跳过列表实际上非常棒：http://en.wikipedia.org/wiki/Skip_list

远离所有这些图结构，我只是喜欢简单的环形缓冲器。

如果实施得当，您可以大大减少内存占用，同时保持性能，有时甚至提高性能。

快速紧凑尝试：

• Judy数组：非常快速和内存高效的有序稀疏动态数组，用于位、整数和字符串。Judy数组比任何二叉搜索树更快，内存效率更高。

• HAT-trie：一个基于Trie的字符串数据结构

• 基于磁盘的字符串管理的B尝试

二项式堆有很多有趣的属性，其中最有用的是合并。

斐波那契堆

它们被用于一些已知最快的算法（渐近地）中，用于许多与图相关的问题，例如最短路径问题。Dijkstra的算法在标准二进制堆的O（E log V）时间内运行；使用斐波那契堆将其改进为O（E+V log V），这对于稠密图来说是一个巨大的加速。然而，不幸的是，它们有很高的常数因子，通常使它们在实践中不切实际。

我认为标准数据结构的无锁替代方案，即无锁队列、堆栈和列表被忽视了。
随着并发成为更高的优先级，它们变得越来越相关，并且比使用互斥体或锁来处理并发读/写更令人钦佩。

这里有一些链接
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf[链接到PDF]
http://www.boyet.com/Articles/LockfreeStack.html

迈克·阿克顿的（通常是挑衅性的）博客有一些关于无锁设计和方法的优秀文章

您可以使用min-heap在常数时间内查找最小元素，或者使用max-heap查找最大元素。但是，如果您想同时执行这两个操作怎么办？您可以使用Min-Max在常数时间内执行这两个操作。它通过使用min max排序来工作：在连续树级别之间交替进行min和max堆比较。

我很惊讶没有人提到默克尔树（即哈希树）。

在许多情况下（P2P程序、数字签名）中使用，当您只有部分文件可用时，您希望验证整个文件的哈希值。

一个鲜为人知但非常漂亮的数据结构是芬威树（有时也称为二叉索引树或BIT）。它存储累积和并支持O（log（n））操作。虽然累积和听起来不太令人兴奋，但它可以适应解决许多需要排序/log（n）数据结构的问题。

IMO，它的主要卖点是易于实施。在解决算法问题时非常有用，否则将涉及编码红黑/avl树。

看看手指树，特别是如果你是前面提到纯函数式数据结构的粉丝。它们是持久序列的函数表示，支持在摊销的常数时间内访问末端，以及在时间上对较小块的大小进行对数连接和拆分。

根据原始文章：

我们的功能2-3指树是Okasaki（1998）引入的通用设计技术的一个实例，称为隐式递归减速。我们已经注意到这些树是他隐式双端结构的扩展，用2-3个节点替换对，以提供高效连接和拆分所需的灵活性。

手指树可以使用单峰进行参数化，使用不同的单元格将导致树的不同行为。这让手指树可以模拟其他数据结构。

适当的字符串数据结构。几乎每个程序员都满足于语言对结构的任何本机支持，这通常效率低下（特别是对于构建字符串，您需要一个单独的类或其他东西）。

最糟糕的是将字符串视为C中的字符数组并依赖NULL字节来确保安全。

拉链-修改结构以具有“游标”的自然概念的数据结构的派生-当前位置。这些非常有用，因为它们保证指示不能超出约束-使用，例如在xmonad窗口管理器中跟踪哪个窗口已聚焦。

令人惊讶的是，您可以通过应用微积分技术将它们派生到原始数据结构的类型！

嵌套集非常适合表示关系数据库中的树并对其运行查询。例如，ActiveRecords（Ruby on Rails的默认ORM）附带了一个非常简单的嵌套集插件，这使得处理树变得微不足道。

PQ树

我个人认为稀疏矩阵数据结构非常有趣。http://www.netlib.org/linalg/html_templates/node90.html

著名的BLAS库使用这些。当您处理包含100,000行和列的线性系统时，使用这些变得至关重要。其中一些也类似于计算机图形中常见的紧凑网格（基本上就像桶排序网格）。http://www.cs.kuleuven.be/~ares/publications/LD08CFRGRT/LD08CFRGRT.pdf

就计算机图形学而言，MAC网格有点有趣，但只是因为它们很聪明。http://www.seas.upenn.edu/~cis665/projects/Liquation_665_Report.pdf

它非常特定于领域，但半边数据结构非常简洁。它提供了一种迭代多边形网格（面和边）的方法，这在计算机图形学和计算几何中非常有用。

优先级双端队列比必须维护两个具有不同顺序的单独优先级队列便宜。http://www.alexandria.ucsb.edu/middleware/javadoc/edu/ucsb/adl/middleware/PriorityDeque.htmlhttp://cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf

增量列表/增量队列用于cron或事件模拟器等程序中，以确定下一个事件何时触发。http://everything2.com/title/delta+listhttp://www.cs.iastate.edu/~cs554/lec_notes/delta_clock.pdf

左倾红黑树。Robert Sedgewick在2008年发布的一个显着简化的红黑树实现（大约一半的代码行要实现）。如果你曾经无法理解红黑树的实现，请阅读这个变体。

与Andersson树非常相似（如果不完全相同）。

不是真正的数据结构；更多的是一种优化动态分配数组的方法，但Emacs中使用的间隙缓冲器有点酷。

替罪羊树。普通二叉树的一个经典问题是它们变得不平衡（例如，当键按升序插入时）。

平衡二叉树（AKA AVL树）在每次插入后都会浪费大量时间进行平衡。

红黑树保持平衡，但每个节点需要额外的存储空间。

替罪羊树像红黑树一样保持平衡，但不需要任何额外的存储。他们通过在每次插入后分析树并进行微小调整来做到这一点。参见http://en.wikipedia.org/wiki/Scapegoat_tree。

BK-Trees或Burkhard-Keller树是一个基于树的数据结构，可用于快速查找与字符串的近似匹配。

环境跟踪递归结构。

编译器使用递归结构，但不像树。内部作用域有一个指向封闭作用域的指针，因此嵌套是由内而外的。验证变量是否在作用域中是内部作用域对封闭作用域的递归调用。

public class Env{HashMap<String, Object> map;Env                     outer;
Env(){outer = null;map = new HashMap();}
Env(Env o){outer = o;map = new HashMap();}
void put(String key, Object value){map.put(key, value);}
Object get(String key){if (map.containsKey(key)){return map.get(key);}if (outer != null){return outer.get(key);}return null;}
Env push(){return new Env(this);}
Env pop(){return outer;}}

我不确定这个结构是否有名字。我称之为由内而外列表。

有一个聪明的数据结构，它使用数组来保存元素的数据，但数组在链接列表/数组中链接在一起。

这确实有一个优点，即对元素的迭代非常快（比纯链表方法更快），并且在内存和/或（取消）分配中移动带有元素的数组的成本最低。（正因为如此，这个数据结构对模拟很有用）。

我从这里了解到：

http://software.intel.com/en-us/blogs/2010/03/26/linked-list-verses-array/

“……并且分配一个额外的数组并链接到粒子数组的单元格列表中。这在某些方面类似于TBB实现其并发容器的方式。”（这是关于链接列表与数组的性能）

持久的数据结构

其他人已经提出了Burkhard-Keller-Trees，但我想我可能会再次提到它们，以便插入我自己的实现。：）

http://well-adjusted.de/mspace.py/index.html

有更快的实现（参见ActiveState的Python食谱或其他语言的实现），但我认为/希望我的代码有助于理解这些数据结构。

顺便说一句，BK树和VP树都可以用于搜索相似字符串之外的更多用途。你可以对任意对象进行相似性搜索，只要你有一个满足一些条件（正性、对称性、三角形不等式）的距离函数。

飞溅表很棒。它们就像一个普通的哈希表，除了它们保证了恒定的时间查找，并且可以处理90%的利用率而不会损失性能。它们是布谷鸟哈希的泛化（也是一个很好的数据结构）。它们看起来确实是专利，但和大多数纯软件专利一样，我不会太担心。

水桶旅

它们在Apache中被广泛使用。基本上它们是一个在环中循环的链表。我不确定它们是否在Apache和Apache模块之外使用，但它们适合作为一种很酷但鲜为人知的数据结构。桶是一些任意数据的容器，桶旅是桶的集合。这个想法是您希望能够在结构中的任何一点修改和插入数据。

假设您有一个存储桶旅，其中包含一个HTML文档，每个存储桶有一个字符。您想将所有<和>符号转换为<和>实体。存储桶旅允许您在遇到<或>符号时在存储桶中插入一些额外的存储桶，以适应实体所需的额外字符。因为存储桶旅在一个环中，您可以向后或向前插入。这比使用简单的缓冲区要容易得多（在C中）。

下面是一些关于桶旅的参考：

Apache Bucket旅参考

桶和旅的介绍

我以前在WPL树上很幸运。一种最小化分支加权路径长度的树变体。权重由节点访问决定，因此经常访问的节点迁移到更靠近根的位置。不知道它们与张开树相比如何，因为我从未使用过它们。

球树。只是因为它们让人们咯咯笑。

球树是一种在度量空间中索引点的数据结构。这是一篇关于构建它们的文章。它们通常用于查找点的最近邻居或加速k均值。

芬威克树。这是一种数据结构，用于在两个给定的子索引i和j之间记录向量中所有元素的总和。简单的解决方案，从一开始就预先计算总和，不允许更新项目（你必须做O（n）的工作来跟上）。

Fenwick Trees允许您在O（log n）中更新和查询，它的工作原理非常酷且简单。Fenwick的原始论文中对此进行了很好的解释，可在此处免费获得：

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

它的父亲，RQM树也非常酷：它允许您保留有关向量两个索引之间的最小元素的信息，并且它也适用于O（log n）更新和查询。我喜欢先教RQM，然后再教Fenwick树。

2-3棵手指树 by欣兹和帕特森是一个很好的函数式数据结构，具有很好的渐近性，适用于广泛的操作。虽然复杂，但它们比Kaplan和Tarjan之前的通过递归减速实现链式的持久列表的命令式结构要简单得多。

它们作为一个可连接的双端队列工作，O(1)访问任何一端，O(log min(n,m))追加，并提供O(log min(n,length - n))索引，直接访问序列任何部分的一元前缀和。

实现存在于haskell、Coq、F#、scala、Java、C、Clojure、c#和其他语言中。

您可以使用它们来实现优先搜索队列、区间映射、头部快速进入的绳索、映射、集合、可连序列或几乎任何结构，在这些结构中，您可以将其表示为在快速可捕获/可索引序列上收集一元结果。

我也有一些幻灯片描述它们的派生和使用。

自举斜二项堆由Gerth Stølting Brodal和Chris Okasaki：

尽管它们的名字很长，但它们提供渐近最优堆操作，即使在函数设置中也是如此。

• O(1)大小，联盟，插入，最小
• O(log n)删除权限

请注意，与数据结构教科书中常见的堆（例如左堆）不同，联合需要O(1)而不是O(log n)时间。与斐波那契堆不同，这些渐近是最坏情况，而不是摊销，即使持续使用！

在Haskell中有多个实现。

它们是由Brodal和Okasaki共同推导的，在Brodal提出具有相同渐近性的命令式堆之后。

我有时使用反转列表来存储范围，它们通常用于存储正则表达式中的字符类。参见示例http://www.ibm.com/developerworks/linux/library/l-cpinv.html

另一个很好的用例是加权随机决策。假设您有一个符号列表和相关的概率，您想根据这些概率随机选择它们

a => 0.1b => 0.5c => 0.4

然后你对所有的概率做一个运行和：

(0.1, 0.6, 1.0)

这是您的反转列表。您生成一个介于0和1之间的随机数，并找到列表中下一个更高条目的索引。您可以使用二进制搜索来执行此操作，因为它是排序的。获得索引后，您可以在原始列表中查找符号。

如果您有n个符号，则每个随机选择的符号有O（n）个准备时间，然后O（log（n））个访问时间-独立于权重的分布。

反转列表的变体使用负数来指示范围的端点，这使得计算在某一点有多少范围重叠变得容易。有关示例，请参见http://www.perlmonks.org/index.pl?node_id=841368。

工作窃取队列

用于在多个线程之间平均划分工作的无锁数据结构C/C++中工作窃取队列的实现？

B*tree

这是一种B树，以更昂贵的插入为代价进行有效的搜索。

区域四叉树

（引用自维基百科）

区域四叉树通过将区域分解为四个相等的象限、子象限等来表示二维空间的分区，每个叶节点包含对应于特定子区域的数据。树中的每个节点要么正好有四个子节点，要么没有子节点（叶节点）。

像这样的四叉树非常适合存储空间数据，例如纬度和经度或其他类型的坐标。

这是到目前为止我在大学里最喜欢的数据结构。编写这个家伙并看到它的工作非常酷。如果你正在寻找一个需要一些思考并且有点偏离常规的项目，我强烈推荐它。无论如何，它比你通常在数据结构课上分配的标准BST派生更有趣！

事实上，作为奖励，我发现了课堂项目（来自弗吉尼亚理工大学）这里（pdf警告）的讲座笔记。

阿恩·安德森树是红黑树的一种更简单的替代方案，其中只有正确的链接可以是红色的。这大大简化了维护，同时保持与红黑树相同的性能。原始论文给出了插入和删除的漂亮而简短的实现。

展开链表是链表上的一个变体，它在每个节点中存储多个元素。它可以大大提高缓存性能，同时减少与存储列表元数据（如引用）相关的内存开销。它与B树有关。

record node {node next       // reference to next node in listint numElements // number of elements in this node, up to maxElementsarray elements  // an array of numElements elements, with space allocated for maxElements elements}

最小-最大堆是堆的变体，实现了双端优先级队列。它通过对堆属性的简单更改来实现这一点：如果偶数（奇数）级别上的每个元素都小于（大于）所有子级和大子级，则称一棵树为min-max有序。级别从1开始编号。

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

芬威克树（或二进制索引树）是一个值得添加的工具包。如果你有一个计数器数组，并且你需要在查询累积计数时不断更新它们（如在PPM压缩中），Fenwick树将在O（log n）时间内完成所有操作，并且不需要额外的空间。另见这个topcoder教程以获得很好的介绍。

根据布隆过滤器提到的，可删除布隆过滤器（DlBF）在某些方面比基本计数变体更好。见http://arxiv.org/abs/1005.0352

A角缝数据结构。从摘要中：

角缝是一种技术表示矩形二维物体。看起来特别适合VLSI交互式编辑系统布局。数据结构有两个重要特点：第一，空的空间被明确表示；其次，矩形区域被缝合在他们的角落里像一个拼布被子这个组织结果在快速算法（线性时间或更好）搜索，创建、删除、拉伸和压缩。算法是在简化模型下提出VLSI电路和存储结构的要求是讨论过。测量表明角缝合需要大约是原来的三倍尽可能简单的存储空间代表。

Burrows-Wheeler变换（块排序压缩）

它是压缩的基本算法。假设你想压缩文本文件上的行。你会说如果你对行进行排序，你会丢失信息。但是BWT是这样工作的——它通过对输入进行排序来减少熵，保持整数索引以恢复原始顺序。

PATRICIA-检索以字母数字编码的信息的实用算法，D. R. Morrison（1968）。

PATRICIA树与Trie相关。Tries的问题是，当密钥集稀疏时，即当实际密钥形成潜在密钥集的一小部分时，通常情况下，Trie中的许多（大多数）内部节点只有一个后代。这导致Trie具有很高的空间复杂度。

我真的很喜欢区间树。它们允许你采取一堆间隔（即开始/结束时间，或者其他什么）并查询哪些间隔包含给定的时间，或者哪些间隔在给定的时间段内是“活动的”。查询可以在O（log n）中完成，预处理是O（n log n）。

DAWG是一种特殊的Trie，其中类似的子树被压缩到单亲中。我扩展了修改后的DAWG并提出了一个很好的数据结构，称为ASSDAWG（Anagram Search Sorted DAWG）。它的工作方式是每当将字符串插入DAWG时，它首先进行桶排序，然后插入，叶节点持有额外数量，指示如果我们从根到达叶节点，哪些排列是有效的。这有两个好处：

1. 由于我在插入之前对字符串进行排序，并且由于DAWGs自然折叠类似的子树，所以我得到了高级别的压缩（例如“吃”，“吃”，“茶”都变成了1路径a-e-t，在叶节点处有一个数字列表，指示a-e-t的哪些排列是有效的）。
2. 搜索给定字符串的字谜现在非常快速和简单，因为从根到叶的路径使用排列号在叶节点保存该路径的所有有效字谜。

异或链表使用两个异或指针来减少双重链表的存储需求。有点模糊但简洁！

半边数据结构和有翼边缘为多边形网格。

用于计算几何算法。

我不确定这个数据结构是否有名字，但是提议的tokenmap数据结构包含在Boost中有点有趣。这是一个动态可调整大小的映射，其中查找不仅是O（1），它们是简单的数组访问。我在这个数据结构上写了大部分背景材料，它描述了它如何工作的基本原理。

操作系统使用类似于令牌映射的东西将文件或资源句柄映射到表示文件或资源的数据结构。

我喜欢缓存不经意的数据结构。基本思想是在递归较小的块中布局一棵树，以便许多不同大小的缓存将利用适合它们的块。这导致在从RAM中的L1缓存到从磁盘读取的大块数据的所有方面有效使用缓存，而无需知道任何缓存层大小的细节。

我认为Paolo Ferragina和Giovanni Manzini的fm-指数真的很酷。特别是在生物信息学中。它本质上是一个压缩的全文索引，利用后缀数组和参考文本的Burrows-Wheer变换的组合。索引可以在不解压缩整个索引的情况下搜索。

直角三角形网络（RTIN）

自适应细分网格的非常简单的方法。拆分和合并操作只是几行代码。

三元搜索树

• 快速前缀搜索（用于增量自动完成等）
• 部分匹配（当您想找到字符串的X汉明距离内的所有单词时）
• 通配符搜索

很容易实现。

使用2个堆栈实现的队列非常节省空间（与使用至少有1个额外指针/引用开销的链表相反）。

如何使用两个堆栈实现队列？

当队列很大时，这对我来说效果很好。如果我在指针上保存8个字节，这意味着具有一百万个条目的队列节省了大约8MB的RAM。

我认为周期排序是一个非常简洁的排序算法。

这是一种排序算法，用于最小化写入总数。这在处理闪存时特别有用，其中闪存的寿命与写入量成正比。这是维基百科文章，但我建议转到第一个链接。（漂亮的视觉效果！）

Zobrist散列是一个哈希函数，通常用于表示游戏棋盘的位置（如国际象棋），但肯定有其他用途。它的一个好处是可以随着棋盘的更新而递增更新。

不相交的森林允许快速成员查询和联合操作，并且在克鲁斯卡尔算法中最著名的是用于最小生成树。

真正酷的是，这两个操作都有与阿克曼函数的逆成比例的摊销运行时间，使其成为“最快”的非恒定时间数据结构。

当我阅读一些与RMQ和LCA相关的算法时，我偶然发现了另一个数据结构笛卡尔树。在笛卡尔树中，两个节点之间的最低公共祖先是它们之间的最小节点。将RMQ问题转换为LCA很有用。