Двоичное дерево. Функциональная спецификация

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

Суть урока. Функциональная спецификация двоичного дерева (как абстрактного типа данных) задает набор операций без привязки к конкретной реализации в памяти. Она определяет, что можно делать с деревом, абстрагируясь от указателей, массивов и сборщиков мусора.

Двоичное дерево. Функциональная спецификация: ПОСТРОИТЬ собирает дерево из двух поддеревьев и корня, а СЛЕВА, КОРЕНЬ и СПРАВА разбирают его обратно — Что собрал конструктор, то селекторы разбирают обратно без потерь

Двоичное дерево. Функциональная спецификация: семь операций

Двоичное дерево типа T (обозначим его BTT, от англ. Binary Tree Type) описывается семью базовыми функциями. Эти функции работают с целыми поддеревьями, а не с отдельными разрозненными узлами памяти.

СОЗДАТЬ: ∅ → BTT - возвращает новое пустое двоичное дерево.
ПОСТРОИТЬ: BTT × T × BTT → BTT - конструирует новое дерево из переданного корня (элемент типа T) и двух готовых поддеревьев (левого и правого).
ПУСТО: BTT → boolean - проверяет, является ли дерево пустым.
КОРЕНЬ: BTT → T - возвращает корневой элемент непустого дерева.
СЛЕВА: BTT → BTT - осуществляет доступ к левому поддереву.
СПРАВА: BTT → BTT - осуществляет доступ к правому поддереву.
УНИЧТОЖИТЬ: BTT → ∅ - разрушает дерево (уничтожение структуры).

Историческая справка. Функциональные спецификации структур данных (Абстрактные Типы Данных, ADT) получили строгое математическое обоснование в 1970-х годах, во многом благодаря работам Барбары Лисков (создательницы языка CLU) и Джона Гуттага. Их подход позволил отделить логику структуры от физических ограничений "фон-неймановской" архитектуры памяти ЭВМ.

Аксиомы (свойства операций)

Чтобы спецификация была полной, необходимо задать правила, по которым эти функции взаимодействуют друг с другом. Эти правила называются аксиомами.

ПУСТО(СОЗДАТЬ) = true
Вновь созданное базовое дерево всегда пусто.
ПУСТО(ПОСТРОИТЬ(btl, t, btr)) = false
Дерево, собранное вокруг корня t, не может быть пустым.
КОРЕНЬ(ПОСТРОИТЬ(btl, t, btr)) = t
Корень построенного дерева - это элемент t.
СЛЕВА(ПОСТРОИТЬ(btl, t, btr)) = btl
Левое поддерево построенного дерева - это переданное дерево btl.
СПРАВА(ПОСТРОИТЬ(btl, t, btr)) = btr
Правое поддерево построенного дерева - это переданное дерево btr.
ПОСТРОИТЬ(СЛЕВА(bt), КОРЕНЬ(bt), СПРАВА(bt)) = bt
Любое непустое дерево bt можно разобрать на корень и поддеревья, а затем собрать обратно, получив в точности исходное дерево.

В реальных языках программирования к этому базовому набору добавляют и другие высокоуровневые операции: присоединение к узлу нового поддерева, замена поддерева, поиск узла по ключу и удаление поддерева. Однако все они могут быть теоретически выражены через комбинацию базовых функций.

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

Функциональная спецификация описывает дерево как абстрактный тип данных (ADT), независимо от реализации в памяти.
Доступ к элементам и поддеревьям осуществляется через строгий набор базовых операций (КОРЕНЬ, СЛЕВА, СПРАВА).
Аксиомы задают математические правила взаимодействия абстрактных операций.
Любое непустое дерево можно разобрать на корень и два поддерева, а затем собрать обратно в идентичную структуру.
Более сложные операции (поиск, вставка) строятся на основе базового функционального набора.

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

Какой тип данных возвращает абстрактная функция СЛЕВА(bt)?

Элемент типа T (данные) Двоичное дерево типа T (BTT) Указатель на структуру node Логическое значение (boolean)

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