Массив с быстрой вставкой/удалением

Я ищу структуру данных, которая хранит массив элементов и поддерживает следующие операции:

  • Доступ к элементу по заданному индексу
  • Добавление или удаление элемента по заданному индексу (и, следовательно, смещение следующих элементов)

Массивы выполняют первую операцию в O (1), а вторую берут O (n), а связанные списки - наоборот. Существует ли структура данных с промежуточными данными? Скажем, что-то, что может делать обе операции в O (lg n) или O (n ^ epsilon) "наихудшее" время?

Обратите внимание, что я не прошу сбалансированное двоичное дерево поиска. Здесь ключи (индексы) меняются и сдвигаются каждый раз, когда новый элемент добавляется/удаляется. Например, удаление наименьшего элемента уменьшает индексы для всех остальных элементов на 1.

Ответы

Ответ 1

Существует "AVL-Array", контейнер типа STL, который выполняет обе операции в O (log n).

Он построен поверх AVL-дерева, но он все еще не ассоциативный контейнер, но последовательный.
Он поддерживает индексный доступ [] с семантикой vector.

Обратите внимание, что AVL-Array не реализует дерево поиск, а скорее последовательный контейнер, который происходит в виде дерева. Индексирование, итерация, вставка и удаление все делают то, что вы хотели бы ожидать a vector.

Вы можете найти здесь

Ответ 2

Вы можете сделать это с помощью своего рода сбалансированного двоичного дерева, в обходном порядке которого приводятся элементы массива по порядку, т.е. самый левый node хранит A[0], а самый правый node хранит A[n-1], где n - количество элементов в массиве.

В каждом node мы сохраним общий размер s поддерева, внедренного в этот node (т.е. общее число узлов), значение v элемента массива, сохраненного в этом node, левый дочерний элемент l node и правый дочерний элемент r node.

Вы можете получить значение A[i] из такого дерева следующим образом (для простоты изложения не проверяются условия ошибки):

int get_element(node *n, int i) {
  int ls = (n->l == NULL) ? 0 : (n->l)->s;

  if (i < ls) return get_element(n->l, i);
  else if (i == s) return n->v;
  else return get_element(n->r, i-(ls+1));
}

Если дерево сбалансировано, это займет время O(log n). Вставка в индекс или удаление по индексу аналогична любой сбалансированной схеме дерева, за исключением того, что вы используете размеры поддерева для навигации, а не ключевое значение, которое также примет значение O(log n). Сбалансированные структуры данных дерева обычно используют "поворот" для восстановления баланса, например, поворот вправо:

   y o                  o x  
    / \                / \   
 x o   C     ==>      A   o y
  / \                    / \ 
 A   B                  B   C

Мы можем поддерживать размер нового поддерева в node y как size(B)+size(C)+1, а затем размер x как size(A)+size(y)+1.

Если вы используете идеи из дерева поиска пальцев, вы также сможете выполнить итерацию по всему массиву в O(n), пропустить последовательность длины k в O(k) и пропустить вперед или назад из A[i] до A[i+k] или A[i-k] в O(log k).

Ответ 3

Вы можете попробовать использовать IgushArray (https://github.com/igushev/IgushArray), который подобен обычному массиву с O (1) постоянным временем доступа, но операция вставки/удаления занимает только O (N ^ 1/2). Структура приносит большую пользу, если вы правильно используете reserver().