Ключевые термины
- Корень (root) — единственный узел без родителя
- Лист (leaf) — узел без дочерних
- Высота — максимальная глубина от корня до листа
Типы деревьев
- Binary Tree — каждый узел имеет ≤ 2 дочерних
- BST (Binary Search Tree) — левый < узел < правый. Поиск O(log n)
- B-Tree — многопутевое, сбалансированное. Основа индексов MySQL/PostgreSQL
- Trie — строковое дерево для быстрого поиска по префиксу (автодополнение)
Обходы
Pre-order (корень → лево → право), In-order (лево → корень → право; даёт отсортированный BST), Post-order, BFS (уровень за уровнем).