一个人应该知道的一些鲜为人知的数据结构和算法是什么？

Question

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

我想知道我需要知道的其他数据结构是什么？我知道 - 数组,列表,堆栈,队列,链接列表,哈希表,树及其不同的形式,如B-tree,Trie等.想知道您是否发现其他一些有趣的数据结构/概念以及有用的定期开发周期.

Answer 1

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

您还遗漏了堆，它们通常用作优先级队列的基础结构。二叉堆是最简单的，但您也可以研究最小-最大-中值堆、二项式堆（快速合并）和斐波那契堆（快速递减键 - 对于某些图形算法有用）。

其他有趣的数据结构包括帕特里夏尝试（Patricia attempts），这是一种节省空间的尝试（以子字符串而不是字符为键），展开树（splay trees），它是平衡的并且可以编程为持久的。另请查看布隆过滤器，它是一种概率数据结构，可让您确定元素是否是集合的成员。它可能会出现误报，但不会出现误报，并且具有空间/时间效率。

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