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

 

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

69164. Построение эпюр поперечных сил Q, изгибающих М и крутящих моментов Мz в сечениях крыла 696.5 KB
  Построение эпюр поперечных сил Q изгибающих М И крутящих моментов Мz В СЕЧЕНИЯХ КРЫЛА 8. Уравновешиваются эти нагрузки опорными реакциями rф крыла на фюзеляже рис. Площадь каждой iой трапеции численно равна приращению поперечной силы...
69166. Механизмы инвестирования и реинвестирования. Оценка бизнеса 97 KB
  По формам собственности инвестиции подразделяются: частные средства граждан предприятий негосударственной формы собственности неправительственных организаций; государственные финансируемые за счет бюджетных средств различных уровней государственными предприятиями...
69167. Системы налогообложения 114.5 KB
  Налоги оплата услуг государства за обеспечение гражданских прав и свобод граждан страны. Объект налогообложения событие вещь явление существование которых предполагает уплату соответствующего налога например наличие квартиры или наличие прав на земельный...
69168. Прогнозирование в проектах 181 KB
  Прогноз вполне понятно это продукт прогнозирования. объективная необходимость прогнозирования в условиях рыночной экономики обусловлена: Общественным характером производства; Усложнением межотраслевых и региональных связей...
69169. Механизмы управления рисками 145.5 KB
  Понятием риска характеризуется неопределенность связанная с возможностью возникновения в ходе реализации проекта неблагоприятных ситуаций и последствий. Таким образом четко заметна тесная связь риска вероятности и неопределенности.
69170. Механизмы ценообразования 118.5 KB
  Цены мощный рычаг управления экономикой хотя их реальные возможности воздействия на экономику вообще и на уровень жизни в частности намного меньше надежд возлагаемых на цены на ценовой механизм людьми. Это с одной стороны сами цены их виды структура величина динамика изменения...
69171. Проектное финансирование 128 KB
  На практике вклад акционеров в проект чаще осуществляется в виде внутренних займов, чем в виде вклада в уставный капитал. Распространено также реинвестирование прибыли, причем в последнее время в основном с помощью паевых инвестиционных фондов,...
69172. ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА ТЕХНОЛОГІЧНІ ПРОЦЕСИ ОБРОБЛЕННЯ ЕКОНОМІЧНОЇ ІНФОРМАЦІЇ 36.5 KB
  Інформаційна технологія ІТ це сукупність методів і процедур які реалізують функції збирання передавання оброблення зберігання та доведення до користувачів інформації в організаційноуправлінських системах з використанням обраного комплексу технічних засобів.