Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

авл деревья поиска ответы на вопросы vkclub152685050

.pdf
Скачиваний:
40
Добавлен:
08.08.2019
Размер:
869.17 Кб
Скачать

vk.com/id446425943 Ответы 6 лаб

Что такое дерево? Что такое высота и степень дерева?

 

 

vk.com/club152685050

Деревом называется орграф, для которого

vk.com/id446425943

существует узел, в который не входит ни одной дуги (корень);

 

в каждую вершину, кроме корня, входит одна дуга.

 

Вершины дерева подразделяют на следующие три группы:

корень – вершина, в которую не входит ни одной дуги;

узлы – вершины, в которые входит одна дуга и выходит одна или более дуг;

листья – вершины, в которые входит одна дуга и не выходит ниодной

дуги.

Все вершины, в которые входят дуги, исходящей из одной вершины, называются потомками этой вершины, а сама вершина – предком. Корень не имеет предка, а листья не имеют потомков.

Выделяют уровни дерева. На первом уровне дерева может быть только дна вершина корень, на втором – потомки корня, на третьем – потомки потомков корня и т. Д

Поддеревом называется вершина со всеми ее потомками

Высотой поддерева будем считать максимальную длину цепи y1, …,yn его вершин такую, что yi+1 – потомок yi для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня – единице.

Степенью вершины в дереве называется количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень нуль.

По величине степени дерева часто различают два типа деревьев:

 

двоичные – степень дерева не более двух;

vk.com/club152685050

сильноветвящиеся – степень дерева произвольная

vk.com/id446425943

 

 

Cтепеньдеревапроизвольнаятепень дерева произвольная

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

Назовите способы реализации бинарного дерева.

Двоичные (бинарные)

деревья – это деревья со степенью не более двух

двоичные деревья бывают:

строгие – вершины дерева имеют степень нуль (у листьев) или два (у узлов);

нестрогие – вершины дерева имеют степень нуль (у листьев), один или два (у узлов).

vk.com/club152685050

vk.com/id446425943

В общем случае на k-муровнедвоичногодереваможетбытьдо2k–1м уровне двоичного дерева может быть до 2k–1k–1

вершин.Двоичное дерево, содержащее только полностью заполненные уровни (т. е. 2k–1k–1 вершин на каждом k-муровнедвоичногодереваможетбытьдо2k–1м уровне), называется полным .

Двоичное дерево можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде списка

Списочное представление двоичных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой – с левым. Листья имеют пустые указатели потомков. При таком способе представления дерева обязательно следует сохранять указатель на узел, являющийся корнем дерева.

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

Главным недостатком статического способа представления двоичного дерева является то, что массив имеет фиксированную длину. Размер массива выбирается исходя из максимально возможного количества уровней двоичного дерева, и чем менее полным является дерево, тем менее рационально используется память. Кроме того, недостатком являются большие накладные расходы при изменении структуры дерева (например, при обмене местами двух поддеревьев).

vk.com/club152685050

vk.com/id446425943

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

Двоичные (бинарные)

В качестве основных операций с двоичными деревьями рассмотрим операцию прямого обхода

двоичного дерева в рекурсивной и нерекурсивной форме.

Реализация обратного и симметричного обходов аналогична. Операции добавления, поиска и удаления вершин дерева зависят от принятого порядка вершин

В процедуре, реализующей нерекурсивный обход двоичного дерева, используется стек, хранящий путь от корня дерева до предка текущей вершины.

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

Что такое дерево поиска?

vk.com/club152685050

vk.com/id446425943

 

Случайные деревья поиска

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

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

При поступлении элементов в случайном порядке получаем дерево с минимальной высотой h (рис.32,рис. 32, а), а соответственно минимизируется время поиска элемента в таком дереве, которое пропорцио-

