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

 

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

65439. Закономірності гідромеханічних процесів утилізації твердих відходів содового виробництва 4.99 MB
  Вирішенням проблеми позбавлення шкідливої дії відходів содових виробництв може стати їх накопичування у підземних порожнинах які утворюються в процесі вилуговування солі у відпрацьованих розсільних свердловинах.
65440. ПРОФЕСІЙНА ПІДГОТОВКА МАГІСТРІВ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ В СИСТЕМІ ДИСТАНЦІЙНОЇ ОСВІТИ США 232.5 KB
  Стрімкий розвиток інформаційних та телекомунікаційних технологій, активізація інтеграційних процесів у вищій освіті, глобалізація світової економіки, модернізація виробництва, динамічні зміни на ринку праці зумовлюють потребу у фахівцях-професіоналах...
65441. БІОЛОГІЧНЕ ОБГРУНТУВАННЯ ВАЖЛИВІШИХ ЕЛЕМЕНТІВ ТЕХНОЛОГІЇ ВИРОЩУВАННЯ НАСІННЯ КОРІАНДРУ СОРТУ НЕКТАР В КРИМУ 877 KB
  Індивідуальний розвиток ефіроолійних рослин і зокрема коріандру є загально відомим проте циклічна схема онтогенезу і вегетаційного періоду для коріандру не розроблені не досліджені закономірності формування насіння що не дає можливості...
65442. ПІДВИЩЕННЯ ПРОДУКТИВНОСТІ ОБРОБКИ ДЕТАЛЕЙ У ВІБРУЮЧИХ КОНТЕЙНЕРАХ ШЛЯХОМ ВИБОРУ ФОРМИ ІНСТРУМЕНТУ 323 KB
  Відповідно до цього актуальною науковопрактичною задачею стосовно вібраційної обробки є розробка рекомендацій що сприяють підвищенню її продуктивності за рахунок розробки та дослідження інструменту одиничних абразивних...
65443. Експериментальні методи оцінки часової та функціональної ефективності алгоритмів у програмно-апаратних середовищах 922.5 KB
  Переважна більшість теоретичних досліджень з аналізу алгоритмів ґрунтується на аспекті представлення алгоритмів і не враховує особливостей сучасних засобів їх виконання. Можна виділити три основні підходи до аналізу алгоритмів.
65444. МІЦНІСТЬ ЗАЛІЗОБЕТОННИХ ПЛИТ ПРИ ПРОДАВЛЮВАННІ ШТАМПАМИ РІЗНОЇ ГЕОМЕТРІЇ 7.21 MB
  У сучасному будівництві все більше поширення отримують монолітні залізобетонні будинки з безригельним безкапітельним каркасом коли плоскі плити перекриттів постійної товщини опираються безпосередньо на колони.
65445. ПРАВОВЕ РЕГУЛЮВАННЯ ПЕНСІЙНОГО ЗАБЕЗПЕЧЕННЯ СУДДІВ В УКРАЇНІ 163 KB
  Одним із перших змін у спеціальному пенсійному законодавстві зазнало пенсійне забезпечення суддів у звязку із прийняттям Закону України Про судоустрій і статус суддів. Законом України Про судоустрій і статус суддів закріплено...
65446. ГІГІЄНІЧНА ОЦІНКА ОСОБЛИВОСТЕЙ ХАРЧУВАННЯ МОЛОДШИХ ШКОЛЯРІВ У ЗАГАЛЬНООСВІТНІХ НАВЧАЛЬНИХ ЗАКЛАДАХ РІЗНОГО ТИПУ 368 KB
  У сучасних соціальноекономічних реаліях життя в Україні коли змінюються умови навчання дітей та виникають його нові форми і програми дослідження з вивчення харчового статусу дитячого населення України з метою його корекції є вкрай актуальним але недостатньо вивченим...
65447. ТЕРИТОРІАЛЬНА ОРГАНІЗАЦІЯ ВИЩОЇ ОСВІТИ УКРАЇНИ 352.5 KB
  Оцінка впливу чинників на сучасний стан вищої освіти; Дослідження регіональних особливостей вищої освіти; Визначення відповідності розвитку вищої освіти рівню розвитку регіону Аналіз територіальної структури вищої освіти тенденцій її розвитку Типізація регіонів України...