以下数据结构有名称吗?有论文和引文吗?
实现高效的集合抽象数据类型的一种方法是拥有一个排序数组的集合,其中每个数组都有唯一的2的幂大小。
例如,一组 13 个元素 {1, 2, ..., 13} 可以用这个排序数组的集合来表示:{[5], [2, 3, 9, 13], [1, 4, 6, 7, 8, 10, 11, 12]}.一般来说,集合中的数组的大小与集合大小的二进制表示形式中的 1 位相对应。该数据结构是高效的,因为插入可以在摊销 θ(log
n) 时间内执行,并且搜索可以在 θ((log n)2) 时间内执行(这比线性搜索更好)。此外,它仅使用 θ(log n) 空间开销来存储指针,这与平衡二叉树和 B 树不同,平衡二叉树和 B 树使用 θ(n) 额外空间来存储指针。因此,几乎所有空间都用于有效负载数据。
我查看了维基百科的数据结构列表,但没有找到匹配的内容。确实,《算法导论》(“CLRS”)一书在“摊销分析”部分将这种数据结构描述为作业问题,但由于这是一个问题而不是示例,因此本书对此没有过多提及。
如果我是你,我会询问 cstheory
,然后写信给 CLRS,但考虑到次优边界和缺乏删除,我不希望出现任何结果,除非简洁数据结构 社区对某些内容感兴趣点。 有什么特别想知道的吗?