list - 快速功能顺序收集

Question

我正在寻找一个顺序收集数据结构（即可以被视为列表的东西），其中：

1. 基本的拼接操作（在列表中的任何位置添加或删除元素）是摊销 O(log N) 或更好的（因此数组不符合条件，因为它只是在末尾添加或删除元素很快）。

2. 即使在功能上使用也是如此，即操作是非破坏性的（因此双向链表不符合条件，因为对于非破坏性操作，您必须复制整个列表；据我所知，绳索也是如此）。

是否有符合这些标准的数据结构？

Answer 1

是的，你想要一个平衡的二叉树。它们具有纯粹的功能性，不仅适用于排序的地图，也适用于序列。

所需的适应是将序列索引映射到值。为了避免对中间序列操作进行昂贵的重新编号，不要直接表示键；相反，让每个节点存储其左子树中的节点总数。在向下遍历期间，只要遍历正确，就通过添加计数来维护当前节点的索引。