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

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

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

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

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


 

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

26715. «Левый уклон» 15.02 KB
  Почти наверняка отказ от поддержки Абхазии Осетий и Приднестровья сложный вопрос так ли уж это убыточно но суть в том что сфера интересов России будет ужата. Возможно – размещение баз НАТО в России или даже вступление в блок если пустят. Потому что есть большие подозрения что ЕЭП ляжет тяжким бременем на экономику России а братская семья народов заставит еще более стремительно почернеть русские регионы. Благородный срединный путь Юмор ситуации в том что третьим пунктом нашей схемы должен был бы идти центризм но в роли...
26716. Мировой финансово – экономический кризис 27.56 KB
  Утверждение этой модели в качестве основной для мировой экономики сменило или серьезно поколебало философский смысл человеческого бытия. Кризис отвлек на некоторое время внимание мировой общественности от драматических событий на планете. Но уже в 20х числах сентября 2009 года из штаб квартиры ООН зазвучали предупреждения о природном апокалипсисе: убытки мировой экономики изза стихийных бедствий в 2008 году составили более 200 млрд.
26717. Геополитика 12.04 KB
  Геоэкономика в отличие от традиционной геополитики делает акцент на экономической мощи государства. Предмет изучения Основной объект изучения геополитики геополитическая структура мира представленная множеством территориальных моделей. Исследование механизмов и форм контроля над территорией одна из основных задач геополитики. Историческим ядром геополитики выступает география ставящая во главу угла исследование прямых и обратных связей между свойствами территории и балансом соперничеством или сотрудничеством мировых силовых полей.
26718. Основные направления и разделы геополитики 13.61 KB
  Геополитика будучи преимущественно политикой наоборот концентрирует свое внимание на политических явлениях и стремится дать географическую интерпретацию и анализ географических аспектов этих явлений. В рамках самой геополитики различают два достаточно четко обозначенных направления: геополитика предписывающая или доктринальнонормативная к ней можно причислить не боясь ошибиться всю немецкую школу связанную с именем Хаусхофера; геополитика оценочноконцептуальная типичные представители Маккиндер Спикмен Коэн. Геополитика...
26719. Сфера глобальных взаимоотношений между государствами 11.55 KB
  Сфера глобальных взаимоотношений между государствами является предметом анализа комплекса исторических наук истории внешней политики национальных государств взаимоотношений между отдельными государствами и группами государств дипломатической истории истории международных отношений имеющих устойчивую традицию. Третье понятие сфера международных отношений например экономические дипломатические политические военные идеологические позволяет определять предмет и направление исследования привлекать или отбрасывать те или иные...
26720. Русская геополитика 15.24 KB
  €œПериферийная модель€ помещает географическую ось истории в периферийную зону соприкосновения морских и континентальных держав концепция Rimland'а Н. €œЗональная модель€ помещает ключевой геополитический регион за который обречены бороться центры мировой силы в зоне умеренных и субтропических поясов Северного полушария. В реальности такая модель практически полностью повторяет предыдущую поскольку евразийская можно даже сказать – российская периферия по большей части совпадает с €œзоной конфликтов€. €œМондиалистская модель€...
26721. Основные категории современной геополитики 13.08 KB
  Одним из ключевых понятий геополитики является пространственнотерриториальный фактор. Геополитические процессы представляют собой исторические процессы формирования развития взаимодействия и распада субъектов геополитики. Одной из важнейших категорий геополитики является понятие субъекты геополитики.
26722. ИСТОЧНИКИ ГЕОПОЛИТИКИ 21.71 KB
  Исследование механизмов и форм контроля над территорией одна из основных задач геополитики. Историческим ядром геополитики выступает география ставящая во главу угла исследование прямых и обратных связей между свойствами территории и балансом соперничеством или сотрудничеством мировых силовых полей. Методологическим ядром геополитики при этом является моделирование на общепланетарном уровне хотя в составе этой научной дисциплины существуют и региональные и локальные разделы например исследование границ проблем спорных территорий...
26723. Биполяность и монополярность мира 15.56 KB
  Дополнительно предъявлялись следующие аргументы: только США обладают симметричным могуществом т. в военной экономической политической сферах одновременно; превосходство американской модели развития что было доказано успешной историей США и самое главное – победой в холодной войне; отсутствие у США сколь либо серьёзного конкурента. При этом никто не ставил под сомнение уникальные позиции США в мире.Кустарёв никто из экспертов не верит что США смогут навсегда остаться единственной сверхдержавой Вот образцовое суждение профессора...