43960

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

Доклад

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

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

Русский

2014-03-31

16.14 KB

4 чел.

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

 

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

36886. Прилади магнітоелектричної, електродинамічної та електромагнітної систем 229 KB
  Мета роботи: Вивчення будови принципу дії приладів магнітоелектричної електродинамічної та електромагнітної системи та методами їх використання. Завдання: Ознайомитись з призначенням та областю використання приладів магнітоелектричної електродинамічної та електромагнітної систем. Вивчити принцип дії приладів та методику їх використання. Ознайомитись із властивостями та технічними характеристиками приладів.
36887. Дослідження простої випадкової вибірки за допомогою функції «Выборка» Microsoft Excel 16.4 KB
  Загальні відомості Процедура отримання простої випадкової вибірки проілюстрована на наступному прикладі. Побудова простої випадкової вибірки здійснюється у такій послідовності: Генеральна сукупність – дані таблиці 1. Основа вибірки – нумерація елементів таблиці.
36888. Ознайомитись з основними командами програмного симулятора dScope-51 56.5 KB
  1 При введенні команд перед командою ставиться SM без нього введення команди не відбудеться. Всі команди проводяться через акумулятор А Основні команди симулятора: DD – додавання; SUBB – віднімання; CPL – інверсія; RL – зсув вліво на один; RR – зсув в право на один; XCH – обмін; CJNE – порівняння; CLR – встановлення нулів; DEC – віднімання від регістра одиниці; INC – додавання до регістру одиниці; h ставиться в кінці вводу команди для того щоб показати що число вводиться в шістнадцятирічній СЧ; означає що ми вводимо до...
36893. Дослідження тиристорів за допомогою програмного комплексу Electronics Workbench 72.5 KB
  Дослідження прямої гілки ВАХ тиристора можна проводити з використанням схеми на рис. Рисунок 4 Схема для побудови прямої гілки ВАХ тиристора в режимі фіксованих струмів анода Рисунок 5 Схема для побудови прямої гілки ВАХ тиристора в режимі фіксованих струмів керувального електрода Порядок виконання роботи 1. Рисунок 6 Схема для лабораторного дослідження тиристора 5. В результаті момент відкриття тиристора зміщується в часі і залежить від величини резистора.