48754 (Реализация АВЛ–деревьев через классы объектно–ориентированного программирования)

Министерство образования и науки Украины

Запорожская государственная инженерная академия

Кафедра программного обеспечения автоматизированных систем

КУРСОВАЯ РАБОТА

По дисциплине «Объектно – ориентированное программирование »

На тему: «Реализация АВЛ – деревьев через классы объектно – ориентированного программирования»

Выполнил: ст. гр. СП – 07 – 1з Воронько О.А.

Проверил: Попивщий В.И.

Запорожье, 2009г.

ПЛАН

Введение

1. Основные термины

2. Основные операции с АВЛ - деревьями

3. Алгоритм реализации АВЛ – деревьев через классы объектно – ориентированного программирования

Список литературы

ВВЕДЕНИЕ

Язык программирования С++ является одним из наиболее популярных средств объектно – ориентированного программирования, позволяющим разрабатывать программы, эффективные по объему кода и скорости выполнения. С++ включает большое число операций и типов данных, средства управления вычислительными процессами, механизмы модификации типов данных и методы их обработки и, как следствие, является мощным языком программирования. Он позволяет описывать процессы обработки информации, начиная с уровня отдельных разрядов, видов и адресов памяти, переходя на основе механизмов объектно – ориентированного программирования к близким конкретным предметным областям понятиям.

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

Другими важнейшими факторами, влияющими на эволюцию методов проектирования и создания ПП, являются:

• изменение архитектур вычислительных средств (ВС) в интересах повышения производительности, надежности и коммуникативности;

• упрощение взаимодействия пользователей с ВС и интеллектуализация ВС.

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

Можно выделить 5 следующих источников сложности программирования:

1) решаемая задача;

2) язык программирования;

3) среда выполнения программы;

4) технологический процесс коллективной разработки и создания ПП;

5) стремление к универсальности и эффективности алгоритмов и типов данных.

От свойства сложности нельзя избавиться, но можно изменять характеристики его проявления путем управления или организации.

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

В настоящее время объектно – ориентированное программирование (ООП) является доминирующим стилем при создании больших программ.

1. ОСНОВНЫЕ ТЕРМИНЫ

Так исторически сложилось, что у этих деревьев есть два альтернативных названия: АВЛ - деревья и сбалансированные деревья. АВЛ произошло от фамилий изобретателей.

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

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

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

Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n). Однако при некотором стечении обстоятельств дерево может оказаться вырожденным. Тогда высота его будет O(n), и доступ к данным существенно замедлится. Рассмотрим модифицированный класс деревьев, обладающих всеми преимуществами бинарных деревьев поиска и никогда не вырождающихся. Они называются сбалансированными или АВЛ - деревьями. Под сбалансированностью будем понимать то, что для каждого узла дерева высоты обоих его поддеревьев различаются не более чем на 1.

Строго говоря, этот критерий нужно называть АВЛ - сбалансированностью в отличие от идеальной сбалансированности, когда для каждого узла дерева количества узлов в левом и правом поддеревьях различаются не более чем на 1. Здесь мы всегда будем иметь в виду АВЛ - сбалансированность.

Новые методы вставки и удаления в классе АВЛ - деревьев гарантируют, что все узлы останутся сбалансированными по высоте. На рисунках 1 и 2 показаны эквивалентные представления массива АВЛ - деревом и бинарным деревом поиска. Рисунок 1 представляет простой пятиэлементный массив А (A[5] = {1,2,3,4,5}), отсортированный по возрастанию. Рисунок 2 представляет массив B (B[8] = {20, 30, 80, 40, 10, 60, 50, 70}).

Бинарное дерево поиска имеет высоту 5, в то время как высота АВЛ - дерева равна 2. В общем случае высота сбалансированного дерева не превышает O(log2n). Таким образом, АВЛ - дерево является мощной структурой хранения, обеспечивающей быстрый доступ к данным.

Для этого используем подход, при котором поисковое дерево строится отдельно от своих узлов. Сначала разрабатываем класс AVLTreeNode, а затем используем объекты этого типа для конструирования класса AVLTree. Предметом пристального внимания будут методы Insert и Delete.

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