нально O(рис.32,log n). При поступлении элементов в упорядоченном виде или в несколько необычном порядке (рис.32,рис. 32, в) происходит построение вырожденных деревьев поиска (рис.32,оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет O(рис.32,n)

Что такое идеально сбалансированное дерево?

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

vk.com/club152685050

vk.com/id446425943

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

Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.

При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.

Схематично алгоритм добавления нового элемента в сбалансированное дерево будет состоять из следующих трех основных шагов:

1.поиск по дереву.

2.вставка элемента в место, где закончился поиск, если элемент отсутствует.

3.восстановление сбалансированности.

Первый шаг необходим для того, чтобы убедиться в отсутствии элемента в дереве, а также найти такое место вставки, чтобы после вставки дерево осталось упорядоченным.

Первые два шага ничем не отличаются от алгоритмов,

Третий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин, и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота

Алгоритм удаления элемента из сбалансированного дерева будет выг-

 

лядеть так:

vk.com/club152685050

 

 

1.

поиск по дереву

vk.com/id446425943

 

2.

удаление элемента из дерева.

 

3.

восстановление сбалансированности дерева (рис.32,обратный проход).

 

Первый шаг необходим, чтобы найти в дереве вершину, которая должна быть удалена

Третий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости.

Что такое дерево, сбалансированное по АВЛ?

Дерево считается сбалансированным по АВЛ (рис.32,в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.

vk.com/club152685050

vk.com/id446425943

vk.com/club152685050
vk.com/id446425943

При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.

алгоритм балансировки

В этом алгоритме опущены левые вращения (рис.32,большое и малое), которые записываются симметрично.

Предварительно договоримся, что в каждой вершине дерева помимо значения элемента будем хранить показатель сбалансированности в данной вершине. Показатель сбалансированности вершины – это разница между высотами правого и левого поддеревьев

В сбалансированном дереве показатели сбалансированности всех вершин лежат в пределах от –1 до 1. При операциях добавления/удаления могут появляться вершины с показателями сбалансированности –2 и 2

Какие операции применяют для восстановления сбалансированности дерева?

Восстановление сбалансированности представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин, и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота

vk.com/club152685050

vk.com/id446425943

vk.com/id446425943

vk.com/club152685050

ЛАБОРАТОРНАЯ РАБОТА № 6 «АВЛ - ДЕРЕВЬЯ ПОИСКА»

1.1 Цель работы

Целью работы является изучение деревьев поиска и получение практических навыков их использования.

1.2 Задание на лабораторную работу

Разработать на языке программирования высокого уровня программу, которая должна выполнять следующие функции:

добавлять элементы в сбалансированное дерево поиска;

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

искать элементы в дереве поиска с выводом количества шагов, за которое осуществляется поиск;

выводить дерево на экран (любым способом доступным для восприятия);

выводить список, соответствующий обходу вершин, в соответствии с вариантом задания;

осуществлять операцию, заданную в таблице 6.

Количество элементов и порядок их ввода при создании сбалансированного дерева поиска определяется по согласованию с преподавателем.

 

 

 

 

Таблица 1

 

 

 

 

 

Задание

 

Порядок

вар.

 

обхода

 

 

 

1

Вывести глубину самого верхнего листа дерева (maxh)

и

Прямой

 

самого нижнего листа (ов)

дерева (minh), а так же

их

 

 

значения. Удалить элементы и сбалансировать дерево.

 

 

Процедуру повторять до тех пор, пока не выполнится условие

 

 

maxh = minh

 

 

 

2

Вывести глубину самого верхнего листа дерева (maxh)

и

Обратный

 

самого нижнего листа (ов)

дерева (minh), а так же

их

 

 

значения. Удалить элементы и сбалансировать дерево.

 

 

Процедуру повторять до тех пор, пока не выполнится условие

 

 

maxh = minh

 

 

 

vk.com/club152685050

vk.com/id446425943

Задание

 

 

 

Порядок

вар.

 

 

 

обхода

 

 

 

 

 

3

Вывести глубину самого верхнего листа дерева (maxh) и

Симметричный

 

самого нижнего листа (ов)

дерева

(minh), а так

же

их

 

 

значения. Удалить элементы и перебалансировать дерево.

 

 

Процедуру повторять до тех пор, пока не выполнится условие

 

 

maxh = minh

 

 

 

 

 

4

Вывести глубину самого верхнего листа дерева (maxh) и

В ширину

 

самого нижнего листа (ов)

дерева

(minh), а так

же

их

 

 

значения. Удалить элементы и перебалансировать дерево.

 

 

Процедуру повторять до тех пор, пока не выполнится условие

 

 

maxh = minh

 

 

 

 

 

5

Подсчитать среднее арифметическое всех листов

дерева.

Прямой

 

Затем вычесть из каждого листа данное значение, затем

 

 

обойти дерево еще раз и удалить все элементы, делящиеся без

 

 

остатка на 3 и перестроить дерево с учетом изменений

 

 

 

6

Подсчитать среднее арифметическое всех листов

дерева.

Обратный

 

Затем вычесть из каждого листа данное значение, затем

 

 

обойти дерево еще раз и удалить все элементы, делящиеся без

 

 

остатка на 3 и перестроить дерево с учетом изменений

 

 

 

7

Подсчитать среднее арифметическое всех листов

дерева.

Симметричный

 

Затем вычесть из каждого листа данное значение, затем

 

 

обойти дерево еще раз и удалить все элементы, делящиеся без

 

 

остатка на 3 и перестроить дерево с учетом изменений

 

 

 

8

Подсчитать среднее арифметическое всех листов

дерева.

В ширину

 

Затем вычесть из каждого листа данное значение, затем

 

 

обойти дерево еще раз и удалить все элементы, делящиеся без

 

 

остатка на 3 и перестроить дерево с учетом изменений

 

 

 

9

Заменить в дереве все отрицательные элементы

на

их

Прямой

 

абсолютные величины, после чего уменьшить в 2 раза все

 

 

элементы, делящиеся без остатка на 4. Затем обойти дерево

 

 

повторно в соответствии с вариантом, у каждой обойденной

 

 

вершины изменить значение

=|

| , где i –

индекс

 

 

текущего элемента в порядке обхода

 

 

 

 

10

Заменить в дереве все отрицательные элементы

на

их

Обратный

 

абсолютные величины, после чего уменьшить в 2 раза все

 

 

элементы, делящиеся без остатка на 4. Затем обойти дерево

 

 

повторно в соответствии с вариантом, у каждой обойденной

 

 

вершины изменить значение

=|

| , где i –

индекс

 

 

текущего элемента в порядке обхода

 

 

 

 

11

Заменить в дереве все отрицательные элементы

на

их

Симметричный

 

абсолютные величины, после чего уменьшить в 2 раза все

 

 

элементы, делящиеся без остатка на 4. Затем обойти дерево

 

 

повторно в соответствии с вариантом, у каждой обойденной

 

 

вершины изменить значение

=|

| , где i –

индекс

 

 

текущего элемента в порядке обхода

 

 

 

 

 

vk.com/club152685050

 

 

 

 

 

vk.com/id446425943

 

 

 

 

2

Задание

 

Порядок

вар.

 

обхода

 

 

12

Заменить в дереве все отрицательные элементы на их

В ширину

 

абсолютные величины, после чего уменьшить в 2 раза все

 

 

элементы, делящиеся без остатка на 4. Затем обойти дерево

 

 

повторно в соответствии с вариантом, у каждой обойденной

 

 

вершины изменить значение =|

| , где i – индекс

 

 

текущего элемента в порядке обхода

 

 

13

Обойти дерево в соответствии с вариантом и найти

Прямой

 

максимальную глубину листа. Добавлять элементы в дерево,

 

 

пока высота всех листов дерева не будет одинакова, но не

 

 

превысит изначально найденного максимального значения

 

14

Обойти дерево в соответствии с вариантом и найти

Обратный

 

максимальную глубину листа. Циклично добавлять элементы

 

 

в дерево, пока высота всех листов дерева не будет одинакова,

 

 

но не превысит изначально найденного максимального

 

 

значения

 

 

15

Обойти дерево в соответствии с вариантом и найти

Симметричный

 

максимальную глубину листа. Циклично добавлять элементы

 

 

в дерево, пока высота всех листов дерева не будет одинакова,

 

 

но не превысит изначально найденного максимального

 

 

значения

 

 

16

Обойти дерево в соответствии с вариантом и найти

В ширину

 

максимальную глубину листа. Циклично добавлять элементы

 

 

в дерево, пока высота всех листов дерева не будет одинакова,

 

 

но не превысит изначально найденного максимального

 

 

значения

 

 

17

Циклично удалять каждый нечѐтный узел дерева (Корень – 1,

Прямой

 

нечетный) и перестраивать дерево, беря элементы по порядку

 

 

обхода. Данную процедуру выполнять, пока не останется

 

 

последний элемент. На каждой итерации выводить дерево

 

18

Циклично удалять каждый нечѐтный узел дерева (Корень – 1,

Обратный

 

нечетный) и перестраивать дерево, беря элементы по порядку

 

 

обхода. Данную процедуру выполнять, пока не останется

 

 

последний элемент. На каждой итерации выводить дерево

 

19

Циклично удалять каждый нечѐтный узел дерева (Корень – 1,

Симметричный

 

нечетный) и перестраивать дерево, беря элементы по порядку

 

 

обхода. Данную процедуру выполнять, пока не останется

 

 

последний элемент. На каждой итерации выводить дерево

 

20

Циклично удалять каждый нечѐтный узел дерева (Корень – 1,

В ширину

 

нечетный) и перестраивать дерево, беря элементы по порядку

 

 

обхода. Данную процедуру выполнять, пока не останется

 

 

последний элемент. На каждой итерации выводить дерево

 

21

Для каждого узла дерева A, вывести список потомков в

Прямой

 

порядке обхода.

 

 

22

Для каждого узла дерева A, вывести список потомков в

Обратный

 

порядке обхода.

 

 

23

Для каждого узла дерева A, вывести список потомков в

Симметричный

 

порядке обхода.

 

 

24

Для каждого узла дерева A, вывести список потомков в

В ширину

 

порядке обхода.

 

 

 

vk.com/club152685050

 

 

vk.com/id446425943

3

1.3Порядок выполнения работы

1)выбрать вариант задания в соответствии с требованиями;

2)изучить теоретический материал;

