Деревья и их свойства

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 22 · страница 22.1
Деревья и их свойства
BST, обходы, куча. BST-конструктор.
Дерево
— связный граф без циклов. Главное свойство: между любыми двумя вершинами ровно один путь. На деревьях построены BST (поиск), heap (приоритетная очередь), куча (heap sort), файловые системы.
ФГОС
ФОП
ЕГЭ №12,23
01
Бинарное дерево поиска (BST)
В BST для каждого узла: все ключи в левом поддереве < меньше, в правом — больше. Это позволяет находить элемент за O(h), где h — высота.
Для сбалансированного BST h ≈ log₂N, поиск O(log N). Для вырожденного (как список) h = N, поиск O(N).
02
3 обхода дерева
🔼
Preorder
Корень → Левый → Правый
Используется для копирования/сериализации дерева.
↔
Inorder
Левый → Корень → Правый
Для BST даёт отсортированный порядок!
🔽
Postorder
Левый → Правый → Корень
Используется для удаления дерева (сначала дети).
03
BST-конструктор
Введи числа — увидишь BST и обходы
🌳
BST-конструктор
Числа (через запятую)