algorithm - 人们应该知道哪些鲜为人知的数据结构和算法？

Question

最近我遇到了 SkipList 数据结构。它确实帮助我解决了一个原本难以解决的问题。我一直在努力使用平衡二叉树来解决它，但它变得非常复杂，因为树需要始终保持平衡，我想知道不仅存在特定值而且存在一定范围内的值。 SkipList 帮助我有效地解决了这个问题。

我想知道我还需要了解哪些其他数据结构？我知道 - 数组、列表、堆栈、队列、链表、哈希表、树及其不同形式，如 B 树、Trie 等。想知道您是否发现其他一些数据结构/概念在常规开发周期中既有趣又有用。

Answer 1

您没有提到非常强大的图表，如果您不了解它们，您绝对应该阅读它们。查阅 Dijkstra 算法和 A* 搜索算法以及一般的深度优先搜索和广度优先搜索。

您还遗漏了堆，堆通常用作优先级队列的底层结构。二叉堆是最简单的，但您也可以查看最小-最大中值堆、二项式堆(快速合并)和斐波那契堆(快速递减键 - 对于某些图算法很有用)。

其他有趣的数据结构包括 Patricia 尝试，它是节省空间的尝试(以子字符串而不是字符为键)，splay 树，它是平衡的并且可以编程为持久的。还要检查 Bloom 过滤器，它是一种概率数据结构，可让您确定元素是否是集合的成员。它可以有误报，但没有误报，并且空间/时间效率高。

最后，您可以走函数路线，研究不可变和持久的数据结构。其中许多只是您已知的数据结构的功能版本。如果您对此感兴趣，那么我建议您查看 Okasaki 的 Purely Functional Datastructures。