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

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

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

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


当前回答

任何有3D渲染经验的人都应该熟悉BSP树。通常,这是一种通过构造3D场景来进行渲染的方法,该方法可以在知道相机坐标和方位的情况下进行管理。

二进制空间分区(BSP)是一种递归细分a的方法通过超平面将空间划分为凸集。该细分产生通过方法表示场景树数据结构的BSP树。换句话说,这是一种方法形状复杂的破碎多边形转化为凸集,或更小多边形完全由非反射角(小于180°). 更一般的描述空间分区,请参见空间分区。最初,提出了这种方法在3D计算机图形方面渲染效率。其他一些应用程序包括执行具有形状的几何操作(构造实体几何),机器人和3D中的碰撞检测计算机游戏和其他计算机涉及处理的应用程序复杂的空间场景。

其他回答

区域四叉树

(引自维基百科)

区域四叉树通过将区域分解为四个相等的象限、子象限等来表示二维空间的分区,每个叶节点包含对应于特定子区域的数据。树中的每个节点要么正好有四个子节点,要么没有子节点(叶节点)。

像这样的四叉树很适合存储空间数据,例如纬度和经度或其他类型的坐标。

这是我在大学里最喜欢的数据结构。对这家伙进行编码并看到它的工作非常酷。如果你正在寻找一个需要思考并且有点偏离常规的项目,我强烈建议你这样做。无论如何,它比通常在数据结构类中分配的标准BST派生工具有趣得多!

事实上,作为奖励,我在这里找到了(弗吉尼亚理工大学的)课堂项目前的演讲笔记(pdf警告)。

尝试,也称为前缀树或临界位树,已经存在了40多年,但仍然相对未知。在“TRASH-一个动态LC trie和哈希数据结构”中描述了一个非常酷的trys用法,它将trie与哈希函数结合在一起。

跳过列表非常整洁。

维基百科跳过列表是一种概率数据结构,基于多个并行、排序的链接列表,其效率与二进制搜索树相当(大多数操作的顺序日志n平均时间)。

它们可以作为平衡树的替代(使用概率平衡而不是严格执行平衡)。它们很容易实现,而且比红黑树更快。我认为他们应该在每一个优秀的程序员工具箱中。

如果你想深入了解跳过列表,这里有一个麻省理工学院算法简介讲座视频的链接。

此外,这里还有一个Java小程序,直观地演示了跳过列表。

看看手指树,特别是如果你是前面提到的纯函数数据结构的粉丝。它们是持久序列的功能表示,支持以摊销的恒定时间访问末端,以及以较小片段的大小按时间对数连接和拆分。

根据原文:

我们的函数2-3指树是Okasaki(1998)介绍的一种通用设计技术的一个实例,称为隐式递归减速。我们已经注意到,这些树是他的隐式deque结构的扩展,用2-3个节点替换对,以提供高效连接和拆分所需的灵活性。

手指树可以用幺半群参数化,使用不同的幺半群将导致树的不同行为。这使手指树可以模拟其他数据结构。

我喜欢字符串处理的后缀树和数组,平衡列表的跳过列表,自动平衡树的显示树