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

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

← Вернуться к оглавлению
Глава 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
: 2
k
Максимум узлов в дереве высоты
h
: 2
h+1
− 1
Минимальная высота дерева из
n
узлов: ⌊log₂(n)⌋
Количество листьев в полном дереве: (n+1)/2
Интерактивные свойства деревьев
Макс. узлов на уровне k: 2
k
Подсветите уровень — увидите, сколько узлов на нём
Макс. узлов в дереве высоты h: 2
h+1
− 1
Задайте высоту — увидите, сколько узлов вмещает дерево
Уровень k:
0
→ 2
0
=
1
Высота h:
0
→ 2
1
−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 вопросов
0 / 500 XP
0/5