相关疑难解决方法(0)

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

每个人都知道链接列表,二叉树和哈希,但是例如跳过列表和布隆过滤器.我想知道更多不常见的数据结构,但值得了解,因为它们依赖于很棒的想法并丰富了程序员的工具箱.

PS:我也对像跳舞链接这样的技巧感兴趣,这些技巧巧妙地使用了常见数据结构的属性.

编辑:请尝试更详细地包含指向描述数据结构的页面的链接.此外,尝试添加几个关于数据结构为什么很酷的词(正如JonasKölker已经指出的那样).此外,尝试为每个答案提供一个数据结构.这将允许更好的数据结构根据他们的投票单独浮动到顶部.

在我编程的10年里,我可以计算我一方面使用的数据结构的数量:数组,链表(我将堆栈和队列放在一起)和字典.考虑到我编写的几乎所有应用程序都属于数据形式/ CRUD类别,这并不奇怪.

我从来不需要使用红黑树,跳过列表,双端队列,循环链表,优先级队列,堆,图或过去50年来研究过的数十种奇异数据结构中的任何一种.我觉得我错过了.

这是一个开放式的问题,但这些"异国情调"的数据结构在实践中使用在哪里？有没有人有使用这些数据结构解决特定问题的实际经验？

我听说过一种新的平衡 BST 数据结构，称为zip 树。什么是zip树？它是如何工作的？

我偶然发现了维基百科页面:

融合树

我读到了底部链接的课堂笔记pdf,但它对数据结构本身有了一些手感,并详细介绍了该sketch(x)功能.我认为我的一些困惑是文章试图非常笼统,我想要一个可视化的具体例子.

此数据结构是否适合存储基于任意32或64位整数键的数据？它与B树有何不同？有一节说它基本上是一个带有分支因子的B树B = (lg n)^(1/5).对于具有32位密钥的完全填充的树,B将为2.这是否只是一个二叉树？这个数据结构是否打算使用更长的位串作为键？

我的谷歌搜索没有发现任何非常有用的东西,但我欢迎任何有关该主题的良好链接.这真的只是一种好奇心,所以我还不愿意为PDF付费portal.acm.org.

这是一个衍生问题,但我正在询问您至少应该熟悉它们的实用性的数据结构.如果没有一些专业知识,这些结构太难实现.

我会说两者之间的良好界限是堆 - 你应该能够编写一个堆,但它需要你一天.不合适的是BST等.编辑:我认为这取决于你在做什么.我认为列出一个包含总结您使用它的原因的短语会很棒!

这是一个开始的列表:

1. B +树:单个键上的一般索引结构很好
2. Kd树:空间数据
3. 红黑树:自平衡BST; 还有AVL或splay树
4. 跳过列表:用于随机或(伪)顺序访问的良好混合结构
5. Trie:线性时间字符串搜索

有一种相对较新的数据结构 (2020)，称为XOR 过滤器，它被用作布隆过滤器的替代品。

什么是异或滤波器？与布隆过滤器相比，它有哪些优势？它是如何运作的？

什么是计数分钟草图？在什么情况下会有用？