Поиск и удаление за время (log n) с использованием массивов

Question

Предположим, нам изначально дан набор из n чисел. Нам нужно построить структуру данных, которая поддерживает запросы Search(), Predecessor() и Deletion().

Поиск и Предшественник должны занять наихудший случай O(обработка журнала n) время. Удаление должно занять амортизированное O(log n) время. Допустимое время - O(n). У нас изначально есть пространство O(n). Но я хочу, чтобы на любом этапе, если они были m числами в структуре, используемое пространство должно быть O(m)

Эту проблему можно решить тривиально, используя RBT, но я хочу структуру данных, которая использует только массив (ы). Я не хочу реализацию RBT с использованием массивов, структура данных не должна использовать алгоритмы, основанные на деревьях. Кто-нибудь может придумать одну такую ​​структуру данных?

Answer 1

Я могу предложить какую-то древовидную структуру, которая проще, чем RBT. Чтобы упростить его описание, пусть количество элементов в нем будет 2^k,

Первый уровень просто цифры. Второй уровень имеет 2^(k-1) числа, как в двоичном дереве. Следующий уровень имеет 2^(k-2) номера и так далее, пока у нас нет только одного номера. Итак, у нас есть двоичное дерево с 2^(k+1) узлы, а parent будет содержать максимум дочерних значений. Чтобы построить это дерево, мы будем O(N) время. Дерево будет потребительским O(n) пространство, потребитель первого уровня nвторой n/2, в третьих n/4... и так далее, так что общее пространство будет n + n/2 + n/4 + ... = 2n = O(n), Например, у нас будет следующее дерево для чисел 1,2,4,6,8,9,12,14:

 1  2  4  7  8  9 12  14 

   2    7     9     14 

      7          14

            14

Чтобы удалить элемент, нам нужно найти его с помощью бинарного поиска и пометить его как ноль в списке. Обновите дерево, если оба потомка NULL выставят NULL в узел. Это займет k операции (высота дерева) или O(log(N)). Например, мы удаляем 12.

 1  2  4  7  8  9 NULL(12)  14 

   2    7     9     14 

      7          14

            14

Теперь удалите 7.

 1  2  4  NUll(7)  8  9 NULL(12)  14 

   2    4            9     14 

      4                 14

            14

Теперь мы должны искать или предшественника в O(log(N)). Путем бинарного поиска найдите на первом уровне наш элемент или его предшественника. Если это не NULL, мы получаем ответ. Если NULL перейти на уровень выше, у нас есть три варианта:

1. Узел имеет значение NULL, перейдите на верхний уровень
2. Левый дочерний узел имеет значение не NULL. Это меньше, чем запрашиваемое число (из-за структуры дерева), и это ответ.
3. Значение узла больше, чем запрашиваемое число, иди наверх.