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