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

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

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

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

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


 

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

35574. ТЕОРИЯ ЭЛЕКТРИЧЕСКОЙ ТЯГИ 3.27 MB
  Построить электромеханические характеристики на ободе колеса VI FI I для всех схем соединений двигателей и всех степеней ослабления поля используя нагрузочные характеристики характеристики магнитных и механических потерь характеристику потерь мощности в механической передаче. Режим пуска нанести на электромеханические характеристики двигателя VI на ободе колеса. Построить тяговые характеристики поезда FV для всех режимов включения двигателей. Нанести на эти характеристики ограничения по сцеплению максимальной скорости и...
35576. Проектирование и эксплуатация газо- и водоочистки 1.88 MB
  Более того десульфурацию проводили вдувая каустическую соду в контур охлаждающей воды рис. В процессе Эрфайн можно выделить три основные стадии: охлаждения отделения пыли и обработки воды. Крупные частицы фракцией 10мкм удаляются в результате вспрыскивания распыленной циркуляционной воды в противоток отходящему газу посредством форсунок работающих на одном виде жидкости. На стадии обработки воды взвешенные твердые частицы и тяжелые металлы удаляют из сбросовых стоков данного процесса в установке обработки воды в три этапа: отделяют...
35577. АНТИПРИГОЖИН. УПРАВЛЯЕМЫЙ ХАОС 1.69 MB
  Вместо физического времени в ней использовался обратимый эрзац. Человек будучи вне времени становится богоподобным или намного ближе к квазибожественному состоянию.Ньютон же считал что вмешательство бога требуется в каждый момент времени отсюда эпигенез и гениальное предвидение И. Это вернуло прежний интерес к конструктивной роли времени.
35578. Социология. Курс лекций в схемах 2.05 MB
  Предмет и история социологии. Общество как социокультурная система. Социальные группы и общности. Массовое сознание и общественное мнение. Методология социологических исследований.
35579. История Белоруссии 492 KB
  В истории Белоруси выявлено много белых пятенБНРВКЛсоздание БССР и т.Полоцкая земля находилась на терр сев Белорусии в землях кривичейвключала в себя современную Вит обл.На границе 1314в Полоцкое княжество вошло в состав ВКЛ.В конце 13начале14 веков Туровская земля была включена в состав ВКЛ.
35580. История беларускiх зямель 228.5 KB
  Тэрмiн зясялення тэрыторыi Беларусi – 40 тыс. Iндаеўрапейскi перыяд пачаўся ў бронзавым веку з часу рассялення iндаеўрапейскiх плямён на тэрыторыi Беларусi 3 2 тыс. Засяленне славянамi Беларусi адбывалася ў вынiку мiграцыi славян са сваёй прарадзiмы – тэрыторыi памiж р. Славяне асiмiлiравалi балтаў i ў вынiку славянабалцкага ўзаемадзеяння ўзнiклi новыя этнiчныя супольнасцi: ва ўсходняй Еўропе больш за 15 на тэрыторыi Беларусi – 3 гэта крывiчы дрыгавiчы радзiмiчы.
35581. История Руси от древних времен до ХХ столетия 221 KB
  Древние славяне - большая этническая группа: Восточные (русские, украинцы, белорусы); Западные (Чехи, Поляки); Южные (болгары, сербы, хорваты, македонцы). Соседи с севера: угро-финские племена, норманны, балты. С норманнами были напряженные отношения т.к. они промышляли грабежами, плавали во Францию, Испанию, Италию. Славяне часто платили им дань.
35582. АДМИНИСТРАТИВНОЕ ПРАВО КАК ОТРАСЛЬ ПРАВА 138.5 KB
  Административное право как отрасль современного права появилась тогда когда в правовой системе достаточное место заняли нормы закрепляющие права личности гарантии от административного произвола. Реализация в законодательстве идей естественных и неотъемлемых прав гражданина разделения властей контроля за государственной администрацией необходимое условие превращения полицейского права в административное. Административное право очень важная отрасль права так как роль государственной администрации в России очень велика.