Действительно ли красно-черным является дерево моя идеальная структура данных?
У меня есть набор объектов (большой rationals), что я буду обрабатывать. В каждом случае обработка будет состоять из удаления самого маленького объекта в наборе, выполнение некоторой работы и затем добавление 0-2 новых объектов (который всегда будет больше, чем удаленный объект). Набор будет инициализирован с одним объектом, и работа продолжится, пока это не будет пусто. Я не уверен, какого размера набор, вероятно, достигнет, но я ожидал бы в диапазоне объекты 1M-100M. Я не должен буду определять местоположение никакого объекта кроме самого маленького.
Я в настоящее время планирую использовать красно-черное дерево, которое возможно настраивают для хранения указателя на самый маленький объект. Однако я никогда не использовал тот прежде, и я не уверен, соответствует ли мой шаблон использования своим характеристикам хорошо.
1) Существует ли опасность шаблон удаления слева +, случайная вставка будет влиять на производительность, например, путем требования значительно более высокого количества вращений, чем случайное удаление было бы? Или удалит и вставит операции все еще быть O (зарегистрируйте n) с этим шаблоном использования?
2) Некоторая другая структура данных дала бы мне лучшую производительность, или из-за шаблона удаления или из-за использования в своих интересах факта, я только когда-либо должен находить самый маленький объект?
Обновление: довольный я спросил, двоичная "куча" является ясно лучшим решением для этого случая и, как обещано оказалась очень легкой реализовать.
Hugo
3 ответа
Двоичная куча бинарная куча гораздо лучше подходит для того, что вы хотите. Она проще в реализации и быстрее, поскольку вы заботитесь только о нахождении наименьшего элемента и вставках. Нахождение наименьшего элемента - O(1), удаление - O(log N), а вставка - также O(log N).
Куча даст вам O (1) удаление O (log n) и вставку O (log n), и это намного проще реализовать, чем красно-черное дерево
При необходимости хорошо знать, как создавать более сложные структуры данных. Однако, как правило, лучше всего начать как можно проще и использовать что-то более сложное только тогда, когда окажется, что это необходимо.
Единственный раз, когда я реализовал самобалансирующееся дерево, однажды я случайно узнал, что мое дерево будет действительно большим (более 10 000 элементов), а данные будут поступать отсортированными скачками. Это означало, что если бы я использовал обычное двоичное дерево, у меня получился бы почти связанный список.
Если ваши данные вводятся в случайном порядке, вам действительно не следует беспокоиться об алгоритме балансировки.