2. ОСНОВНЫЕ ОПЕРАЦИИ С АВЛ - ДЕРЕВЬЯМИ

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

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

Добавление элемента в сбалансированное дерево.

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

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

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

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

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

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

Эффективность сортировки вставкой в АВЛ - дерево.

Ожидаемое число сравнений, необходимых для вставки узла в бинарное дерево поиска, равно O(log2n). Поскольку в дерево вставляется n элементов, средняя эффективность должна быть O(n log2n). Однако в худшем случае, когда исходный список отсортирован в обратном порядке, она составит O(n2). Соответствующее дерево поиска вырождается в связанный список. Покажем, что худший случай требует O(n2) сравнений. Первая вставка требует 0 сравнений. Вторая вставка - двух сравнений (одно с корнем и одно для определения того, в какое поддерево следует вставлять данное значение). Третья вставка требует трех сравнений, 4 - я четырех,..., n - я вставка требует n сравнений. Тогда общее число сравнений равно:

0 + 2 + 3 + ... + n = (1 + 2 + 3 + ... + n) - 1 = n(n + 1) / 2 - 1 = O(n2)

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

Когда n случайных значений повторно вставляются в бинарное дерево поиска, можно ожидать, что дерево будет относительно сбалансированным. Наилучшим случаем является законченное бинарное дерево. Для этого случая можно оценить верхнюю границу, рассмотрев полное дерево глубиной d. На i-ом уровне (1≤i≤d) имеется 2i узлов. Поскольку для помещения узла на уровень i требуется i+1 сравнение, сортировка на полном дереве требует (i+1) * 2i сравнений для вставки всех элементов на уровень i.

Если вспомнить, что n = 2(d+1) - 1, то верхняя граница меры эффективности выражается следующим неравенством:

Таким образом, эффективность алгоритма в лучшем случае составит O(n log2n).

Удаление элемента из сбалансированного дерева.

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

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

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

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

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

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

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

Анализ операций над сбалансированным деревом.

Понятно, что в случае полного двоичного дерева мы получим сложность T(log(n)) (на каждом шаге размер дерева поиска будет сокращаться вдвое). Рассмотрим минимальное сбалансированное дерево (худший случай). Таким будет дерево, у которого для каждой вершины высота левого и правого поддеревьев различаются на 1. Для такого дерева можно записать следующую рекуррентную формулу для числа вершин (h – высота дерева):

Покажем, что h2(N_h). Для этого необходимо и достаточно показать, что 2^h>N_h. Докажем последнее методом математической индукции.а) h=0: 2⁰>N₀=0; б) h=1: 2¹>N₁=1; в) h>1: Пусть 2^h-2>N_h-2 и 2^h-1>N_h-1. Тогда 2^h-2+2^h-1>N_h-2+ N_h-1. И далее получаем 2^h>1+2^h-2+2^h-1>1+N_h-2+ N_h-1=N_h, что и требовалось доказать.

Таким образом алгоритмы поиска/добавления/удаления элементов в сбалансированном дереве имеют сложность T(log(n)). Г.М. Адельсон -Вельский и Е.М. Ландис доказали теорему, согласно которой высота сбалансированного дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%.

Основные узлы АВЛ - деревьев.

АВЛ - деревья имеют структуру, похожую на бинарные деревья поиска. Все операции идентичны описанным для бинарных деревьев, за исключением методов Insert и Delete, которые должны постоянно отслеживать соотношение высот левого и правого поддеревьев узла. Для сохранения этой информации расширяем определение объекта TreeNode, включив поле balanceFactor (показатель сбалансированности), которое содержит разность высот правого и левого поддеревьев.

Left data balanceFactor right

AVLTreeNode

balanceFactor = height(right subtree) - height(left subtree)

Если balanceFactor отрицателен, то узел «перевешивает влево», так как высота левого поддерева больше, чем высота правого поддерева. При положительном balanceFactor узел «перевешивает вправо». Сбалансированный по высоте узел имеет balanceFactor = 0.