Что такое tree?
На этой странице
Tree - иерархическая структура данных из узлов и связей parent-child. У дерева есть root, листья, высота, глубина и поддеревья. На собеседованиях чаще всего встречаются binary tree, BST и обходы DFS/BFS.
Вопрос
Что такое tree и какие термины деревьев нужно знать?
Как выглядит дерево
Пример - структура папок или DOM-дерево:
A <- root, depth 0
/ \
B C <- depth 1; B и C - дети A, A - их parent
/ \ \
D E F <- depth 2; D, E, F - листья (leaf)- Поддерево с корнем
B- этоB, D, E. - Высота дерева - 2: самый длинный путь от корня до листа проходит 2 ребра (
A -> B -> D). - Глубина
E- 2, глубинаC- 1. - В дереве нет циклов, и до каждого узла ведет ровно один путь от корня.
Базовые термины
- Root - корневой узел.
- Parent - родитель.
- Child - потомок.
- Leaf - узел без детей.
- Edge - связь между узлами.
- Depth - расстояние от root.
- Height - максимальное расстояние до листа.
- Subtree - поддерево.
Binary tree
type TreeNode<T> = {
value: T
left: TreeNode<T> | null
right: TreeNode<T> | null
}У каждого узла максимум два ребенка.
Пример обхода
function sum(root: TreeNode<number> | null): number {
if (!root) return 0
return root.value + sum(root.left) + sum(root.right)
}Time O(n), потому что посещаем каждый узел.
Space O(h), где h - высота дерева: одновременно в call stack лежат вызовы только для одного пути от корня вниз.
Как разворачивается рекурсия для маленького дерева 1 с детьми 2 и 3:
sum(1) = 1 + sum(2) + sum(3)
sum(2) = 2 + sum(null) + sum(null) = 2 + 0 + 0 = 2
sum(3) = 3 + 0 + 0 = 3
sum(1) = 1 + 2 + 3 = 6Узел не знает сумму всего дерева - он просит детей посчитать свои поддеревья и складывает ответы. Так устроены почти все рекурсивные задачи на деревьях.
Что отвечать на собеседовании?
Tree - связная ациклическая иерархическая структура. В отличие от массива, данные организованы не линейно, а через parent-child отношения. Для binary tree каждый узел имеет максимум двух детей. Основные операции на интервью - обход, поиск глубины, проверка баланса, lowest common ancestor, работа с BST.
Что важно помнить: частые ошибки
- Путать depth и height.
- Забывать
root = null. - Не учитывать recursion stack.
- Считать все деревья balanced.
- Путать tree и graph.
Мини-шпаргалка
- Root - начало.
- Leaf - нет детей.
- Binary tree - left/right.
- Height важна для complexity.
- DFS часто рекурсивный.
- BFS идет по уровням.