Где и как используют деревья в программировании?

Question

[Dyadko_Orest]

Привет! Начал изучать алгоритмы и структуры данных и сейчас прохожу деревья, но не могу найти четкого определение когда и где они используются. Можете скинуть полезные статьи или привести примеры? Спасибо!

Answer 1

[Mercury13]

1. Нечто, действительно имеющее древовидную форму — например, деревья каталогов на дисках, деревья сцен в 3D, деревья принятия решений.
2. Деревья поиска — структуры данных, позволяющие добавлять-убирать объекты и позволяющие быстрый поиск по ключу. Например, словари всякие, индексы БД.
3. Так называемая куча — структура данных, позволяющая добавлять-убирать объекты и поддерживающая минимальный элемент в этом множестве. Используется как вспомогательная в каких-нибудь алгоритмах.
4. Двоичное разбиение пространства в 3D — известный способ сортировки от дальних к ближним.

Кроме того, деревья могут не существовать в памяти, а только подразумеваться — в синтаксических разборах, теоретико-игровых обсчётах. Хотя один из вариантов промежуточного хранения разобранной формулы, чтобы потом по ней проводить многократные расчёты — дерево (но чаще используют обратную польскую запись).

Answer 2

[Денис Загаевский]

Деревья везде:)
Самый банальный пример - дерево поиска, BST, сбалансированное BST(например, красночерное дерево, rb-tree), используется для организации структур, хранящих пары ключ-значение(например имплементация SortedMap - TreeMap в Java).

Сильно ветвистые сбалансированные деревья (В-дерево), используются для реализации индексов в СУБД

Дерево решений в машинном обучении, используется для принятия решений. Развитие идеи - случайный лес, использование множества деревьев решений.

Хэш-дерево, или дерево Меркла - в блокчейнах для хранения транзакций.

Префиксное дерево - для хранения и поиска ключей-строк

Октодеревья, q-деревья в играх и графике для разбиения пространства на области.

Даже вьюхи в большинстве GUI фреймворков организуются в виде деревьев.

И это я ещё далеко не всё перечислил, 100%

Answer 3

[Wataru]

Само по себе тупо дерево весьма бесполезно. Но как базовая организация данных она встречается много где. Если на него навесить какие-то дополнительные свойства и поддерживать их, то получаются классные штуки.

Балансированные бинарные деревья поиска - очень популярная структура данных. Используется где угодно, если вам нужно хранить множество или ассоциативный массив чего-либо и менять произвольные элементы.

Еще деревья часто используются в алгоритмах на строки. Есть такая структура - бор (trie) - позволяет эффективно хранить кучу строк и искать: есть ли такая строка в структуре. Более продвинутые алгоритмы типа Ахо-Корасика, Укконена тоже строят некоторое дерево с дополнительными фишками и позволяют делать крутые вещи, типа искать кучу шаблонов в тексте разом, или моментально находить самую часто встречающуюся подстроку задонного размера.

Куча (heap) используется для сортировки а так же реализации приоритетных очередей.

Далее, деревья в смысле графов тоже используются, например, в сети. Маршрутизаторы строят остовное дерево и раздают команды по его ребрам.

Answer 4

[Ivan Shalganov]

Помимо того что уже сказали, есть еще такой вид деревьев как AST, используется для описания синтаксиса. Почти во всех языках программирования, шаблонизациях используется для компиляции и интерпретации кода.

Так же есть алгоритм Nested Sets для хранения древовидных структур в базе данных, например категории чего-либо