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. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла

 

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

5839. Водопостачання та водовідведення. Конспект лекцій 4.8 MB
  Метою вивчення дисципліни є формування у майбутніх фахівців умінь і знань з сучасних методів проектування, будівництва та експлуатації систем водопостачання і водовідведення населених міст, житлових і промислових об'єктів...
5840. Організація і управління виробництвом. Конспект лекцій 343 KB
  Вступ Розвиток ринкових відносин, перебудова та вдосконалення господарського механізму змінюють вимоги до економічних методів управління, підвищують роль окремого спеціаліста-інженера - майбутнього організатора виробництва. Метою вивчення дисци...
5841. Методика викладання основ економіки. Конспект лекцій 374.79 KB
  Тема 1. Економічна освіта в системі економічної культури суспільства. Проблеми організації економічної освіти в Україні 1.1 Економічна освіта в системі економічної культури суспільства. 1.2 Проблеми організації економічної освіти в Україні 1.3...
5842. Управління програмами та проектами. Конспект лекцій 943 KB
  Тема 1. Загальна характеристика управління програмами та проектами Сутність проектної діяльності Посилення конкурентної боротьби, мінливість ринкового оточення будь-якої сучасної компанії чи організації потребують від них здатності швидко та е...
5843. Соціальна реабілітація інвалідів. Курс лекцій 444 KB
  Тема 1: Теоретичні основи соціальної реабілітації План 1.Наукові концепції соціалізації і інвалідизація. 2.Підходи до розуміння поняття інвалідності. 3. Роль соціальної реабілітації в процесі соціалізації. 1. Наукові концепції соціал...
5844. Теория линий влияния 109.5 KB
  Теория линий влияния 1. Линии влияния внутренних усилий в шарнирно консольной балке При расчете ряда сооружений (мостов, подкрановых балок и т.п.) приходится иметь дело с подвижной нагрузкой в виде проходящих поездов, автомобилей, мостовых кранов и ...
5845. Распорные системы 127 KB
  Распорные системы 1 Основные системы о трехшарнирных системах. Из прошлого к нам в строительство пришли ряд конструкций, целесообразность которых была проверена Веками Нашей Цивилизации. Одна из них Распорная система. С учетом работы распорной систе...