Деревья

Дерево — связный ациклический граф. В корневом дереве у каждого узла, кроме корня, один родитель.

Термины

• leaf — узел без детей;
• depth — число ребер от корня к узлу;
• height — максимальный путь вниз до листа;
• subtree — узел со всеми потомками;
• degree — число детей.

Основные структуры

• Бинарное дерево — не более двух детей;
• binary search tree — слева меньшие ключи, справа большие по выбранной политике равенства;
• Красно черное дерево — сбалансированное BST с высотой O(log n);
• heap — частичный порядок для быстрого min/max, но не BST;
• trie — путь кодирует префикс ключа.

Обходы

Обход	Порядок	Применение
preorder	node, left, right	копирование/сериализация формы
inorder	left, node, right	ключи BST по порядку
postorder	left, right, node	удаление/вычисление снизу
BFS	по уровням	кратчайший путь в невзвешенном дереве

Для n узлов полный обход занимает O(n), а память DFS — O(height). В вырожденном дереве height равна n, в сбалансированном — O(log n).

На собеседовании

• Чем дерево отличается от произвольного графа? Связно и не содержит циклов.
• Дает ли бинарное дерево O(log n) поиска? Нет, только сбалансированное BST.
• Как inorder обходит BST? В отсортированном порядке.
• Память рекурсивного DFS? O(height).