周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
持久数据结构
其他回答
工作窃取队列
无锁数据结构，用于在多个线程之间平均分配工作C/C++中工作窃取队列的实现？
Scapegoat树。普通二叉树的一个典型问题是它们变得不平衡（例如，当按升序插入键时）
平衡二叉树（AKA AVL树）在每次插入后都会浪费大量时间进行平衡。
红黑树保持平衡，但每个节点都需要额外的存储空间。
Scapegoat树像红黑树一样保持平衡，但不需要任何额外的存储。他们通过在每次插入后分析树并进行微小调整来实现这一点。看见http://en.wikipedia.org/wiki/Scapegoat_tree.
XOR链表使用两个XOR'd指针来减少双链表的存储需求。有点晦涩但整洁！
PATRICIA-检索字母数字编码信息的实用算法，D.R.Morrison（1968）。
PATRICIA树与Trie相关。Tries的问题是，当密钥集稀疏时，即当实际密钥形成潜在密钥集的一个子集时，Trie中的许多（大多数）内部节点只有一个后代，这是非常常见的情况。这导致Trie具有较高的空间复杂性。
http://www.csse.monash.edu.au/~合金/瓷砖AlgdS/树/PATRICIA/
任何有3D渲染经验的人都应该熟悉BSP树。通常，这是一种通过构造3D场景来进行渲染的方法，该方法可以在知道相机坐标和方位的情况下进行管理。
二进制空间分区（BSP）是一种递归细分a的方法通过超平面将空间划分为凸集。该细分产生通过方法表示场景树数据结构的BSP树。换句话说，这是一种方法形状复杂的破碎多边形转化为凸集，或更小多边形完全由非反射角（小于180°). 更一般的描述空间分区，请参见空间分区。最初，提出了这种方法在3D计算机图形方面渲染效率。其他一些应用程序包括执行具有形状的几何操作（构造实体几何），机器人和3D中的碰撞检测计算机游戏和其他计算机涉及处理的应用程序复杂的空间场景。
