Деревья.ppt

«Деревья»
Цель работы
Изучить способы

эффективного хранения и обработки информации на примере деревьев.

узла, называемого корнем (root). В терминах генеалогического дерева узел можно

считать родителем (parent), указывающим на 0, 1 или более узлов, называемых сыновьями (children). Дерево может представлять несколько поколений семьи. Сыновья узла и сыновья их сыновей называются потомками (descendants), а родители и прародители — предками (ancestors) этого узла. Каждый некорневой узел имеет только одного родителя, и каждый родитель имеет 0 или более сыновей. Узел, не имеющий детей (Е, G, H, I, J), называется листом (leaf).

Дерево общего вида

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

самого длинного пути от корня до узла.

каждого узла бинарного дерева может быть 0, 1 или 2

сына. По отношению к узлу слева употребляется термин левый сын (left child), а по отношению к узлу справа — правый сын (right child).

Бинарные деревья

бинарные деревья (complete binary tree) глубины N, где каждый уровень

0...N-1 имеет полный набор узлов и все листья уровня N расположены слева. Законченное бинарное дерево, содержащее 2N узлов на уровне N является полным (full). На рисунке показаны законченное и полное бинарные деревья.

данных и указатели на другие узлы в коллекции. Узел дерева

содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL является признаком пустого дерева.

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

ключи его правого поддерева — больше, оно называется деревом поиска.

названия: АВЛ-деревья и сбалансированные деревья. АВЛ произошло от фамилий изобретателей(Г.М.Адельсоном-Вельским

и Е.М.Ландисом). Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более, чем на 1.

Г.М.Адельсон-Вельский

Е.М.Ландис

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

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

Вращения

баланса, равен -2, а показатель сбалансированности корня левого поддерева равен

-1. Тогда восстановить сбалансированность такого поддерева можно следующим преобразованием, называемым малым левым вращением:

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

в которой произошло нарушение баланса равен -2, а показатель сбалансированности

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

корне показатель сбалансированности по модулю равен 2-м. Такое дерево можно

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

варианта задания соответствует вашему номеру в журнале)
1. Написать рекурсивную числовую

функцию, подсчитывающую сумму элементов дерева.
2. Написать функцию, которая находит наибольший элемент дерева.
3. Написать функцию, которая находит наименьший элемент дерева.
4. Напишите процедуру, которая удаляет из дерева все четные элементы.
5. Написать рекурсивную процедуру, которая определяет число вхождений заданного элемента в дерево.
6. Написать рекурсивную процедуру, которая печатает элементы из всех листьев дерева.

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


7. Написать процедуру,

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

1 группа
1 курс
2 группа
ФМИ
3 группа
2 курс
4 группа
8. Написать рекурсивную функцию, которая определяет глубину заданного элемента на дереве и возвращает –1, если такого элемента нет.
9. Написать процедуру, которая печатает (по одному разу) все вершины дерева.
10. Написать процедуру, которая по заданному n считает число всех вершин глубины n в заданном дереве.
11. Написать процедуру, которая считает глубину дерева.

и скопировать отсортированные данные обратно в А.
13. Задана последовательность

слов. Определить частоту вхождения каждого из слов в последовательность.
Указание. Для решения задачи любое слово ищется в дереве, которое на начальном этапе пусто. Если слово найдено, то счетчик его вхождений увеличивается на единицу, если нет, то слово включается в дерево с единичным значением счетчика.
14. Написать программу представления бинарного дерева с помощью динамических структур (запрограммировать стандартные операции: добавление, удаление элемента, просмотр дерева). Запрограммировать специальную функцию, которая определяет значение листа двоичного дерева, имеющего минимальную глубину
15. Организовать хранение сбалансированного дерева в памяти ЭВМ, а также реализовать основные операции над сбалансированным деревом: поиск/добавление/удаление.

12. Отсортировать массив А путем включения его элементов в дерево и скопировать отсортированные данные обратно в А.
13. Задана последовательность слов. Определить частоту вхождения каждого из слов в последовательность.
Указание. Для решения задачи любое слово ищется в дереве, которое на начальном этапе пусто. Если слово найдено, то счетчик его вхождений увеличивается на единицу, если нет, то слово включается в дерево с единичным значением счетчика.
14. Написать программу представления бинарного дерева с помощью динамических структур (запрограммировать стандартные операции: добавление, удаление элемента, просмотр дерева). Запрограммировать специальную функцию, которая определяет значение листа двоичного дерева, имеющего минимальную глубину
15. Организовать хранение сбалансированного дерева в памяти ЭВМ, а также реализовать основные операции над сбалансированным деревом: поиск/добавление/удаление.

вершин на каждом уровне непустого дерева (корень считать вершиной 0-го

уровня). В программе используйте подпрограммы.
17. Напишите программу, содержащую процедуру или функцию, которая определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.
18. Постройте два дерева. Проверьте, является ли одно из них поддеревом другого. Если "нет", то включите это поддерево. В программе используйте подпрограммы.
19. Написать программу формирования дерева. Удалите из дерева все повторяющиеся элементы. В программе используйте подпрограммы.
20. Объедините два дерева в одно идеально сбалансированное. В программе используйте подпрограммы.

16. Напишите программу, содержащую процедуру или функцию, которая подсчитывает число вершин на каждом уровне непустого дерева (корень считать вершиной 0-го уровня). В программе используйте подпрограммы.
17. Напишите программу, содержащую процедуру или функцию, которая определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.
18. Постройте два дерева. Проверьте, является ли одно из них поддеревом другого. Если "нет", то включите это поддерево. В программе используйте подпрограммы.
19. Написать программу формирования дерева. Удалите из дерева все повторяющиеся элементы. В программе используйте подпрограммы.
20. Объедините два дерева в одно идеально сбалансированное. В программе используйте подпрограммы.

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

дерево, сбалансированное по АВЛ, изучить управление таким деревом, анализ алгоритмов управления.
При выполнении индивидуального задания придерживаться следующей последовательности действий:
- изучить словесную постановку задачи;
- разработать программу, решающую поставленную задачу;
- оттестировать и отладить программу;
- написать и представить к защите отчет по работе.

Программа
4. Результат выполнения работы программы
5. Ответы на контрольные вопросы
6. Вывод

два способа хранения деревьев в памяти ЭВМ, укажите их недостатки

и достоинства.
3. Приведите определение идеально сбалансированного дерева и дерева сбалансированного по АВЛ.
4. Что такое вращения и для чего они применяются?