Структуры данных
Деревья: Иерархия повсюду
Цели урока
- Понять что такое дерево и где оно встречается
- Выучить терминологию: root, leaf, height, depth
- Разобраться с бинарными деревьями
- Реализовать узел дерева
Предварительные знания
- Связные списки
Откройте проводник Windows или Finder на Mac. Папки внутри папок - это дерево! Теперь представьте, что вам нужно найти файл среди миллиона. Структура дерева делает это возможным.
- Файловые системы - папки и файлы
- HTML DOM - структура веб-страниц
- Базы данных - B-деревья для индексов
- Компиляторы - AST (абстрактное синтаксическое дерево)
Откуда взялись деревья и их термины
Слова, которыми мы описываем деревья (корень, родитель, ребёнок, лист, предок, потомок), пришли из генеалогии и схем иерархий: люди веками рисовали родословные именно так. В вычислениях древовидные структуры появились рано: парсеры выражений строили деревья разбора, а Стивен Клини в 1950-х использовал деревья при работе с регулярными событиями и автоматами. Строгую формализацию дал Дональд Кнут в первом томе The Art of Computer Programming в 1968 году, где он аккуратно различил упорядоченные и неупорядоченные деревья, а также корневые (rooted) деревья с выделенным корнем и свободные (free) деревья без него. Именно язык Кнута, где поддерево само является деревом, лежит в основе рекурсивного определения, которое мы используем в этом уроке.
Деревья вокруг нас
**Дерево** - это иерархическая структура с одним корнем и ветвями к потомкам.
- Файловая система - папки и файлы
- HTML DOM - теги вложены друг в друга
- Оргструктура - CEO → директора → менеджеры → сотрудники
- Генеалогическое древо - предки и потомки
В отличие от графа, в дереве **нет циклов** - путь от корня к любому узлу единственный.
Что НЕ является примером дерева?
Терминология: Root, Leaf, Height
- **Root (корень)** - верхний узел, не имеет родителя
- **Leaf (лист)** - узел без детей
- **Internal node** - узел с хотя бы одним ребёнком
- **Parent/Child** - родитель и ребёнок
- **Siblings** - дети одного родителя
- **Depth (глубина)** - расстояние от корня (root depth = 0)
- **Height (высота)** - максимальная глубина в дереве
Дерево: root → [A, B], A → [C, D, E], B → [F]. Какова высота дерева?
Бинарное дерево
**Бинарное дерево** - каждый узел имеет **максимум 2 ребёнка**: левого и правого.
**Типы бинарных деревьев:**
- **Full** - каждый узел имеет 0 или 2 детей
- **Complete** - все уровни заполнены, последний - слева направо
- **Perfect** - все листья на одной глубине, все внутренние имеют 2 детей
- **Balanced** - высота левого и правого поддерева отличается не более чем на 1
Бинарное дерево - это дерево где:
Реализация узла дерева
**Рекурсивная структура:** дерево состоит из корня + левое поддерево + правое поддерево. Каждое поддерево - тоже дерево!
Как проверить, что узел является листом?
Свойства бинарных деревьев
Полезные формулы для бинарных деревьев:
- **Максимум узлов на уровне k:** 2^k
- **Максимум узлов в дереве высоты h:** 2^(h+1) - 1
- **Минимальная высота для n узлов:** floor(log2(n))
| Высота | Max узлов | Пример |
|---|---|---|
| 0 | 1 | Только root |
| 1 | 3 | Root + 2 детей |
| 2 | 7 | 3 уровня |
| 3 | 15 | 4 уровня |
| 10 | 2047 | ~2K узлов |
Сколько максимум узлов в perfect binary tree высоты 4?
Ключевые понятия
- Дерево = иерархия без циклов
- Root - корень, Leaf - лист, Height - высота
- Бинарное дерево: максимум 2 ребёнка
- Узел: val + left + right
- Деревья рекурсивны: поддерево - тоже дерево
Дальше
Как обойти все узлы дерева? Три классических способа (inorder, preorder, postorder) - в следующем уроке!
- Обходы деревьев — Как посетить все узлы
- Binary Search Tree — Дерево для быстрого поиска
Связанные уроки
- ds-02-linked-lists — Trees generalise linked lists to multiple children
- ds-10-tree-traversals — Traversal algorithms operate on tree structure introduced here
- ds-11-bst — BST adds ordering invariant on top of tree structure
- ds-16-graphs-intro — Trees are a special case of DAGs, which are special case of graphs
- comp-16-ast
- plt-26-ast