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

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

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

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

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


 

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

78366. Типы национальных хозяйственных систем 44.06 KB
  Национальные экономики открытого закрытого типа. Типы хозяйственных систем национальной экономики и критерии их разграничения. Хозяйственная система национальной экономики состоит из следующих основных элементов: социально-экономических определяющих специфику отношений между хозяйствующими субъектами по поводу собственности порядка владения и распределения основных экономических ресурсов и результатов экономической деятельности хозяйствующих субъектов...
78367. Структура национальной экономики 43.87 KB
  Структура национальной экономики. Структура национальной экономики: понятие сущность и виды. Теории структурных реформ национальной экономики.Инфраструктура экономики: виды и значение для национальной экономики.
78368. Система потенциалов национальной экономики 36.08 KB
  Система потенциалов национальной экономики. Виды совокупного экономического потенциала национальной экономики. Национальное богатство часть совокупного экономического потенциала национальной экономики. Совокупный экономический потенциал: понятие и сущность Основным направлением функционирования современной экономики РК ее реформирования является устранение сдерживающих факторов и активизация развития экономики.
78369. Домашние хозяйства, Фирмы и предпринимательство в Казахстане 35.42 KB
  Домашние хозяйства Фирмы и предпринимательство в Казахстане. Домашние хозяйства в экономической системе страны. Домашние хозяйства в экономической системе страны. В системе экономических отношений домашние хозяйства имеют исключительно важное значение поскольку они являются собственниками факторов производства находящихся в частной собственности.
78370. Государство в современном Казахстане и его функции 44.15 KB
  Производство общественных благ. Понятие сущность классификация общественных благ. Специфика потребления общественных благ. Условия эффективного обеспечения общественными благами в национальной экономике.
78371. Кинетика хемостимулированного окисления полупроводников (на примерах кремния и соединений AIIIBV) 29 KB
  Целью данной работы являлось установление механизма хемостимулирующего действия ванадия и его оксида на оксидирование GaAs и InP.
78372. Растровая графика. Растровые представления изображений 163.5 KB
  Количество цветов растрового изображения. Растровые изображения напоминают лист клетчатой бумаги на котором любая клетка закрашена либо черным либо белым цветом образуя в совокупности рисунок. растровая графика описывает изображения с использованием цветных точек пиксели расположенных на сетке. В частности изменение размеров растровой графики может привести к разлохмачиванию краев изображения поскольку пиксели будут перераспределяться на сетке.
78373. Векторная графика. Элементы (объекты) векторной графики. Объекты и их атрибуты 379 KB
  Достоинства и недостатки векторной графики. Элементы объекты векторной графики. Пример векторной графики В отличие от растровой графики в векторной графике изображение строится с помощью математических описаний объектов окружностей и линий. Ключевым моментом векторной графики является то что она использует комбинацию компьютерных команд и математических формул для объекта.
78374. Трехмерная графика. Программные средства обработки трехмерной графики 60 KB
  Вид поверхности определяется расположенной в пространстве сеткой опорных точек. Каждой точке присваивается коэффициент величина которого определяет степень ее влияния на часть поверхности проходящей вблизи точки. От взаимного расположения точек и величины коэффициентов зависит форма и гладкость поверхности в целом.