43960

Выбор и обоснование структуры данных для алгоритма построения AVL дерева

Доклад

Информатика, кибернетика и программирование

АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так. Следует заметить, что сбалансированные деревья очень эффективны для поиска.

Русский

2014-03-31

16.14 KB

5 чел.

Выбор и обоснование структуры данных для алгоритма построения AVL дерева Высотой некоторого бинарного дерева является максимальный уровень его листьев. Баланс некоторого узла определяется как высота его левого поддерева минус высота его правого поддерева.

Дерево называется сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.

АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так. Следует заметить, что сбалансированные деревья очень эффективны для поиска. Предположим у нас сбалансированное дерево и упорядоченное бинарное дерево, которое вырождено, оба эти дерева содержат 10000 узлов. Так, например, упорядоченном бинарном дереве следует просмотреть 9999 уровней дерева прежде, чем он найдет самый крайний правый узел, а сбалансированном дереве 8 уровней.

Возможны 3 случая:

  1. hL = hR: L и R становятся неравной высоты, но критерий сбалансированности не нарушается
  2. hL < hR: L и R приобретают равную высоту, т.е. сбалансированность даже улучшается
  3. hL > hR: критерий сбалансированности нарушается, и дерево нужно трансформировать, такая перестройка называется поворотом.

Поворот должен удовлетворять следующим требованиям:

  1. Прохождение трансформированного дерева в симметричном порядке должно быть таким же, как и для первоначального дерева (т.е. трансформированное дерево должно оставаться деревом бинарного поиска)
  2. Трансформированное дерево должно быть сбалансированным

Одинарный поворот вправо происходит тогда, когда родительский узел Р и его левый сын LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывая правое поддерево узла LC (ST) присоединяется к Р в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла Р. Поворот уравновешивает как родителя, так и его левого сына.

Двойной поворот вправо происходит тогда, когда родительский узел (Р) становится перевешивающим влево, а его левый сын (LC) - перевешивающим вправо. NP - корень правого перевешивающего дерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.

Процесс включения узла состоит из последовательности таких 3 этапов:

  1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве
  2. Включить новый узел и определить новый показатель сбалансированности
  3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла

 

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

30654. Почему для Катерины невозможен путь Варвары? (По пьесе А.Н. Островского «Гроза») 13.29 KB
  Представительницами двух миров старого и нового являются в пьесе Катерина и Варвара. Но при всей своей хитрости приспособляемости и нравственной убогости Варвара не смогла вынести домашней тирании. Варвара бы так никогда не поступила.
30655. Поэма Н.А. Некрасова «Кому на Руси жить хорошо» как движущаяся панорама народной жизни 14.57 KB
  Некрасова Кому на Руси жить хорошо как движущаяся панорама народной жизни.Большую часть поэмы Некрасов посвящает обзору именно народной жизни ведь главным героем произведения является русский народ.Уже в первой главе Поп создаются масштабные картины народной жизни. Из рассказа попа мы узнаем не только о жизни духовного сословия в России после отмены крепостного права но и бедственном положении большинства крестьянских семей не способных заплатить священнику за его работу.
30656. Чем отличается народное и барское представление о счастье? (По поэме Н.А. Некрасова «Кому на Руси жить хорошо») 16.89 KB
  Некрасов остро ставит вопрос о счастье.Счастливых людей трудно найти потому что у каждого свое представление о счастье. Таким образом представление о счастье у крестьян напрямую связано с общественной иерархией.
30657. Предыстория героя как способ характеристики героя в произведениях отечественной классики XIX века 12.52 KB
  Так показав детство главного героя Гончаров раскрыл суть всего крепостного уклада калечащего жизни дворянского класса.
30658. Каковы главные причины «лежания» Ильи Ильича Обломова? (По роману И.А.Гончарова «Обломов») 13.12 KB
  Именно такая жизнь для Обломова является идеальной поэтому герой не принимает петербургскую жизнь для него она холодна и лишена души. Ничегонеделание Обломова это своеобразный протест и отрицательное отношение к жизни и интересам современных герою людей.Штольц пытается вывести Обломова из апатичного состояния знакомит его с Ольгой Ильинской.
30659. Роль пейзажа в произведениях отечественной литературы 13.54 KB
  Так например в повести Бедная Лиза Карамзина живописные картины природы на первый взгляд можно счесть случайными эпизодами которые являются всего лишь красивым фоном для основного действия. Таким образом здесь описание природы служит для выражения авторской позиции. Здесь картина природы раскрывает не только душевное состояние Лизы но и предвещает трагичный финал данной истории. Его характер отражается в принадлежащих ему описаниях природы Фаталист Тамань Княжна Мери.
30660. Сны героев. Их художественная функция в произведениях отечественной литературы 12.95 KB
  Так сон Татьяны в Евгении Онегине заключает в себе идею о близости героини к народу. Татьяна исключительно романтическая натура что и доказывает её сон. Во многом сон носит символический характер таким образом автор переплетает народные представления о сне образ ручья медведя леса и т. Иной характер носит сон Обломова Гончаров Обломов в котором герой видит свою родную деревню и свое детство.
30661. Русский характер в очерке Н. Лескова “Леди Макбет Мценского уезда” 14.73 KB
  Леди Макбет Мценского уезда история трагической любви и преступлений Катерины Измайловой. В картинах любви гармонию нарушает вдруг вторгшийся разлад: возлюбленный то думает о деньгах. Героиня обезумела от любви и готова сделать все что угодно чтобы только Сергей был доволен. Признаваясь что не любил Катерины Львовны никогда Сергей пытается отнять то единственное что составляло жизнь Измайловой прошлое ее любви.
30662. Русский характер в очерке Н. Лескова Леди Макбет Мценского уезда 15.62 KB
  Леди Макбет Мценского уезда история трагической любви и преступлений Катерины Измайловой. Да и чувство Катерины Львовны не может быть свободным от инстинктоз собственнического мира и не попадать под действие его законов. И вместе с тем слепая страсть Катерины неизмеримо больше значительнее чем корысть Сергея. Признаваясь что не любил Катерины Львовны никогда Сергей пытается отнять то единственное что составляло жизнь Измайловой прошлое ее любви.