算法谜题 : sequence with random access, 插入和移除

Question

描述一个数据结构，其中:

• 任何项目都由数组中的整数值索引
  • 一个整数可以索引一个值
  • 用于索引项目的整数连续:它们从 1 到 n 没有空洞
• 获取位置 i 的项目(即:与整数 i 关联的项目)应该尽可能快
  • 随机访问
• 在位置 i 插入一个新项目应该尽可能快
  • 这将从 i 开始向右移动任何项目
• 在位置 i 移除一个项目也应该尽可能快
  • 这将从 i+1 开始向左移动任何项目

编辑:我忘记了一件小事:项目索引只能在添加/删除项目时移动，它们不能随机交换。

在此描述中，n 是结构的大小(即:它包含多少项)，i 是一个通用整数(1 <= i <= n)，当然可以。

---

我是从我在学校遇到的一个人那里听说的。不知道是面试题、考试题还是谜语还是什么，但我想这可能是一切。

如果我没记错的话(嘿，那是在 12 月 24 日之前)他说这样的数据结构可以通过 O(sqrt n) 插入/删除和 O(1 ) 访问时间，或者用 O(log n) 进行任何操作。

---

编辑:已经给出了一些正确的答案。如果您不想再考虑这个问题，请阅读它。

Answer 1

好吧，任何类型的自平衡二叉树(例如，红黑树)都将为 O(logn) 提供所有三种操作。提到的 C++ 映射 RB 就是一个例子(如果我没有完全忘记 C++ 的话)。

至于索引(get 操作)，有一个标准技巧。我们将在每个节点中存储其左子树有多少个节点。现在我们可以用这样的方式在 O(logn) 时间内定位 i 位置的元素

Data get(Node root, int i) {
    if (i <= root.leftCount) {
        return get(root.left, i);
    } else if (i == root.leftCount + 1) {
        return node;
    } else {
        return get(root.right, i - root.leftCount - 1);
    }
}

显然，每次添加或删除元素时，都必须重新计算 leftCount 值，但这只需要对 O(logn) 节点进行. (想一想有多少节点在其左子树中包含已删除的节点 - 只有直接位于它和根节点之间的节点)