Материал: Вопросы к экзамену

2) помещаем операцию o1 в стек.

•Когдавходнаястроказакончилась,выталкиваемвсесимволыизстекаввыходнуюстроку.

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

12.Деревья. Дерево поиска и бинарное дерево поиска. Основные понятия.

Дерево — структура данных, эмулирующая древовидную структуру в виде набора

связанных узлов. Является связным графом, не содержащим циклы.

Дерево поиска — структура данных для работы с упорядоченными множествами. Один узель может иметь сколько угодно потомков.

Двоичное дерево поиска — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

•Оба поддерева — левое и правое — являются двоичными деревьями поиска.

•У всех узловлевого поддерева произвольного узла Xзначения ключейданных меньше, нежели значение ключа данных самого узла X.

•УвсехузловправогоподдеревапроизвольногоузлаXзначенияключейданныхбольше либо равны, нежели значение ключа данных самого узла X.

Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше. (В случае, если в поле данных расположена структура или касс, то нужно либо в структуре/классе перегрузить(определить) оператор сравнения, либо поиск выполнить по определенному полю структуры/класса)

Основным преимуществом является(log возможная высокая (эффективностьlog реализации основанных на нём алгоритмов поиска ( ) ) и сортировки ( ) ).

Подробнее про деревьев (Бинарное, АВЛ, КЧ): https://markoutte.me/wp-content/uploads/Сбалансированные-деревья-поиска.pdf

13. Сбалансированные деревья. Основные понятия. Малый и большой повороты дерева.

Сбалансировзнное дерево – сбалансированнoe по высоте двоичное дерево поиска.

Для каждой его вершины высота её двух поддеревьев различается не более чем на 1 (в случае АВЛ), количество черных узлов совпадает (в случае КЧ дерева), в последнем уровне нет ''дырок'' (в случае 2-3-4… дерева).

Малый поворот бывает левый и правый.

Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев |высота (L)− высота (R)| = 2, изменяет связи предок-потомок в поддереве даннойвершинытак, чтобы восстановилосьсвойство дерева | высота (L)− высота (R) | 1, иначе ничего не меняет.

Двойные (большие) повороты выполняются в случае, если при малом повороте невозможно сбалансироватрь дерево. Большие повороты выполняются относительно данного узла и родителя/дляди/деда данного узла (зависит ос случае).

Двоичное дерево представляет собой в общем случае неупорядо-ченный набор узлов, который

•либо пуст (пустое дерево)

•либо разбит на три непересекающиеся части:

11

•узел, называемый корнем;

•двоичное дерево, называемое левым поддеревом;

•двоичное дерево, называемое правым поддеревом.

Таким образом, двоичное дерево — это рекурсивная структура данных.

Каждый узел двоичного дерева можно представить в виде струк-туры данных, состоящей из следующих полей:

•данные, обладающие ключом, по которому их можно идентифицировать;

•указатель на левое поддерево;

•указатель на правое поддерево;

•указатель на родителя (необязательное поле).

Значение ключа уникально для каждого узла.

14.Сбалансированные деревья. АВЛ-деревья. Основные понятия.

См. вопрос 13 +

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его

вершины высота её двух поддеревьев различается не более чем на 1.

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

В каждом узле АВЛ-дерева, помимо ключа, данных и указателей на левое и правое поддеревья (левого и правого сыновей), хранит-ся показатель баланса – разность высот правого

и левого поддере-вьев.

Максимальная высота АВЛ-дерева при≤ заданном√2 log( +числе2) узлов:

Балансировка. Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предокпотомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

Используются 4 типа вращений:

•Большое левое вращение

•Малое левое вращение

•Большое правое вращение

•Малое правое вращение

15.Сбалансированные деревья. АВЛ-деревья. Алгоритм добавления нового узла.

См. вопрос 13 + 14 +

Алгоритм добавления нового узла.

1.Проходим по дереву поиска, пока не убедимся, что добавляемого ключа в дереве нет.

2.Включения новой вершины в дерево

3.Определения результирующих показателей балансировки.

4.«Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности.

5.Если необходимо — балансировка.

12

Балансировка:

Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсияидет назад), тогда возможны три случая: { hl — высота левого поддерева, hr — высота правого поддерева } Включение вершины в левое поддерево приведет к

