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Поворачиваем ребро, связывающее кореньи его правый дочерний узел, влево.

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

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

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

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


 

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

64536. Теории происхождения государства и права 36 KB
  Изучение процесса происхождения государства и права имеет не только теоретическое. Изучение процесса происхождения государства и права позволяет понять социальную сущность государства установить место и роль государства в жизни общества.
64537. ОСОБЕННОСТИ РАЗВИТИЯ СТРАН АЗИИ И АФРИКИ. ЯПОНИЯ В 20—30-е ГОДЫ 20.88 KB
  Влияние войны и революции в России на страны Азии и Африки. В зоне военных действий оказались страны Ближнего Востока в армиях Антанты участвовали солдаты ряда колоний. Страны Азии и Африки составляли важный резерв сырья и продовольствия а также рабочей силы.
64538. ОБЩЕТЕОРЕТИЧЕСКИЕ АСПЕКТЫ БЕЗОПАСНОСТИ ЖИЗНЕДЕЯТЕЛЬНОСТИ 66.5 KB
  Под безопасностью понимают состояние деятельности при котором с достаточной вероятностью исключено проявление опасностей или отсутствие явной опасности. Количественной оценкой опасности служит риск который определяется как частота или вероятность появления...
64539. Возникновение понятия «маркетинг». Исторические концепции маркетинга 69.87 KB
  Суть концепции Любой товар будет пользоваться спросом если он доступен по цене и широко представлен на рынке. Особенности концепции Деятельность фирмы ориентирована только на возможности производства не на потребности общества.
64540. Правовой статус Великого княжества Финляндского(ВКФ) и Царства Польского (ЦП) на этапе вхождения данных территорий в состав Российской империи 18.47 KB
  На момент вступления ВКФ в состав РИ финский этнос представлял собой малый молодой крестьянский этнос изза гнета Швеции национальная элита так и не сформировалась население исповедовало лютеранство что объясняло почти 100 грамотность населения...
64541. Основа национальной политики царизма и ее особенности на рубеже XIX – XX веков 54 KB
  На протяжении всей истории, Россия руководствовалась 6 принципами национальной политики, которые выражаются в: сотрудничестве с национальными элитами и стремление растворить...
64542. Система права. Отрасль права, правовой институт, норма права 27.5 KB
  С давних времен существует деление права на публичное и частное. Публичное право регулирует отношения, в которых хотя бы одной из сторон является государство.
64543. Индивидуальный пошив – удобно, качественно и очень красиво 51 KB
  Индивидуальный пошив одежды на заказ сейчас выбирает все больше и больше людей. И дело не только в индивидуальном стиле и высоком качестве, но и в цене пошива.
64544. Великая французская революция и развитие международных отношений 15.86 KB
  К концу 1780-х гг. выявился кризис внешней политики Франции: неудачи в соперничестве с Англией в колониях, уменьшение влияния в Германии и Польше. В предреволюционный период ведущие страны пытались разрешать спорные вопросы мирным путём...