我有一个超过十亿的排序整数，你认为哪种数据结构可以利用排序行为？主要目标是更快地搜索项目......我能想到的选择 -1）常规二进制搜索树，在中间方法中递归拆分 .2）任何其他 balancer 的二进制搜索树应该运行良好，但不利用排序的启发式..
提前致谢..
[编辑]插入和删除非常罕见......此外，除了整数，我必须在节点中存储一些其他信息，我认为普通数组不能这样做，除非它是一个列表对吗？
这实际上取决于您要对数据执行的操作 .
如果您只是搜索数据而从不插入或删除任何内容，只需将数据存储在一个巨大的排序数组中就可以了 . 然后，您可以使用二进制搜索在O（log n）时间内有效地查找元素 . 然而，插入和删除可能是昂贵的，因为有十亿个整数O（n）会受到伤害 . 如果您愿意，可以将辅助信息存储在数组本身内，只需将其放在每个整数旁边即可 .
但是，如果使用十亿个整数，这可能会占用大量内存，您可能需要切换到使用位向量 . 然后，您可以在时间O（log U）中对位向量进行二进制搜索，其中U是位数 . 有十亿个整数，我假设U和n会很接近，所以这不是一个很大的惩罚 . 根据机器字大小的不同，这可以节省32x到128x内存，而不会造成太大的性能损失 . 此外，这将增加二进制搜索的位置，并且还可以提高性能 . 这确实使得实际迭代列表中的数字要慢得多，但它使插入和删除花费O（1）时间 . 为此，您需要存储一些包含与每个整数关联的数据的二级结构（可能是一个哈希表？） . 这不是太糟糕，因为一旦找到了您正在寻找的内容，就可以将这个排序的位向量用于排序查询和未排序的哈希表 .
如果您还需要在列表中添加和删除值，则 balancer 的BST可能是一个不错的选择 . 但是，因为您特别知道存储整数，所以您可能需要查看更复杂的van Emde Boas树结构，它支持O中的插入，删除，前驱，后继，查找最大和查找全部（ log log n）时间，它比二叉搜索树快得多 . 但是，这种方法的实施成本很高，因为数据结构非常难以实现 .
您可能想要探索的另一个数据结构是按位trie，它与排序位向量具有相同的时间范围，但允许您将辅助数据与每个整数一起存储 . 此外，它非常容易实现！
希望这可以帮助！
搜索有序整数的最佳数据结构是一个数组 .
您可以使用log（N）操作进行搜索，并且它比树更紧凑（更少的内存开销） .
而且你甚至不需要编写任何代码（因此错误的可能性更小） - 只需使用标准库中的 bsearch 即可 .
bsearch
使用排序数组，您可以通过插值搜索获得最佳效果，即可获得log（log（n））平均时间 . 它本质上是一个二进制搜索，但不会将数组划分为相同大小的2个子数组 . 它非常快速且非常容易实现 .
http://en.wikipedia.org/wiki/Interpolation_search
不要让最坏的情况O（n）束缚你，因为有10亿个整数，实际上不可能获得 .
O（1）解决方案：
一个大小为2³²的查找表（大约40亿个元素），其中每个索引对应于具有该值的整数数 .
一个非常大的哈希表 . 如果你有一个合理的值分布，通常的模数散列函数是合适的，如果没有，你可能想要将32位策略与散列查找结合起来 .
4 回答
这实际上取决于您要对数据执行的操作 .
如果您只是搜索数据而从不插入或删除任何内容，只需将数据存储在一个巨大的排序数组中就可以了 . 然后，您可以使用二进制搜索在O（log n）时间内有效地查找元素 . 然而，插入和删除可能是昂贵的，因为有十亿个整数O（n）会受到伤害 . 如果您愿意，可以将辅助信息存储在数组本身内，只需将其放在每个整数旁边即可 .
但是，如果使用十亿个整数，这可能会占用大量内存，您可能需要切换到使用位向量 . 然后，您可以在时间O（log U）中对位向量进行二进制搜索，其中U是位数 . 有十亿个整数，我假设U和n会很接近，所以这不是一个很大的惩罚 . 根据机器字大小的不同，这可以节省32x到128x内存，而不会造成太大的性能损失 . 此外，这将增加二进制搜索的位置，并且还可以提高性能 . 这确实使得实际迭代列表中的数字要慢得多，但它使插入和删除花费O（1）时间 . 为此，您需要存储一些包含与每个整数关联的数据的二级结构（可能是一个哈希表？） . 这不是太糟糕，因为一旦找到了您正在寻找的内容，就可以将这个排序的位向量用于排序查询和未排序的哈希表 .
如果您还需要在列表中添加和删除值，则 balancer 的BST可能是一个不错的选择 . 但是，因为您特别知道存储整数，所以您可能需要查看更复杂的van Emde Boas树结构，它支持O中的插入，删除，前驱，后继，查找最大和查找全部（ log log n）时间，它比二叉搜索树快得多 . 但是，这种方法的实施成本很高，因为数据结构非常难以实现 .
您可能想要探索的另一个数据结构是按位trie，它与排序位向量具有相同的时间范围，但允许您将辅助数据与每个整数一起存储 . 此外，它非常容易实现！
希望这可以帮助！
搜索有序整数的最佳数据结构是一个数组 .
您可以使用log（N）操作进行搜索，并且它比树更紧凑（更少的内存开销） .
而且你甚至不需要编写任何代码（因此错误的可能性更小） - 只需使用标准库中的
bsearch即可 .使用排序数组，您可以通过插值搜索获得最佳效果，即可获得log（log（n））平均时间 . 它本质上是一个二进制搜索，但不会将数组划分为相同大小的2个子数组 . 它非常快速且非常容易实现 .
http://en.wikipedia.org/wiki/Interpolation_search
不要让最坏的情况O（n）束缚你，因为有10亿个整数，实际上不可能获得 .
O（1）解决方案：
一个大小为2³²的查找表（大约40亿个元素），其中每个索引对应于具有该值的整数数 .
一个非常大的哈希表 . 如果你有一个合理的值分布，通常的模数散列函数是合适的，如果没有，你可能想要将32位策略与散列查找结合起来 .