Хорошо, так что это всегда меня беспокоило. Структуры древовидных данных, о которых я знаю, являются:
Как определить, какое дерево является лучшим инструментом для работы? Очевидно, что кучи канонически используются для формирования очередей приоритетов. Но остальным из них просто кажется, что это разные способы сделать то же самое. Есть ли способ выбрать лучший для работы?
Давайте отбираем их один за другим, будем ли мы?
- Несбалансированные бинарные деревья
Для задач поиска никогда. В принципе, их характеристики производительности будут совершенно непредсказуемыми, а накладные расходы на балансировку дерева не будут настолько большими, чтобы сделать несбалансированные деревья жизнеспособной альтернативой.
Кроме того, несбалансированные бинарные деревья, конечно, имеют другие применения, но не как деревья поиска.
- Деревья AVL
Их легко развить, но их производительность, как правило, превзойдена другими стратегиями балансировки, потому что их балансировка сравнительно длительна. Wikipedia утверждает, что они лучше работают в сценариях с интенсивным поиском, потому что их высота немного меньше в худшем случае.
- Красно-черные деревья
Они используются в большинстве реализаций С++ std::map и, возможно, в нескольких других стандартных библиотеках. Тем не менее, theres хорошие доказательства, что они на самом деле хуже, чем B (+) деревьев в каждом сценарии из-за кэширования поведения современных процессоров. Исторически, когда кеширование не было таким важным (или хорошим), они превзошли деревья B, когда они использовались в основной памяти.
- 2-3 дерева
- B-деревья
- B * -деревьях
Для этого требуется самое тщательное рассмотрение всех деревьев, так как различные используемые константы - это в основном "магические" константы, которые относятся к странным и иногда непредсказуемым образом к базовой аппаратной архитектуре. Например, оптимальное количество дочерних узлов на уровне может зависеть от размера страницы памяти или строки кэша.
Я не знаю хорошего и общего правила, чтобы отличать их.
- Пытается
Совершенно иная. Tries также являются поисковыми деревьями, но для текстового поиска подстрок в корпусе. Три - это несжатое дерево префикса (т.е. Дерево, в котором пути от корневых до листовых узлов соответствуют всем префиксам заданной строки).
Tries следует сравнивать с деревьями суффиксов, суффиксными массивами и индексами q-грамм, а также компенсировать их, а не против других деревьев поиска, поскольку данные, которые они ищут, различны: вместо дискретных слов в корпусе последний структуры индексов позволяют искать коэффициент.
- Кучи
Как вы уже сказали, они вовсе не являются деревьями поиска.
Как и любая другая структура данных, вы должны знать характеристики (сложность операций поиска, вставки и удаления) каждого типа дерева и требования задания, для которого вы выбираете инструмент. Дерево, которое имеет лучшую производительность для типов операций, которые вы будете делать чаще всего, обычно является лучшим инструментом для работы.
Обычно вы можете найти общие характеристики для любой структуры данных в Википедии. Введение в алгоритмы также содержит как минимум раздел (в некоторых случаях целую главу) для большинства структур данных, которые вы указали, поэтому еще одна хорошая рекомендация.
Аналогичный вопрос: Когда выбрать дерево RB, дерево B-Tree или AVL?
Оффлайн, я бы сказал, написал простейший код, который мог бы работать (воспользовавшись предоставленными библиотекой структурами данных, если это возможно). Затем измерьте его проблемы с производительностью, если они есть.
Если ваши потребности в производительности действительно экстремальны, прочитайте Конрад Рудольф, удивительный ответ.:)
Каждый из них имеет различную сложность для вставки, удаления и извлечения, все имеют в основном время доступа O log (n).
Каждое дерево имеет определенные характеристики, которые делают их полезными определенным образом. Вы должны сравнить характеристики с потребностями, которые у вас есть.