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

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

 1. Нечто, действительно имеющее древовидную форму — например, деревья каталогов на дисках, деревья сцен в 3D, деревья принятия решений.  

2. Деревья поиска — структуры данных, позволяющие добавлять-убирать объекты и позволяющие быстрый поиск по ключу. Например, словари всякие, индексы БД.  

3. Так называемая куча — структура данных, позволяющая добавлять-убирать объекты и поддерживающая минимальный элемент в этом множестве. Используется как вспомогательная в каких-нибудь алгоритмах.  

4. Двоичное разбиение пространства в 3D — известный способ сортировки от дальних к ближним.  

  

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

 Деревья везде:)  

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

  

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

  

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

  

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

  

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

  

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

  

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

  

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

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

  

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

  

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

  

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

  

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

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

  

Так же есть алгоритм [Nested Sets](https://devacademy.ru/article/nested-set) для хранения древовидных структур в базе данных, например категории чего-либо