Как я определяю который вид древовидной структуры данных выбрать?
Вы не можете возможно знать все значения по умолчанию для всех конфигураций всех браузеров в будущее.
способ, которым люди обходят это, состоит в том, чтобы запустить их CSS путем сброса всего к известным значениям. Вот пример от одного из основных экспертов по CSS: http://meyerweb.com/eric/thoughts/2007/05/01/reset-reloaded/
5 ответов
Давайте выберем их по одному, не так ли?
- Несбалансированные двоичные деревья
Для поисковых задач - никогда. По сути, их характеристики производительности будут совершенно непредсказуемыми, а накладные расходы на балансировку дерева не будут такими большими, чтобы сделать несбалансированные деревья жизнеспособной альтернативой.
Кроме того, несбалансированные двоичные деревья, конечно, имеют и другие применения, но не как деревья поиска.
- AVL-деревья
Их легко разработать, но их производительность обычно превосходит другие стратегии балансировки, потому что их балансировка является сравнительно трудоемкой. Википедия утверждает , что они лучше работают в сценариях с интенсивным поиском, поскольку их высота немного меньше в худшем случае.
- Красно-черные деревья
Они используются в большинстве C ++ » std :: map и, возможно, в некоторых других стандартных библиотеках. Однако есть убедительные доказательства того, что они на самом деле хуже, чем деревья B (+) в каждом сценарии, из-за поведения кэширования современных процессоров. Исторически, когда кэширование не было таким важным (или таким хорошим), они превосходили B-деревья при использовании в основной памяти.
- 2-3 дерева
- B-деревья
- B * -деревья
Для этого требуются самое тщательное рассмотрение всех деревьев, поскольку различные используемые константы в основном являются «волшебными» константами, которые странным, а иногда и непредсказуемым образом связаны с базовой архитектурой оборудования. Например, оптимальное количество дочерних узлов на уровне может зависеть от размера страницы памяти или строки кэша.
Я не знаю хорошего общего правила, чтобы различать их.
- Попытки
Совершенно разные. Попытки также являются деревьями поиска, но для текстового поиска подстрок в корпусе. Trie - это несжатое префиксное дерево (т. Е. Дерево, в котором пути от корневых к конечным узлам соответствуют всем префиксам данной строки).
Попытки должны сравниваться и смещаться относительно суффиксных деревьев , массивы суффиксов и индексы q-граммы - не столько по сравнению с другими деревьями поиска, потому что данные , которые они ищут, отличаются: вместо отдельных слов в а корпус, последние структуры индекса позволяют выполнять поиск по факторам .
- Кучи
Как вы уже сказали, они вообще не являются деревьями поиска.
Как и любая другая структура данных, вы должны знать характеристики (сложность операций поиска, вставки и удаления) каждого типа дерева, а также требования к выполняемой вами работе. выбор инструмента для. Дерево, которое имеет наилучшую производительность для того типа операций, которые вы будете выполнять чаще всего, обычно является лучшим инструментом для этой работы.
Обычно вы можете найти общие характеристики для любого типа структуры данных в Википедии. Введение в алгоритмы также имеет по крайней мере раздел (в некоторых случаях целую главу) по большинству перечисленных вами структур данных, так что это еще один хороший справочник.
Каждый из них имеет разную сложность для вставки, удаления и извлечения. У всех в основном время доступа O log (n).
Каждое дерево имеет определенные характеристики, которые делают их полезными определенным образом. Вы должны сравнить эти характеристики с вашими потребностями.
Аналогичный вопрос: Когда выбрать дерево RB, B-дерево или дерево AVL?
Я бы сказал, что вначале напишите самый простой код, который мог бы работать (используя данные из библиотеки конструкции, если возможно). Затем измерьте его проблемы с производительностью, если таковые имеются.
Если ваши потребности в производительности действительно чрезвычайно высоки, прочтите замечательный ответ Конрада Рудольфа. :)