Практическое использование m-way tree
Я снова начал изучать структуры данных. Я нашел очень мало практического использования этого. Один из них был о файловой системе на диске. Может кто-нибудь дать мне больше примеров практического использования дерева m-way.
2 ответа
Решение
M-way деревья появляются на многих аренах. Вот небольшая выборка:
- B-деревья: это поисковые деревья, похожие на двоичное дерево поиска с огромным фактором ветвления. Они спроектированы таким образом, что каждый узел может уместиться только внутри памяти, которую можно прочитать с жесткого диска за один проход. Все они имеют такие же гарантии asymPtotic для обычных BST, но предназначены для минимизации числа узлов, в которых выполняется поиск, чтобы найти конкретный элемент. Следовательно, многие гигантские системы баз данных используют B-деревья или другие связанные структуры для хранения больших таблиц на дисках. Таким образом, количество дорогостоящих операций чтения с диска сводится к минимуму, а общая эффективность намного выше.
- Octrees. Октри и их двухмерные двоюродные братья - структуры данных для хранения точек в трехмерном пространстве. Они широко используются в видеоиграх для быстрого обнаружения столкновений и вычислений рендеринга в реальном времени, и мы были бы намного хуже, если бы не они.
- Ссылка / рубить деревья. Эти специализированные деревья используются в задачах сетевого потока для эффективного вычисления совпадений или нахождения максимальных потоков намного быстрее, чем традиционные подходы, что имеет огромную применимость в исследовании операций.
- Несвязно-множественные леса. Эти многолучевые деревья используются в алгоритмах минимального связующего дерева для невероятно быстрого вычисления связности, оптимизируя время выполнения до теоретического предела.
- Пытается. Эти деревья используются для кодирования строковых данных и обеспечивают чрезвычайно быстрый поиск, хранение и обслуживание наборов строк. Они также используются в некоторых регулярных выражениях.
- Van Emde Boas Trees - молниеносная реализация приоритетных очередей целых чисел, подкрепленная лесом деревьев с огромным фактором ветвления.
- Суффикс деревья. Эти драгоценности мира обработки текста позволяют осуществлять быстрый поиск строк. Они также обычно имеют коэффициент разветвления, намного превышающий два.
- PQ-деревья. Эти деревья для перестановок кодирования позволяют проводить тестирование на плоскостность в линейном времени, что имеет применение в компоновке схем и построении графиков.
Уф! Это много деревьев. Надеюсь это поможет!
Под m-way вы подразумеваете обобщенное дерево? Если так, то практически любая иерархия "с одним родителем".