1.hl < hr: выравняется hl = hr. Ничего делать не нужно.

2.hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.

3.hl > hr: теперь | hl — hr | = 2, — требуется балансировка. В данной ситуации требуется определить балансировку левого поддерева. Если левоеподдеревоэтой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.

16.Сбалансированные деревья. АВЛ-деревья. Алгоритм удаления существующего узла.

См. вопрос 13 + 14 +

Рекурсивный алгоритм удаления.

Если вершина — лист, то удалим её и вызовем балансировку всех её предков в порядке от

родителя к корню.

Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.

Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировкивысота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может измениться) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой(по) второму вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует операций. Становится очевидной возможность оптимизации: поискближайшей(log ) вершины может быть выполнен по краю поддерева, что сокращает сложность до

.

Нерекурсивное удаление из АВЛ-дерева сверху вниз:

1.Найдём вершину, удаление из которой не приведёт к изменению её высоты.

Существует два случая:

1.высота левого поддерева равна высоте правого поддерева (исключая случай, когда у листа нет поддеревьев)

2.высота дерева по направлению движения меньше противоположной(«брат» направления) и баланс «брата» равен 0 (разбор этого варианта довольно сложен, так что пока без доказательства)

13

2.Найденная удаляемая вершина заменяется значением из левой подветви.

1.ищем удаляемый элемент и попутно находим нашу замечательную вершину

2.производим изменение балансов, в случае необходимости делаем ребалансировку

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

17.Сбалансированные деревья. Красно-чёрные деревья. Основные понятия.

См. вопрос 13 +

Красно-чёрные деревья:

КЧ-деревья – это двоичные деревья поиска, каждый узел которых хранит дополнительное

поле color, обозначающее цвет: красный или черный, и для которых выполнены приведенные ниже свойства.

struct RBNode { key_type key;

struct RBNode *left, *right, *parent; char color; // цвет

};

Если left или right равны NULL, то это «указатели» на фиктивные листья. Таким образом, все узлы – внутренние (нелистовые).

Свойства КЧ-деревьев:

1.каждый узел либо красный, либо черный;

2.каждый лист (фиктивный) – черный;

3.если узел красный, то оба его сына – черные;

4.все пути, идущие от корня к любому фиктивному листу, содержат одинаковое количество черных узлов;

5.корень – черный.

Черная высота:

Черной высотой узла называется количество черных узлов на пути от этого узла к узлу, у которого оба сына – фиктивные листья.

Сам узел не включается в это число. Например, у дерева, приведенного на рисунке ниже, черная высота корня равна 2.

14

18.Сбалансированные деревья. Красно-чёрные деревья. Алгоритм добавления нового узла.

См. вопрос 13 + 17 + См.стр 38 из этой книги:

https://markoutte.me/wp-content/uploads/Сбалансированные-деревья-поиска.pdf

19.Сбалансированные деревья. Красно-чёрные деревья. Алгоритм удаления существующего узла.

См. вопрос 13 + 17 + См.стр 42 из этой книги:

https://markoutte.me/wp-content/uploads/Сбалансированные-деревья-поиска.pdf

20.Сбалансированные деревья. B-деревья. 2-3-4 деревья. Основные понятия.

См. вопрос 13 +

B-дерево — структура данных, дерево поиска. С точки зрения внешнего логического

представления, сбалансированное, сильно ветвистое дерево. Часто используется для хранения данных во внешней памяти.

B-деревом называется дерево, удовлетворяющее следующим свойствам:

потомок и все его потомки содержат ключи из интервала Глубина всех листьев одинакова.

Поиск ключа в Б-дереве:

Если ключ содержится в корне, он найден. Иначе определяем интервал и идём к соответствующему потомку. Повторяем.

2-3-4 дерево:

2–3–4 дерева (также названный деревом 2–4) являются самоуравновешивающейся структурой данных. Числа означают дерево, где каждый узел с детьми (внутренний узел) имеет или два, три, или четыре детских узла:

•с 2 узлами имеет один элемент данных, и, если внутренний имеет два детских узла;

•с 3 узлами имеет два элемента данных, и, если внутренний имеет три детских узла;

•с 4 узлами имеет три элемента данных, и, если внутренний имеет четыре детских узла.

15