logo标签列表

你应该听说过的复杂数据结构有哪些？

performancealgorithmdata-structures
16

这是一个派生问题，但我想了解哪些数据结构对于它们的实用性至少应该熟悉。 然而，这些结构如果没有一定的专业知识，就很难实现。

我认为两者之间的好界限是堆 -- 你应该能够编写一个堆，但需要一天时间。 不适合的是二叉搜索树等。编辑：我看到这取决于你在做什么。 我认为有一个列出使用原因的短语清单会很棒！

以下是一个起点列表：

  1. B+ 树：在单个键上良好的常规索引结构
  2. K-d 树：空间数据
  3. 红黑树：自平衡二叉搜索树；也有 AVL 或 splay 树
  4. 跳跃表：对于随机或（伪）顺序访问的良好混合结构
  5. Trie 树：线性时间字符串搜索
什么是鲜为人知但很酷的数据结构？ - Casebash
14个回答
4
不相交集合的实现非常容易。但是分析起来很困难。 - Phil Miller
2

这是一个很好的开始; 在维基百科上有一个全面的数据结构列表，其中一些应该被检查。但是你需要哪些，取决于你打算做什么领域的工作。

嵌入式系统工程师会和Web开发人员有非常不同的想法，并且业务逻辑工程师会强烈反对他们。先搞清楚你想要做什么; 编程语言和平台也会影响你所需的列表。

2
2

van Emde Boas树。我并不认为你一定要听说过它们，但我相信它们是使用“位操作技巧”实现的复杂性的有趣例子 --- 它的时间复杂度是O(log log n)，比二叉树高出指数倍！

1
1
与您提到的B+树密切相关的是B*-tree。这些树以及一种称为“跳舞树”方法的平衡方法，共同构成了Reiser4的基础。
1

二进制决策图，特别是简化序列二进制决策图（ROBDD）。当有人决定创建自己的过滤系统时，这些东西经常被重新发明（很差地）。

1

布谷鸟哈希，一种简单而优雅的方法，可以在预期的常数时间内解决哈希表冲突。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接