Дерево — что такое и где применяется?

Дерево — связный неориентированный граф, в котором отсутствуют циклы. Эквивалентные определения:

• Граф из $n$ вершин и $n-1$ ребра, который связен.
• Связный граф, между любыми двумя вершинами которого ровно один путь.

Специальное дерево — корневое: одна вершина выделена как корень, остальные образуют ориентированную иерархию (потомки/предки).

Двоичное дерево (binary tree): каждый узел имеет максимум двух потомков (левого и правого).

Где применяются:

1. Файловая система — папки и файлы образуют дерево каталогов.
2. DOM в браузере — HTML-страница это дерево элементов.
3. Двоичные деревья поиска (BST) — быстрый поиск ($O(\log n)$).
4. B-деревья — индексы в базах данных, файловые системы (NTFS).
5. Хаффман-дерево — алгоритм сжатия.
6. Синтаксические деревья — разбор кода компилятором.
7. AI / игры — дерево решений, минимакс.