Закрепление материала: Деревья

Модуль "Деревья" • урок 10 из 11 • ~5 минут

Суть урока. В этом модуле мы изучили деревья - фундаментальную нелинейную структуру данных для работы с иерархиями. Мы рассмотрели математическую базу, логическое представление в виде двоичных узлов, алгоритмы рекурсивных обходов, методы оптимизации памяти (прошивка) и способы приведения любых лесов к строгому бинарному виду.

Карта модуля о деревьях: от определения дерева до деревьев общего вида и правила LCRS — Шесть тем модуля в том порядке, в котором они разбирались

Краткое резюме модуля

За прошедшие уроки мы разобрали главные аспекты работы с деревьями:

Функциональная спецификация - абстрактное определение дерева через корень, левое и правое поддеревья. Набор операций включает построение, проверку пустоты и доступ к сыновьям.
Логическая реализация - классическое представление двоичного дерева в памяти: каждый узел обязательно содержит два указателя (на левого и правого сына) и поле данных.
Обходы - три фундаментальных порядка посещения узлов: прямой (КЛП), симметричный (ЛКП) и обратный (ЛПК). В англоязычной литературе те же три обхода называют traversals и обозначают NLR, LNR и LRN.
Деревья общего вида - структуры с произвольным числом потомков, которые элегантно сводятся к бинарным деревьям с помощью правила LCRS.

Ключевые идеи

Рекурсивная природа: любое дерево состоит из корня и поддеревьев, которые сами по себе являются полноценными деревьями. Это делает рекурсию естественным инструментом для любых алгоритмов на деревьях.
Прошивка (Threading): техника замены неиспользуемых пустых указателей (NULL) у листьев на нити, указывающие на следующий или предыдущий узел при симметричном обходе. Это позволяет обходить дерево без использования дополнительной памяти (стека).
Схема LCRS (Левый сын - правый брат): универсальное правило, доказывающее выразительную полноту двоичных деревьев. Левый указатель ведет к старшему ребенку, а правый - к следующему родному брату.

Коротко: главное

Дерево - это связный граф без циклов с выделенным корнем.
В двоичном дереве каждый узел имеет строго не более двух детей.
Традиционный обход дерева в глубину требует O(H) дополнительной памяти для стека вызовов, где H - высота дерева.
Прошивка позволяет выполнять обходы за O(1) дополнительной памяти.
Любой лес деревьев общего вида можно однозначно отобразить в одно двоичное дерево.

Проверьте себя

Вопрос 1

В чем принципиальное отличие дерева от линейного списка?

Дерево всегда хранится в массиве, а список в динамической памяти. Список линеен (один элемент следует за другим), а в дереве пути разветвляются. Дерево не может содержать чисел, только строки.

Вопрос 2

Что содержит каждый узел двоичного дерева в классическом логическом представлении?

Только значение ключа. Массив указателей на всех возможных потомков. Значение (ключ) и два указателя - на левого и правого сына.

Вопрос 3

Какую основную проблему решает прошивка двоичного дерева?

Избавляет от необходимости использовать дополнительную память (O(H) на стек) при обходе дерева. Ускоряет поиск произвольного элемента в дереве в два раза. Сжимает данные узлов для экономии оперативной памяти.

Вопрос 4

Какое правило используется для представления дерева общего вида в виде двоичного?

Корень - Лист (Root-Leaf). Левый сын - правый брат (Left-Child, Right-Sibling). Правый сын - левый отец.

Вопрос 5

Какие существуют основные порядки обхода двоичного дерева?

Прямой, симметричный, обратный. Верхний, средний, нижний. Быстрый, медленный, случайный.

Вопрос 6

В чем разница между функциональной спецификацией и логическим описанием дерева?

Никакой разницы нет, это синонимы. Функциональная спецификация пишется на C++, а логическая - на Python. Функциональная спецификация определяет набор математических операций, а логическое описание задает представление в памяти (узлы и указатели).

Как вам урок? Спасибо за отзыв!