2

我需要一个数据结构，它将非重叠范围（例如8..15，16..19）映射到指向结构的指针。

我需要能够查找该范围内的任何元素并检索该指针。例如：

structure[8..15] = 0x12345678;
structure[16..19] = 0xdeadbeef;

structure[7]; // => NULL
structure[12]; // => 0x12345678
structure[18]; // => 0xdeadbeef

我目前正在考虑使用二叉搜索树。由于范围永远不会重叠，我可以在对数时间内相对轻松地搜索索引。

但是，我想知道是否有任何数据结构更适合这种情况。我需要能够有效地插入、删除和查找。在 BST 中，所有这些操作都是 O(log n)，但我想知道是否有任何更快的方法。

4

2 回答 2

3

如果您想要比 O(log n) 更快的东西，请使用Van Emde Boas tree。

应该像使用二叉搜索树一样使用它：使用每个范围的开始作为键，范围的结束 - 作为值的一部分（与指针一起），映射到该键。时间复杂度是 O(log log M)，其中 M 是键的范围（INT_MAX，如果任何整数值都可以作为范围的开始）。

在某些情况下，Van Emde Boas 树的内存开销很大。如果这不可接受，请使用 Beni 解释的简单 trie 或Y-fast trie。

于 2012-11-01T14:23:02.643 回答
2

我不认为你可以做得更好。

非重叠范围等同于一系列交替的起点/终点。所以查找只是“找到最大元素≤ x”，然后是 O(1) 检查它是开始还是结束。即有序地图。

通常的疑点——二叉树、B 树、各种尝试——本质上都是 O(log n)。在实践中最好的是调整问题，这取决于对范围的了解。它们是稀疏的还是密集的？它们的大小相似还是差异很大？数据有多大（适合缓存/内存/磁盘）？你插入/删除很多还是查找占主导地位？访问是随机的还是具有高局部性？

适用于许多方案的一种权衡是拆分范围，在多个位置复制相同的指针。这可能会以插入/删除和内存使用为代价来加快查找速度。一个极端的应用程序只是一个按点索引的平面数组，其中查找是 O(1)，但插入是 O(范围大小)；这需要一个多级结构：一个由 k 个统一子范围组成的数组，如果完全被一个范围覆盖，则指向值，否则指向子数组。嘿，我刚刚描述了一个尝试！查找是 log(maxint)/log(k)，如果 k 是 2 的幂（例如 256），则非常快；插入和内存是 k*log(n)。
但请记住，浪费内存会损害缓存性能，因此任何此类“优化”实际上可能会适得其反，即使对于查找也是如此。

于 2012-11-01T00:26:35.743 回答