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

Question

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

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

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

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

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

Hugo

Answer 1

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

Answer 2

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

Answer 3

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

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

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