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

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

← Вернуться к оглавлению
Alterna · глава 25 · страница 25.1
Деревья и их свойства
Дерево — связный граф без циклов. На нём построены BST, кучи, файловые системы, организационные иерархии.
Дерево
— связный граф без циклов. Главное свойство: между любыми двумя вершинами существует ровно один путь. Деревья лежат в основе BST, куч, файловых систем, XML и DOM.
ФГОС
ФОП
ЕГЭ №12
01
Основные свойства
V, E, корень, высота, глубина
В дереве с
V
вершинами ровно
E = V − 1
рёбер.
Корень
— выделенная вершина. У дерева обычно есть один корень, остальные — потомки.
Высота
— длина самого длинного пути от корня до листа.
Глубина вершины
— расстояние от корня до этой вершины.
Лист
— вершина без потомков.
Узел
— вершина с хотя бы одним потомком.
02
Бинарное дерево
У каждого узла не более двух детей
В
бинарном дереве
каждый узел имеет не более двух детей:
левого
и
правого
.
Количество узлов в полном бинарном дереве высоты h:
N(h) = 2
h+1
− 1
Пример: при h=3 → N = 2⁴ − 1 = 15 узлов.
Двоичное дерево поиска (BST)
В
BST
для каждого узла выполняется правило: все ключи в левом поддереве меньше, в правом — больше. Это позволяет находить элемент за O(h), где h — высота.
Если дерево сбалансировано, h ≈ log₂N, и поиск работает за O(log N). Если вырождено (как список), то за O(N).
Куча (heap)
Куча
— почти полное бинарное дерево, в котором значение в каждом узле ≤ (min-куча) или ≥ (max-куча) значений его потомков. Используется в пирамидальной сортировке и приоритетной очереди.
BFS и DFS на деревьях
Обход в ширину (BFS)
— посещаем все узлы уровня level L перед level L+1. Использует очередь. Применяется для поиска кратчайшего пути в дереве, печати уровень-за-уровнем.
Обход в глубину (DFS)
— идём как можно глубже по одной ветке, потом возвращаемся. Три варианта: pre-order (корень→лево→право), in-order (лево→корень→право), post-order (лево→право→корень). Использует стек (или рекурсию).
BFS (уровнями)
5 → 3, 7 → 1, 4, 6, 8
DFS Preorder
5, 3, 1, 4, 7, 6, 8
DFS Inorder
1, 3, 4, 5, 6, 7, 8
DFS Postorder
1, 4, 3, 6, 8, 7, 5
03
Обходы дерева
3 классических способа обойти бинарное дерево
Прямой (preorder)
Корень → Левый → Правый
К, Л, П
Симметричный (inorder)
Левый → Корень → Правый
Л, К, П
Обратный (postorder)
Левый → Правый → Корень
Л, П, К
Пример: BST с ключами 5, 3, 7, 1, 4, 6, 8
5
3
7
1
4
6
8
①
②
③
④
⑤
⑥
⑦
Preorder (КЛП):
①→②→③→④→⑤→⑥→⑦ →
5, 3, 1, 4, 7, 6, 8
Inorder (ЛКП):
③→②→④→①→⑥→⑤→⑦ →
1, 3, 4, 5, 6, 7, 8
Отсортированный! ✓
Postorder (ЛПК):
③→④→②→⑥→⑦→⑤→① →
1, 4, 3, 6, 8, 7, 5
Как читать дерево:
Левый потомок < красный < правый потомок.
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst_insert(root, key):
if root is None: return BSTNode(key)
if key < root.key: root.left = bst_insert(root.left, key)
else: root.right = bst_insert(root.right, key)
return root
def bst_search(root, key):
while root:
if key == root.key: return root
root = root.left if key < root.key else root.right
return None
def bst_inorder(root, res=[]):
if root:
bst_inorder(root.left, res)
res.append(root.key)
bst_inorder(root.right, res)
# Сборка дерева:
root = None
for k in [5, 3, 7, 1, 4, 6, 8]:
root = bst_insert(root, k)
seq = []; bst_inorder(root, seq)
print(seq) # [1, 3, 4, 5, 6, 7, 8]
🌲
BST: вставка и обходы
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Быстрый тест по теме
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.