Является ли красно-черным деревом идеальная структура данных?

У меня есть набор элементов (больших рациональностей), которые я буду обрабатывать. В каждом случае обработка будет состоять из удаления самого маленького элемента в коллекции, выполнения некоторой работы, а затем добавления 0-2 новых элементов (которые всегда будут больше, чем удаленный элемент). Коллекция будет инициализирована одним элементом, и работа будет продолжаться до тех пор, пока она не станет пустой. Я не уверен, какой размер собирает коллекция, но я ожидал бы в диапазоне 1M-100M элементов. Мне не нужно искать какой-либо предмет, отличный от самого маленького.

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

1) Есть ли опасность, что шаблон удаления из левой + случайной вставки повлияет на производительность, например, если требуется значительно большее число оборотов, чем случайное удаление? Или удалять и вставлять операции по-прежнему O (log n) с использованием этого шаблона?

2) Может ли какая-нибудь другая структура данных повысить производительность, либо из-за шаблона удаления, либо с учетом того факта, что мне когда-либо нужно найти наименьший элемент?

Обновить: рад, что я спросил, двоичная куча, безусловно, является лучшим решением для этого случая, и, как было обещано, было очень легко реализовать.

Уго

Ответ 1

A двоичная куча намного лучше того, что вы хотите. Его проще реализовать и быстрее, поскольку вам нужно только найти самый маленький элемент и вставки. Поиск наименьшего элемента - O (1), удаление которого - O (log N), а также вставка O (log N).

Ответ 2

Куча даст вам ~~O (1)~~ O (log n) удаление и O (log n), и намного проще реализовать, чем красно-черное дерево

Ответ 3

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

Единственный раз, когда я когда-либо реализовывал дерево с балансировкой, был один раз, когда мне стало известно, что мое дерево будет действительно большим (более 10 000 элементов), и данные собираются в отсортированных всплесках. Это означало, что если бы я использовал обычное двоичное дерево, я бы получил почти связанный список.

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