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

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

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

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

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

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

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

Покажем, что h<log₂ (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.

В АВЛ - дереве показатель сбалансированности должен быть в диапазоне [-1, 1]. На рисунке 3 изображены АВЛ - деревья с пометками -1, 0 и +1 на каждом узле, показывающими относительный размер левого и правого поддеревьев.

-1: Высота левого поддерева на 1 больше высоты правого поддерева.

0: Высоты обоих поддеревьев одинаковы.

+1: Высота правого поддерева на 1 больше высоты левого поддерева.

Рис. 1.

Рис. 2.

Используя свойства наследования, можно образовать класс AVLTreeNode на базе класса TreeNode. Объект типа AVLTreeNode наследует поля из класса TreeNode и добавляет к ним поле balanceFactor. Данные - члены left и right класса TreeNode являются защищенными, поэтому AVLTreeNode или другие производные классы имеют к ним доступ.

Рис. 3.

Спецификация класса AVLTreeNode.