🗊Презентация Динамические структуры данных (язык Си). Тема 6. Деревья

Динамические структуры данных Деревья

Двоичные деревья Многие полезные структуры данных основаны на двоичном дереве: Двоичное дерево поиска Двоичная куча АВЛ-дерево Красно-чёрное дерево Матричное дерево Дерево Фибоначчи Суффиксное дерево

Несбалансированные двоичные деревья поиска (unbalanced) Это такие деревья, высота правого и левого поддеревьев которых отличаются более, чем на 1. Дерево двоичного поиска становится несбалансированным, когда в него постоянно добавляются элементы большего или меньшего размера

Неполные двоичные деревья поиска (incomplete) Каждый узел дерева двоичного поиска должен содержать не более 2 детей. Но он может иметь 1 ребенка или не иметь детей. Если в дереве есть такие хотя бы один такой узел, дерево называют неполным.

Основные операции в двоичном дереве поиска Базовый интерфейс двоичного дерева поиска состоит из трех операций: Поиск узла, в котором хранится пара (key, value) с key = K. Добавление в дерево пары (key, value) = (K, V). Удаление узла, в котором хранится пара (key, value) с key = K.

Поиск элемента Дано: дерево Т и ключ K. Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел. Алгоритм: Если дерево пусто, сообщить, что узел не найден, и остановиться. Иначе сравнить K со значением ключа корневого узла X. Если K=X, выдать ссылку на этот узел и остановиться. Если K>X, рекурсивно искать ключ K в правом поддереве Т. Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Добавление элемента Дано: дерево Т и пара (K,V). Задача: добавить пару (K, V) в дерево Т. Алгоритм: Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться. Иначе сравнить K с ключом корневого узла X. Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т. Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.

Удаление узла Дано: дерево Т с корнем n и ключом K. Задача: удалить из дерева Т узел с ключом K (если такой есть). Алгоритм: Если дерево T пусто, остановиться Иначе сравнить K с ключом X корневого узла n. Если K>X, рекурсивно удалить K из правого поддерева Т. Если K<X, рекурсивно удалить K из левого поддерева Т. Если K=X, то необходимо рассмотреть три случая. Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла. Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m. Если оба ребёнка присутствуют, то найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n); присвоим ссылке Left(m) значение Left(n) ссылку на узел n в узле Parent(n) заменить на Right(n); освободим память, занимаемую узлом n (на него теперь никто не указывает).

Двоичная куча

Двоичная куча Двоичная куча (пирамида) — такое двоичное дерево, для которого выполнены три условия: Значение в любой вершине больше, чем значения её потомков. Каждый лист имеет глубину (расстояние до корня) либо d либо d-1. Иными словами, если назвать слоем совокупность листьев, находящемся на определённой глубине, то все слои, кроме, может быть, последнего, заполнены полностью. Последний слой заполняется слева направо. Существуют также кучи, где значение в любой вершине, наоборот, меньше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap.

Кучи Max-heap Значение в любой вершине больше, чем значения ее потомков

Красно-чёрное дерево

Красно-чёрное дерево Красно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — «цвет». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный». Красно-чёрное дерево обладает следующими свойствами: Все листья черные. Все потомки красных узлов черные (т.е. запрещена ситуация с двумя красными узлами подряд). На всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково. Это число называется чёрной высотой дерева. При этом для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных.

АВЛ-дерево АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962

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

2-3-дерево 2-3 дерево — структура данных являющаяся B-деревом степени 1, страницы которого могут содержать только 2-вершины (вершины с одним полем и 2-мя детьми) и 3-вершины (вершины с 2-мя полями и 3-мя детьми). Листовые вершины являются исключением — у них нет детей (но может быть одно или два поля). 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.