← Вернуться к оглавлению
Глава 13 · Страница 4 из 6

Деревья и код Фано

Двоичные деревья — математическая основа неравномерного кодирования. Условие Фано гарантирует однозначное декодирование.

дерево узел лист Фано BST обход

1. Виды деревьев

В информатике дерево — это иерархическая структура данных, состоящая из узлов (вершин), соединённых рёбрами (связями). Верхний узел называется корнем, нижние — листьями.

Основные виды деревьев

  • Бинарное дерево — каждый узел имеет не более 2 потомков (левый и правый)
  • Полное бинарное дерево — все уровни заполнены полностью
  • Бинарное дерево поиска (BST) — левый потомок < родитель, правый > родитель
  • AVL-дерево — сбалансированное BST, разница высот поддеревьев ≤ 1
  • Дерево Хаффмана — оптимальное префиксное кодирование
  • Кодирующее дерево — листья = символы, рёбра = 0/1
Сравнение видов деревьев Бинарное 7 3 9 1 5 Полное бинарное 7 3 9 1 5 8 10 BST (поиск) 7 3 9 1 5 10 Кодирующее B A C D 0 1 0 1 1 Любые 2 потомка Все уровни полные Левый < корень < правый Листья = символы, рёбра = 0/1

2. Терминология деревьев

Основные понятия

  • Узел (node) — элемент дерева, хранящий данные и ссылки на потомков
  • Корень (root) — верхний узел дерева, не имеет родителя
  • Лист (leaf) — узел без потомков
  • Родитель (parent) — узел, имеющий потомков
  • Потомок (child) — узел, связанный с родительским
  • Братья (siblings) — узлы с общим родителем
  • Поддерево (subtree) — часть дерева с потомками узла

Уровни и глубина

  • Уровень (level) — расстояние от корня (корень = уровень 0)
  • Глубина (depth) — количество рёбер от корня до узла
  • Высота (height) — максимальная глубина в дереве
  • Ширина (width) — количество узлов на уровне
Анатомия бинарного дерева Уровень 0 Уровень 1 Уровень 2 Уровень 3 50 КОРЕНЬ 30 родитель 70 лист 20 родитель 40 лист 80 лист 10 лист 25 лист ← левый потомок корня правый потомок корня → ← братья (siblings) → братья (siblings) Высота = 3

Свойства бинарного дерева

  • Максимум узлов на уровне k: 2k
  • Максимум узлов в дереве высоты h: 2h+1 − 1
  • Минимальная высота дерева из n узлов: ⌊log₂(n)⌋
  • Количество листьев в полном дереве: (n+1)/2

Интерактивные свойства деревьев

Макс. узлов на уровне k: 2k

Подсветите уровень — увидите, сколько узлов на нём

Макс. узлов в дереве высоты h: 2h+1 − 1

Задайте высоту — увидите, сколько узлов вмещает дерево

3. Где используются деревья

Файловые системы

C:\ Users Windows doc.txt photo.jpg System32 иерархия папок и файлов

Директории и файлы организованы в иерархическое дерево. Корень — корневая папка (C:\), листья — файлы.

Пример: C:\Users\Documents\file.txt — путь от корня к листу.

Базы данных

[10|20|30] [5|8] [35|40] 5,6,7 8,9 20,25 31,33 38,39 41,50 B-дерево (ветвление = 3)

B-деревья и B+-деревья индексируют записи, обеспечивая поиск за O(log n). Каждый узел — страница индекса.

Пример: PostgreSQL использует B+-деревья для индексов.

Сжатие данных

A B C D 0 1 0 1 0 1 00 01 10 11 дерево Хаффмана

Дерево Хаффмана кодирует символы переменной длины: частые — короткими кодами, редкие — длинными.

Пример: ZIP, JPEG, MP3 используют Хаффман.

DOM (Document Object Model)

<html> <head> <body> <title> <div> <p> дерево HTML-документа

HTML-документ — дерево: <html> — корень, <body>, <head> — потомки, текст — листья.

Пример: document.querySelector() обходит DOM-дерево.

Искусственный интеллект

T < 30? T < 20? T < 35? холод тепло жарко оч.жарко да нет дерево решений (классификация)

Деревья решений, минимакс, альфа-бета отсечение — алгоритмы для игр и классификации.

Пример: Шахматный движок обходит дерево ходов.

Сетевые протоколы

A B C D E F петля! остовное дерево (STP)

Spanning Tree Protocol (STP) предотвращает петли в Ethernet-сетях, строя остовное дерево.

Пример: Коммутаторы используют STP для резервирования.

4. Интерактивное бинарное дерево поиска (BST)

В BST левый потомок всегда меньше родителя, правый — больше. Это обеспечивает быстрый поиск: O(log n) в сбалансированном дереве.

5. Анимация обхода дерева

Обход дерева — систематическое посещение всех узлов. Три основных способа:

In-order (симметричный)

← Слева направо

Левое поддерево → Корень → Правое поддерево

Применение: Получение отсортированного списка из BST

Pre-order (прямой)

↓ По контуру сверху вниз

Корень → Левое поддерево → Правое поддерево

Применение: Копирование дерева, сериализация

Post-order (обратный)

↑ Снизу вверх по контуру

Левое поддерево → Правое поддерево → Корень

Применение: Удаление дерева, вычисление размеров

6. Условие Фано

Прямое условие Фано

Ни один код не является началом другого кода. Это гарантирует однозначное декодирование без lookahead.

Пример: A=0, B=10, C=110 — выполняется (префиксный код)

Контрпример: A=0, B=01 — нарушается (0 — начало 01)

Обратное условие Фано

Ни один код не является концом другого кода. Также гарантирует однозначность при декодировании справа налево.

Пример: A=0, B=01, C=11 — выполняется (суффиксный код)

🔍
Проверка условия Фано

7. Кодирование и декодирование через дерево

📤
Кодировщик: буква → биты
📥
Декодировщик: биты → буква
📝
Банк заданий ОГЭ/ЕГЭ

Решите задачу. Выберите ответ или введите число.

08

Мини-тест

🎯Проверь себя: 5 вопросов