Блог

Для следующей структуры данных:

• добавьте элемент в O(lg(n))
• удалить элемент в O(lg(n))
• найдите k-й элемент в O(lg(n))

мы можем использовать сбалансированный по британскому летнему времени в котором каждый узел имеет размер этого поддерева, но он должен реализовать красно-черное дерево, которое не быстро код.

есть ли лучшее решение?

Общий тип структуры, которую вы ищете, определяется как Indexed или Indexable , то есть структура, дополненная count, чтобы иметь возможность доступа к элементам по индексам.

Вы могли бы использовать либо:

• Индексированное дерево: бинарное дерево поиска (красно-черное дерево, AVL-дерево), B-дерево, пальцевое дерево, …
• Индексированный список пропусков

(и, возможно, несколько других: p)

Я склонен думать, что списки с пропусками легче реализовать, чем по британскому летнему времени, как вы можете использовать рандомизированных высоту вместо того, чтобы все вещи балансировки.

Обычный способ — реализовать собственную расширенную структуру данных O (log (n)), которая позволяет вставлять / искать на основе рангов. Сбалансированный по британскому летнему времени, список пропускать или несколько модифицированных дерево отрезков или дерева Фенвика должен работать.

В Java вы также можете использовать TreeList из Apache Commons.

Если k фиксировано и вы используете C , вы можете использовать хитрый трюк, который вы можете найти в TopCoder (прокрутите вниз до раздела под названием «Плавающая медиана»). В основном вы используете 2 std::multiset s, один для первых k элементов, а другой для последних N-k элементов. Каждый раз, когда вы что-то добавляете / удаляете, вы соответствующим образом обновляете мультимножества. Получение k-го элемента — это просто поиск последнего элемента в первом мультимножестве.

Похоже, что деревья AA проще реализовать, чем RBT, но в остальном они в значительной степени эквивалентны им.

Вы могли бы попробовать пропустить списки с рандомизированной высотой узла. Он должен быть в состоянии делать то, что вы хотите.

Это рандомизированная структура данных. Поскольку идея очень чистая, ее относительно легко реализовать. Красно-черные попытки имеют много особых случаев. Списки пропусков не имеют особых случаев, и их легко исправить. Кроме того, они ведут себя очень хорошо на практике — константа в O() довольно мала.