周围有一些数据结构非常有用,但大多数程序员都不知道。他们是哪一个?

每个人都知道链表、二叉树和散列,但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构,因为它们依赖于伟大的想法,丰富了程序员的工具箱。

PS:我还对舞蹈链接等技术感兴趣,这些技术巧妙地利用了通用数据结构的财产。

编辑:请尝试包含更详细描述数据结构的页面链接。此外,试着补充几句关于数据结构为什么很酷的话(正如乔纳斯·Kölker已经指出的那样)。此外,尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。


当前回答

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

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

其他回答

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

Fenwick Trees允许您在O(logn)中更新和查询,它的工作方式非常简单。芬威克的原始论文对这一点做了很好的解释,可以在这里免费获得:

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

它的父亲RQM树也很酷:它允许您保存关于向量的两个索引之间的最小元素的信息,它还可以在O(logn)更新和查询中工作。我喜欢先教RQM,然后教芬威克树。

计数的未排序平衡树。

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

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

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

如果实施得当,您可以在保持性能的同时,甚至可以提高性能,从而大大减少内存占用。

Van Emde Boas树

我想知道它们为什么很酷会很有用。一般来说,“为什么”这个问题是最重要的;)

我的答案是,他们给你O(log-logn)字典,其中包含{1..n}个键,而与使用的键的数量无关。就像重复减半得到O(log n)一样,重复平方得到O(log-log n),这就是vEB树中发生的情况。

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

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

同样就计算机图形而言,MAC网格有些有趣,但这仅仅是因为它们很聪明。http://www.seas.upenn.edu/~cis665/projects/Liquiation_665_Report.pdf