43966

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

Доклад

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

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

Русский

2014-03-31

63.34 KB

5 чел.

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

АВЛ-деревья

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

 

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

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

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

 

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

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

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

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

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


 

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

45155. Распад СССР и кризисы постсоветского государственного управления 17.72 KB
  Распад СССР процессы системной дезинтеграции происходившие в экономике народном хозяйстве социальной структуре общественной и политической сфере Советского Союза приведшие к прекращению существования СССР в конце 1991 г. 25 декабря 1991 Президент СССР М. Горбачев объявил о прекращении своей деятельности на посту Президента СССР по принципиальным соображениям; 26 декабря Верховный Совет СССР принял декларацию о прекращении существования СССР.
45157. Синодальная система управления Церковью 87.5 KB
  Тем не менее процесс развития капитализма в России набирал силу.Внешняя политика Александра III Миротворца В области внешней политики период царствования Александра III характеризуется почти полным отсутствием войн: только небольшие боевые действия в Туркмении на этом завершилось присоединение Средней Азии к России. Тройственного союза в составе: Германия АвстроВенгрия и Италия стало ясно что естественным союзником России при таком раскладе сил должна быть Франция.Итак патриархальное правление Александра III в общем смогло лишь...
45158. Учредительное собрание 15.7 KB
  ВСЕРОССИЙСКОЕ УЧРЕДИТЕЛЬНОЕ СОБРАНИЕ. Выборы в Учредительное собрание состоялись в конце 1917. На Втором съезде Советов большевики пообещали созвать Учредительное собрание и признать его властью от которой зависит решение всех основных вопросов но это обещание не собирались выполнять. Большевики считали Учредительное собрание главным своим соперником в борьбе за власть.
45159. Лествичная система и княжое право периода раздробленности 13.13 KB
  Княжили в таком порядке: старший братмладшие братья по порядкусыновья старшего брата по старшинствусыновья следующих братьев по старшинствувнуки правнуки в той же последовательности и т. По мере смены главного князя все прочие переезжали по старшинству из города в город.
45160. Столыпинская модель ГУ. Реформа органов государственного управления 23.69 KB
  Об образовании из восточных частей Люблинской и Седлецкой губерний особой Холмской губернии с изъятием ее из управления варшавского генералгубернатора Столыпин и Государственная Дума это особый вопрос. К его чести Столыпин наверное единственный из министров царского правительства кто не боялся выступать в Думе с ответами по самым разным депутатским запросам. Между тем иногда аудитория была настроена к нему настолько враждебно что изза шума в зале Столыпин не мог начать выступление в течение 10 15 минут. Например выступая в Думе по...
45161. Кризис государственной власти и начало конца дворянской управленческой элиты 23.61 KB
  Кризис государственной власти и начало конца дворянской управленческой элиты Почему же относительно легко был сокрушен монархический строй в России Среди главных причин нужно назвать десакрализацию верховной власти потерю ею своего авторитета. В период кризиса власти негативную роль сыграло отсутствие у монарха качеств государственного лидера. Продвижение к власти осуществлялось по критерию личной преданности царю. Назреванию кризиса самодержавной власти способствовала мировая война кровавый воз которой Россия тянула с августа 1914 г.
45162. Двоевластие и его сущность. Кризисы Временного правительства: причины и последствия 16.38 KB
  Кризисы Временного правительства: причины и последствия 27 февраля был образован Петроградский совет рабочих депутатов в количестве 250 человек избравший свой исполнительный комитет. 1 марта между Исполнительным комитетом Совета и Временным комитетом Государственной Думы начались переговоры об образовании Временного правительства....
45163. Новая экономическая политика 30.19 KB
  Сущность НЭПа Сущность НЭПа была понятна не всем. При самом различном понимании НЭПа многие партийные деятели сходились в том что в конце гражданской войны в Советской России сохранилось два основных класса населения: рабочие и крестьяне а вначале 20 годов после ведения НЭПа появилась и новая буржуазия носительница реставраторских тенденций. Ленин понимал неизбежные противоречия опасности развития на пути НЭПа. Не отказываясь от конечной цели создания нерыночной системы экономики НЭПа большевики прибегли к использованию...