M-way деревья появляются на многих аренах.Вот небольшая выборка:
- B-деревья: это поисковые деревья, похожие на двоичное дерево поиска с огромным коэффициентом ветвления.Они спроектированы таким образом, что каждый узел может уместиться только внутри памяти, которую можно прочитать с жесткого диска за один проход.Все они имеют такие же гарантии asymPtotic для обычных BST, но предназначены для минимизации числа узлов, в которых выполняется поиск, чтобы найти конкретный элемент.Следовательно, многие гигантские системы баз данных используют B-деревья или другие связанные структуры для хранения больших таблиц на дисках.Таким образом, количество дорогостоящих операций чтения с диска сводится к минимуму, а общая эффективность намного выше.
- Octrees.Октри и их двухмерные двоюродные братья - структуры данных для хранения точек в трехмерном пространстве.Они широко используются в видеоиграх для быстрого обнаружения столкновений и вычислений рендеринга в реальном времени, и мы были бы намного хуже, если бы не они.
- Связывание / вырезание деревьев.Эти специализированные деревья используются в задачах сетевого потока для эффективного вычисления совпадений или нахождения максимальных потоков гораздо быстрее, чем обычные подходы, что имеет огромную применимость в исследовании операций.
- Лес с непересекающимися множествами.Эти многолучевые деревья используются в алгоритмах минимального связующего дерева для невероятно быстрого вычисления связности, оптимизируя время выполнения до теоретического предела.
- Пытается.Эти деревья используются для кодирования строковых данных и обеспечивают чрезвычайно быстрый поиск, хранение и обслуживание наборов строк.Они также используются в некоторых средствах регулярного выражения.
- Деревья Ван Эмде - молниеносная реализация приоритетных очередей целых чисел, подкрепленная лесом деревьев с огромным коэффициентом ветвления.
- Суффикс деревья.Эти драгоценности мира обработки текста позволяют осуществлять быстрый поиск строк.Они также обычно имеют коэффициент ветвления, намного превышающий два.
- PQ-деревья.Эти деревья для перестановок кодирования позволяют проводить тестирование на плоскостность в линейном времени, что имеет применение в схемах и схемах.
Фу!Это много деревьев.Надеюсь, это поможет!