data-structures - 将非重叠范围映射到值的数据结构？

Question

我需要一个将非重叠范围(例如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)，但我想知道是否有更快的方法。

Answer 1

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

它的使用方式应该与使用二叉搜索树相同:使用每个范围的开头作为键，使用范围的结尾作为值的一部分(与指针一起)，映射到该键。时间复杂度为 O(log log M)，其中 M 是键的范围(INT_MAX，如果范围开始可以有任何整数值)。

在某些情况下，Van Emde Boas 树具有较大的内存开销。如果这是 Not Acceptable ，请使用简单的 trie，如 Beni 所解释的，或 Y-fast trie .