Существует ли структура данных, представляющая упорядоченный список с O (n * log n) временем основных операций?

Question

Я ищу структуру данных, которая позволяет решить конкретную проблему со сложностью O (n * log (n)).Он должен представлять набор целых чисел, в котором я могу выполнять следующие операции: - добавить элемент - проверить, существует ли элемент в наборе - удалить каждое значение больше указанного целого числа. Надеюсь, с логарифмической сложностью.

Я искал связанный список, поскольку добавить элемент посередине и удалить целую часть структуры легко, но я не знаю, как сохранить упорядоченный список или реализовать дихотомический поиск.Сначала я рассматривал хеш-таблицы, но я не знаю, как фильтровать набор.Я смотрю на сбалансированные бинарные деревья и не знаю, ищу ли я что-то бредовое или оно как-то существует, и я просто не могу его найти.

Answer 1

Для реализации с нуля, я бы предложил Treap .

Treap - это просто двоичное дерево поиска, где каждому узлу присваивается случайный приоритет, и оно удовлетворяет условию кучи в виде дерева. Эта рандомизированная структура данных делает ожидаемое время для поиска, вставки, удаления и разбиения дерева равным O(log(n)). Первые три довольно просты. Чтобы разделить, вы просто помещаете узел в точку разделения с более высоким приоритетом, чем корень. Затем одна половина оказывается на одной стороне этого узла, а другая половина - на другой.

Обратите внимание, что при разделении O(log(n)) освобождение удаленных битов O(n).

Обратите внимание, что вам, возможно, не нужно ничего реализовывать. Например, в C ++ вы можете просто использовать std::map. Выполнение этих операций, кроме удаления, составляет O(log(n)). При удалении диапазона длины m из структуры размером n это O(m + log(n)). Если учесть комментарий об освобождении памяти, это о идеале.