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

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

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

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

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


 

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

44644. Художественное моделирование из бумаги. Оригами по спирали 20.31 KB
  Цель: формирование практических навыков по выполнению оригами по спирали Задачи: 1.образовательные: Познакомить с технологией оригами по спирали развивающие: развивать логическое мышление развивать творческое воображение; воспитательные: воспитывать трудолюбие аккуратность дисциплинированность Оборудование: Для учителя: наглядный материалаппликация Для учащихся: нитки карандаш ножницы клей картон Оформление...
44645. Собственные и нарицательные имена существительные. Заглавная буква в именах существительных 19.77 KB
  Кто может еще что то добавить к этому правилу Потренируемся каждый из вас назовет свое собственное имя и так же нарицательное. пример: я учительница Бякова Наталья Сергеевна учительница нарицательное Бякова Наталья Сергеевна собственное я студентка нарицательное Наташа собственное. Нарицательных имен у вас может быть несколько но запомните собственное не изменно. подобрать собственное имя.
44646. Собственные и нарицательные имена существительные 21.1 KB
  Орг момент Отгадаем ребус: отец Какие орфограммы встречаются в этом слове Можем ли мы ее проверить Значит это слово словарное. на какие вопросы оно отвечает на какие две большие группы мы можем поделить и. сущ Как отличить Еще на какие чем они отличаются Какие группы слов мы пишем с заглавной буквы фронтальный опрос и. Прочитай1 ученик устно какие группы слов могут быть собственными.
44648. Имена существительные - названия явлений природы и качеств людей 20.63 KB
  Имена существительные названия явлений природы и качеств людей. Тип урока: комбинированный ФОУД: фронтальная индивидуальная групповая Дидактическая цель: создать условия для систематизации знаний учащихся по теме Имя существительное Задачи: 1.Образовательные: познакомиться с лексическим значением групп существительных; находить отличительные особенности групп; учиться использовать их в своей речи; 2. О какой части речи это стихотворение Что такое имя существительное им.
44649. Единственное и множественное число имен существительных 19.43 KB
  Образовательные: систематизировать и углубить знания об именах существительных единственного и множественного числа; учить находить имена существительные единственного и множественно числа в тексте и подбирать их самостоятельно; учить классифицировать имена существительные единственного и множественного числа; отрабатывать умения изменять имена существительные по числам. Даны существительные в единственном числе преобразовать в существительные множественного числа. Даны существительные во множественном числе преобразовать в...
44650. Единственное и множественное число имен существительных 19.98 KB
  Минутка чистописания: пропишем ее три раза 1 человек у доски 1 букву с комментированием пропишем соединение буквы т с буквой о в тетради 3 раза1 человек на доске с комментированием запишем все словарное слово в н. мн ед ч по смыслу умения находить слова мн ед ч и правильно определят чила имен сущ. доске записаны слова сосны с_сна хлеба хле_ грибы гри_ травы тр_ва горы г_ра Что заметили По какому признаку слова записаны в два столбика Запишем первое слово из второго столбика1ч к доске ост. Как мы ее можем проверить С...