43960

Выбор и обоснование структуры данных для алгоритма построения AVL дерева

Доклад

Информатика, кибернетика и программирование

АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так. Следует заметить, что сбалансированные деревья очень эффективны для поиска.

Русский

2014-03-31

16.14 KB

5 чел.

Выбор и обоснование структуры данных для алгоритма построения AVL дерева Высотой некоторого бинарного дерева является максимальный уровень его листьев. Баланс некоторого узла определяется как высота его левого поддерева минус высота его правого поддерева.

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

АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так. Следует заметить, что сбалансированные деревья очень эффективны для поиска. Предположим у нас сбалансированное дерево и упорядоченное бинарное дерево, которое вырождено, оба эти дерева содержат 10000 узлов. Так, например, упорядоченном бинарном дереве следует просмотреть 9999 уровней дерева прежде, чем он найдет самый крайний правый узел, а сбалансированном дереве 8 уровней.

Возможны 3 случая:

  1. hL = hR: L и R становятся неравной высоты, но критерий сбалансированности не нарушается
  2. hL < hR: L и R приобретают равную высоту, т.е. сбалансированность даже улучшается
  3. hL > hR: критерий сбалансированности нарушается, и дерево нужно трансформировать, такая перестройка называется поворотом.

Поворот должен удовлетворять следующим требованиям:

  1. Прохождение трансформированного дерева в симметричном порядке должно быть таким же, как и для первоначального дерева (т.е. трансформированное дерево должно оставаться деревом бинарного поиска)
  2. Трансформированное дерево должно быть сбалансированным

Одинарный поворот вправо происходит тогда, когда родительский узел Р и его левый сын LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывая правое поддерево узла LC (ST) присоединяется к Р в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла Р. Поворот уравновешивает как родителя, так и его левого сына.

Двойной поворот вправо происходит тогда, когда родительский узел (Р) становится перевешивающим влево, а его левый сын (LC) - перевешивающим вправо. NP - корень правого перевешивающего дерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.

Процесс включения узла состоит из последовательности таких 3 этапов:

  1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве
  2. Включить новый узел и определить новый показатель сбалансированности
  3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла

 

А также другие работы, которые могут Вас заинтересовать

12703. Построение трехмерной модели предмета. Построение комплексного чертежа предмета 2.3 MB
  Лабораторная работа №3 Часть 1.Построение трехмерной модели предмета Часть 2. Построение комплексного чертежа предмета ВВЕДЕНИЕ Данные методические рекомендации предназначаются для студентов первого курса очного обучения изучающих дисциплину Инженерна
12704. Моделирование сборочной единицы в системе КОМПАС -3D 2.87 MB
  Методические рекомендации по выполнению конструкторской документации в системе КОМПАС 3D. Лабораторная работа. Моделирование сборочной единицы. Содержание. Введение. 1. Задание..5 2.. Моделирование сборочной единицы.6 ...
12705. Создание трёхмерных моделей и ассоциативных чертежей деталей, входящих в состав сборочной единицы 2.31 MB
  Методические рекомендации по выполнению конструкторской документации в системе КОМПАС 3D Лабораторная работа №1 Создание трёхмерных моделей и ассоциативных чертежей деталей входящих в состав сборочной единицы Содержание. Введение. 1. Задание
12706. Организация военно-патриотического воспитания подростков на примере деятельности клуба Мужество 270.5 KB
  Патриотическое воспитание учащихся в настоящее время приобретает архиважное значение. Воспитать патриотов сегодня – это значит обеспечить будущее завтра. В советский период на самых различных государственных уровнях патриотической работе с молодёжью уделяется очень большое значение.
12707. Simulink: Инструмент моделирования динамических систем 3.66 MB
  И.В.Черных. Simulink: Инструмент моделирования динамических систем. Содержание 1. Общие сведения 52. Запуск Simulink 53. Обозреватель разделов библиотеки Simulink 64. Создание модели 85. Окно модели 106. Основные приемы подготовки и редактирования модели 11 6.1. Добавление текстовых надпис...
12708. ЗАКОНЫ КИРХГОФА И ОСНОВНЫЕ СВОЙСТВА ЛИНЕЙНОЙ РЕЗИСТИВНОЙ ЦЕПИ 95 KB
  ЗАКОНЫ КИРХГОФА И ОСНОВНЫЕ СВОЙСТВА ЛИНЕЙНОЙ РЕЗИСТИВНОЙ ЦЕПИ Лабораторная работа 1 по дисциплине Электротехника Цель работы. Проверить справедливость законов Кирхгофа а также основных принципов свойств и теорем линейных цепей на примере р...
12709. Создание буклета «Планшет» 2.65 MB
  Упражнение 5. Создание буклета Планшет Рис.6.1.Готовый буклет Цель упражнения: освоить создание и редактирование текстовых объектов и эффект обтекания текстом. 1. Создаем новый документ с размерами рабочего листа...
12710. Конспект лекций к изучению курса Solid Work 593.01 KB
  Лекция №1 Тема: Основные понятия структура документа в программе SolidWorks.Цель:Ознакомиться с основными понятиями структурой документа общими сведениями о панелях инструментов. План лекции: Общие сведения о программе SolidWorks. Окна документов. Условные об...
12711. Создание простой модели в SolidWorks 2001 132 KB
  Практическая работа №2. Тема: Создание простой модели в SolidWorks 2001.Цель: Создание простой модели основания с применением инструментов эскиза прямоугольник окружность нанесением размеров добавлением бобышки выреза изменением элементов добавление скруглений измен...