周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
PATRICIA-检索字母数字编码信息的实用算法，D.R.Morrison（1968）。
PATRICIA树与Trie相关。Tries的问题是，当密钥集稀疏时，即当实际密钥形成潜在密钥集的一个子集时，Trie中的许多（大多数）内部节点只有一个后代，这是非常常见的情况。这导致Trie具有较高的空间复杂性。
http://www.csse.monash.edu.au/~合金/瓷砖AlgdS/树/PATRICIA/
其他回答
成对堆是一种堆数据结构，具有相对简单的实现和出色的实际摊余性能。
三元搜索树
快速前缀搜索（用于增量自动完成等）部分匹配（当您想查找字符串X汉明距离内的所有单词时）通配符搜索
很容易实施。
斐波那契堆
它们被用于一些已知的最快算法（渐近）中，用于许多与图相关的问题，例如最短路径问题。Dijkstra的算法在标准二进制堆的O（E log V）时间内运行；使用斐波那契堆将其提高到O（E+V log V），这对于密集图来说是一个巨大的加速。然而，不幸的是，它们有一个很高的恒定因子，往往使它们在实践中不切实际。
PATRICIA-检索字母数字编码信息的实用算法，D.R.Morrison（1968）。
PATRICIA树与Trie相关。Tries的问题是，当密钥集稀疏时，即当实际密钥形成潜在密钥集的一个子集时，Trie中的许多（大多数）内部节点只有一个后代，这是非常常见的情况。这导致Trie具有较高的空间复杂性。
http://www.csse.monash.edu.au/~合金/瓷砖AlgdS/树/PATRICIA/
Hinze和Paterson的2-3手指树是一种功能强大的数据结构瑞士军刀，具有很好的渐近线，适用于各种操作。虽然复杂，但它们比之前的Kaplan和Tarjan通过递归减速实现的持久列表的命令式结构简单得多。
它们作为一个可链接的deque，O（1）访问任意一端，O（log-min（n，m））追加，并提供O（log-main（n），length-n））索引，直接访问序列的任何部分上的单形前缀和。
实现存在于Haskell、Coq、F#、Scala、Java、C、Clojure、C#和其他语言中。
您可以使用它们来实现优先级搜索队列、区间映射、具有快速头部访问的绳索、映射、集合、可链接序列或几乎任何结构，您可以将其表述为在快速可链接/可索引序列上收集单形结果。
我还有一些幻灯片描述了它们的派生和使用。
