algorithm - 具有快速插入和快速搜索的排序序列的最简单 DS 是什么？

Question

我正在寻找一个易于实现(在 C++ 中)的数据结构 D，它维护一个排序的整数序列(或任何可比较的对象)，具有快速插入和快速搜索(即可以检查如果 X 在 D 中，则获取第 i 个元素)。快应该是 O(log(n))、O(1) 还是 O(sqrt(N))？

template<type T>
Class D {
  D(...) { ... }
  void insert(T x);
  int get_ith(int x);
  boolean check_x(T x);
}

目前，我了解 AVL 树、红黑树、跳表、尝试、哈希。所有这些都需要非常复杂且难以编码的解决方案。尝试可能是最不复杂的。然而，删除元素和为 trie 选择字母表等操作是很困难的。

我希望探索简短而快速的新颖解决方案。

提前致谢!

Answer 1

如果您知道整数值的上限，您可以简单地占用一 block 内存并使用集合中数字的位。

• 如果 X 在 D 中:O(1)
• 插入:O(1)
• 删除:O(1)

如果整数在从最低值到最高值的范围内稀疏，迭代会很慢。在这种情况下，内存消耗也可能是 Not Acceptable 。