3)разработать и реализовать на языке программирования высокого уровня алгоритм, выполняющий требования задания;

4)написать отчет о работе;

5)защитить отчет.

1.4 Содержание отчета

vk.com/id446425943

 

Отчет должен содержать:

vk.com/club152685050

 

1)титульный лист;

2)цель работы;

3)вариант задания;

4)листинг программы, реализующей алгоритм;

5)скриншоты с демонстрацией работы программы;

6)выводы по работе.

1.5 Пример выполнения работы

Алгоритм добавления нового элемента в сбалансированное дерево будет состоять из следующих трех основных шагов:

1)поиск по дереву.

2)вставка элемента в место, где закончился поиск, если элемент отсутствует.

3)восстановление сбалансированности.

Первый шаг необходим для того, чтобы убедиться в отсутствии элемента в дереве, а также найти такое место вставки, чтобы после вставки дерево осталось упорядоченным.

Третий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин, и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота.

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

4

1) поиск по дереву.

vk.com/club152685050

vk.com/id446425943

 

2)удаление элемента из дерева.

3)восстановление сбалансированности дерева (обратный проход).

Первый шаг необходим, чтобы найти в дереве вершину, которая должна быть удалена.

Третий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости.

Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, то есть порядка log n вершин.

Восстановление сбалансированности требует движения от листьев к корню, поэтому будем хранить пути от листьев к корню дерева.

struct Tree

{

int elem; //содержимое узла int height; //высота узла

Tree *Prev; //указатель на предка

Tree *Left; //указатель на меньшего потомка Tree *Right; //указатель на большего потомка

};

Примеры Функций добавления элемента и балансировки:

void BalanceTree(Tree *&Root, Tree *&NewElem)

{

Tree *MainTree = NewElem; while (true)

{

MainTree->height = max(GetHeight(MainTree->Left), GetHeight(MainTree->Right)) +

1;

if (GetHeight(MainTree->Right) - GetHeight(MainTree->Left) == 2)

{

if (GetHeight(MainTree->Right->Right) - GetHeight(MainTree->Right->Left) == 0) LeftRotate(MainTree);

else if (GetHeight(MainTree->Right->Right) - GetHeight(MainTree->Right->Left) == 1)

LeftRotate(MainTree); else

BigLeftRotate(MainTree);

}

else if (GetHeight(MainTree->Right) - GetHeight(MainTree->Left) == -2)

{

if (GetHeight(MainTree->Left->Right) - GetHeight(MainTree->Left->Left) == 0) RightRotate(MainTree);

else if (GetHeight(MainTree->Left->Right) - GetHeight(MainTree->Left->Left) == -1)

RightRotate(MainTree); else

5