Ключові терміни
- Корінь (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 (рівень за рівнем).