有哪些不太为人知但很有用的数据结构？

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

这种结构可以用于：

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

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

我喜欢treaps——因为它采用了随机优先级堆结构与二叉搜索树的叠加，从而实现平衡的简单而有效的想法。

Arne Andersson树是红黑树的一种简化替代，只有右链接可以是红色。这大大简化了维护，同时保持了与红黑树相同的性能。原始论文提供了插入和删除的简洁实现。请参考Arne Andersson trees和原始论文。

DAWG是一种特殊的字典树，其中类似的子树被压缩为单个父节点。我扩展改进了DAWG，并提出了一个巧妙的数据结构称为ASSDAWG（Anagram Search Sorted DAWG）。它的工作原理是将字符串插入到DAWG中时，首先进行桶排序，然后再插入，叶节点保留了一个额外的数字，指示如果我们从根节点到达该叶节点，则哪些排列是有效的。

这有两个巧妙的优点：

1. 由于在插入之前对字符串进行了排序，而且DAWG自然地合并了相似的子树，因此可以实现高水平的压缩（例如，“eat”，“ate”，“tea”都成为一个路径a-e-t，叶节点上带有数字列表，表示a-e-t的哪些排列是有效的）。
2. 现在查找给定字符串的所有字谜非常快捷和简单，因为从根到叶的路径使用排列号码保存了该路径的所有有效字谜。

我有时会使用倒排列表来存储范围，它们经常用于在正则表达式中存储字符类。例如，请参见http://www.ibm.com/developerworks/linux/library/l-cpinv.html 另一个好的用例是用于加权随机决策。假设您有一组符号和相关概率，并且您想根据这些概率随机选择它们。

   a => 0.1
   b => 0.5
   c => 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以获取示例。

快速紧凑的数据结构：

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

• HAT-trie：基于缓存感知的 Trie 的字符串数据结构

• B-tries 用于基于磁盘的字符串管理

计算未排序的平衡二叉树。

非常适合文本编辑器缓冲区。

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

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

Zobrist Hashing 是一种哈希函数，通常用于表示游戏棋盘的位置（例如在国际象棋中），但肯定还有其他用途。它的一个好处是可以在更新棋盘时进行增量更新。

Fenwick树（或二叉索引树）是编程工具箱中值得添加的一种数据结构。如果您有一个计数器数组，并且需要在不断更新它们的同时查询累积计数（如PPM压缩中），Fenwick树将在O(log n)时间内执行所有操作，且不需要额外的空间。此外，topcoder教程也提供了良好的介绍。