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

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

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

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

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


 

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

37538. Милетская школа, Фалес Милетский 51.22 KB
  Первый из ионических философов Фалес из Милета жил приблизительно в 640562 гг. Разносторонние познания Фалеса в области астрономии геометрии арифметики имели определенное влияние на развитие его философского мышления. Именно это и повлияло на взгляды Фалеса направленные на постижение сущности мира. Основой всего сущего Фалес считал воду.
37540. Философия и ее основные смыслы 35.46 KB
  То есть он имел в виду не благоприобретенное субъективное свойство человеческого ума а некое объективное качество разумно устроенного и гармоничного мира. Проследите становление ОВФ историческую роль категорий Смерть Жизнь Тело Душа Природа Дух Бог Бытие Мышление Материя Сознание Материальный мир Духовный мир как ступеней абстрагирования при постановке проблемы. Homo Spiens начинается с момента который может длиться веками когда он осознает себя как индивидуальность личность Я окруженную...
37541. Парменид – древнегреческий философ 14.91 KB
  Парменид рассуждает следующим образом: поскольку изменение происходят во времени и пространстве объект познания существует вне времени и пространства и следовательно не доступен для органов чувств: нет ничего в заблуждающихся умах кроме того что уже было в их заблуждающихся органах чувств. Например из апории Стрела следует летящая стрела в каждый момент времени имеет одно положение в пространстве и следовательно неподвижна. А если она неподвижна в каждый отдельный момент времени то и в сумме всех временных отрезков она...
37542. Первые философы. На какой вопрос они пытались ответить 14.11 KB
  В качестве первоосновы предлагалась одна из природных стихий или их сочетание вода земля огонь воздух. Анаксимандр в качестве первоначала всего сущего считает апейрон беспредельное. Можно считать что Анаксимандр в определенной степени отходит от натурфилософского обоснования первоначала и дает более глубокое его толкование полагая в качестве первоначала не какойлибо конкретный элемент например воду а признавая таковым апейрон материю рассматриваемую как обобщенное абстрактное первоначало приближающееся по своей сущности к...
37543. ЛОГИКА И МЕТОДОЛОГИЯ НАУКИ СТРУКТУРА НАУЧНЫХ РЕВОЛЮЦИЙ 1.08 MB
  Кун Логика и методология науки СТРУКТУРА НАУЧНЫХ РЕВОЛЮЦИЙ Перевод с английского И. То счастливое обстоятельство что я с увлечением прослушал пробный университетский курс по физике читавшийся для неспециалистов позволило мне впервые получить некоторое представление об истории науки. К моему полному удивлению это знакомство со старыми научными теориями и самой практикой научного исследования в корне подорвало некоторые из моих основных представлений о природе науки и причинах ее достижений. Я имею в виду те представления которые ранее...
37545. ОСНОВЫ ФИЛОСОФСКИХ ЗНАНИЙ. Учебно-методическое пособие 792 KB
  Природа человека и смысл его существования 104 Тема 14. В современном представлении философией называется область теоретических знаний о мире в целом о месте человека в нем и о принципах взаимоотношения человека с миром. Мировоззрение это целостный взгляд на мир и место в нем человека. В его структуру входят: знания о мире; ценности с позиций которых человек осмысливает мир; убеждения и идеалы которые определяют поступки человека.