什么是较少知道但有用的数据结构？

有一些数据结构是非常有用的，但大多数程序员都不知道。 他们是哪一个？

每个人都知道链表，二叉树和散列，但跳过列表和布卢姆过滤器例如。 我想知道更多不太常见的数据结构，但值得了解，因为它们依靠伟大的想法并丰富了程序员的工具箱。

PS：我对像跳舞链接这样的技术也很感兴趣，这些技术巧妙地使用了通用数据结构的属性。

编辑 ：请尝试将链接包含到更详细描述数据结构的页面中。 另外，为了说明为什么数据结构很酷，尝试添加几句话（正如JonasKölker已经指出的那样）。 另外，尝试为每个答案提供一个数据结构 。 这将允许更好的数据结构根据他们的投票单独浮到顶部。

---

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

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

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

替罪羊的树木像红黑树木一样保持平衡，但不需要任何额外的存储空间。 他们通过在每次插入后分析树并进行微小调整来完成此操作。 请参阅http://en.wikipedia.org/wiki/Scapegoat_tree。

---

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

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

---

Hinze和Paterson的2-3 Finger Tree是一款功能强大的数据结构瑞士军刀，具有极大的渐进性，适用于各种操作。 虽然复杂，但它们比持续列表中的命令式结构要简单得多，通过持续列表，并通过Kaplan和Tarjan在它们之前的递归减速进行连接。

它们作为一个可链接的deque，通过O(1)访问任一端， O(log min(n,m))追加，并提供O(log min(n,length - n))索引，直接访问monoidal前缀总和序列的任何部分。

Haskell，Coq，F＃，Scala，Java，C，Clojure，C＃等语言都有实现。

您可以使用它们来实现优先搜索队列，区间映射，快速访问头部的索引，映射，集合，可链接序列或几乎任何可以将它描述为通过快速链接/可索引序列收集monoidal结果的结构。

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

链接地址: http://www.djcxy.com/p/6777.html

上一篇: What are the lesser known but useful data structures?

下一篇: Is there any scenario where the Rope data structure is more efficient than a string builder