在中间插入时保持集合排序的算法

Question

假设我有大量元素。
每个元素都有一个“位置”字段，它是一个正整数。
没有两个元素对于“位置”字段具有相同的值。

集合唯一支持的操作是:addElement(newElement, positionAfterElement)，其中:
- newElement 是要添加的新元素(目前位置未知)
- positionAfterElement 是集合中的现有元素。

该函数将保证:
-位置(元素后位置)<位置(新元素)
- 集合中没有其他元素位于 position(positionAfterElement) 和 position(newElement) 之间

我可以根据需要更改所有元素位置的值，但我想尽量减少更改次数(平均)。

如何实现addElement函数？

我可以将所有位置较高的元素都推 1，但我很确定必须有更好的方法来做到这一点。

感谢大家的帮助。

Answer 1

使用平衡树。在树的每个节点，记录其下方的项目数 (left.count + right.count + 1)。然后，您可以在遍历项目时轻松计算项目的索引。这是操作次数的 O(n log n) 时间。