43966

Оптимизация алгоритма построения AVL дерева

Доклад

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

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

Русский

2014-03-31

63.34 KB

4 чел.

Оптимизация алгоритма построения AVL дерева.

АВЛ-деревья

По определению идеально сбалансированное дерево это дерево, все уровни которого, за исключением, может быть, последнего, полностью заполнены. (В бинарном дереве полностью заполненный уровень n содержит 2n узлов). При соблюдении данного условия бинарное дерево предоставляет оптимальнейшие условия для поиска в нем. Однако на практике поддерживать идеальную балансировку дерева вряд ли выгодно, поскольку процедура ее восстановления после случайного включения – довольно сложная операция, поэтому вводится понятие АВЛ-сбалансированных деревьев (АВЛ – аббревиатура фамилий создателей: Адельсон-Вельский и Ландис), в которых критерий сбалансированности несколько упрощен. Дерево называется АВЛ-сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1 Балансировка выполняется с помощью действий, называемых поворотами узлов. При включении узлов повороты выполняются для ближайшего узла с нарушенной балансировкой к включенному. То есть, если после включения узла в дереве образуется несколько узлов с нарушенной балансировкой, поворот выполняется для того, который находится ниже (то есть ближе к включенному). После балансировки этого узла восстанавливается баланс и выше расположенных узлов. Нарушенный путь обозначается аббревиатурами LL, RR (при данном типе разбалансировки выполняется одинарный поворот), RL, LR (требуется двойной поворот), в зависимости от пути от разбалансированного узла к узлу, вызвавшему эту разбалансировку. Причем, стоит отметить, что при LL и RR, и при RL и LR выполняемые действия являются симметричными относительно узлов, что удобно при реализации алгоритма.Правый поворот

 

В левое поддерево добавили элемент 1Дерево не сбалансированноH(Left)=1 > H(Right)=-1Необходимо увеличить высоту правого поддерева

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

Левый поворот(L-rotation)В правое поддерево вставлен элемент3Поворачиваем ребро, связывающее кореньи его правый дочерний узел, влево

 

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

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

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

Для хранения ссылок на «потомков» используйте массив указателей: так будет проще организовать симметрию поворотов.

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


 

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

704. Особенности проведения корреляционно-регрессионного анализа 133 KB
  Используя метод наименьших квадратов определить наличие линейной зависимости между двумя признаками f1 и f2. Коэффициент линейной корреляции между признаками η.
705. Погрузочно-разгрузочные машины напольного действия и область их применения 35 KB
  Погрузочно-разгрузочные машины напольного действия предназначены для погрузки-выгрузки тарно-штучных, сыпучих грузов на транспортные средства, а также для перемещения на складах (складирование и сортировка).
706. Комплексная механизация и автоматизация погрузо-разгрузочных работ и складских операций с зерновыми грузами 43 KB
  Характеристика зерновых грузов и типы зернохранилищ. Зерновые склады по назначению подразделяются на заготовительные, перевалочные, производственные и базисные. Элеватор состоит из рабочей башни и силосных корпусов. КМАПРР и складские операции для вяжущих строительных материалов.
707. Лекарственные средства, влияющие на функции органов дыхания 58.5 KB
  Классификация лекарственных средств, влияющих на дыхание. Противокашлевые средства. Отхаркивающие средства. Бронхолитические средства. Аналептики прямого и рефлекторного действия.
708. Утренняя гигиеническая гимнастика 97 KB
  Сущность утренней гигиенической гимнастики. Методические указания к использованию физических упражнений в комплексах утренней гигиенической гимнастики. Комплекс упражнений утренней гигиенической гимнастики. Самоконтроль для занимающихся утренней гигиенической гимнастикой.
709. Территориальная организация хозяйства 131.5 KB
  Территориальная организация хозяйства России. Территориальная организация хозяйства Мурманской области. Отрасли с наибольшим удельным весом в структуре промышленного производства страны.
710. Социология социальной сферы: предметная область 176 KB
  Предмет социологии социальной сферы и место в структуре социологического знания. Функции социологии социальной сферы и уровни организации изучения социальных процессов. Понятийный аппарат социологии социальной сферы.
711. Закон больших чисел и предельные теоремы теории вероятностей 49.5 KB
  Среднее арифметическое математических ожиданий. Теорема Чебышева. Ее сущность и значение для практики. Случайные величины имеют различные математические ожидания.
712. Анализ динамики обменного курса рубля 58.5 KB
  Используя средства Microsoft Excel и статистические показатели, научиться оценивать динамику реального курса рубля. Установление валютного курса (в результате торгов или государственными органами). Осуществление взаимного обмена валютами при торговле товарами и услугами, при движении капиталов и кредитов.