java - 是否可以从索引数据结构中删除并同时避免移位？

Question

我有:

0 => a
1 => x
2 => A
...
1356 => w
1357 => o

到目前为止，我可以轻松获得 pos 555，因为它已被索引，换句话说，不需要线性搜索。

现在，如果我删除位置 333，则其上方的所有内容都必须移动，因为下次我调用 get(555) 时，删除的元素将是旧的 556，现在是移动后的新 555。

但是当您的列表很大时，转移成本很高。

有没有一种方法可以在不移动的情况下删除并仍然保持所有内容正确索引？

首先想到的是双链表，但它没有索引。

我是否需要一些奇怪的数据结构组合来节省移位并仍然有索引？

Answer 1

实际上，您可以使用称为顺序统计树的修改二叉树来支持随机访问和时间 O(log n) 的移位。这是一个平衡二叉树(例如，即使元素未排序，它也是平衡的，就像红/黑树或 AVL 树一样)，其中每个节点存储其左子树和右子树中的节点数。使用改进的 BST 查找算法，可以在 O(log n) 时间内找到树中的第 k 个元素。一旦获得该节点，您就可以在 O(log n) 时间内删除它，或者在 O(log n) 时间内在其之前或之后插入一个节点。

许多介绍性算法教科书，例如 CLRS，详细描述了如何使这些操作发挥作用。

希望这有帮助!