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

 

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

21705. Технология личностного ориентирования в географии 103.5 KB
  Содержание личностно-ориентированного образования, его средства и методы структурируются так, что позволяют ученику проявить избирательность к предметному материалу, его виду и форме, в этих целях разрабатываются индивидуальные программы обучения, которые моделируют исследовательское мышление.
21706. Методы экспертного оценивания 136 KB
  5] Анализ компетентности экспертов по взаимооценкам [0.6] Анализ компетентности экспертов по оценкам объектов [0. Типичные ситуации группового выбора: распределение конкурсной комиссией поощрений; обсуждение и согласование нескольких альтернативных законопроектов; ранжирование по перспективности внедрения образцов новых промышленных изделий производимое группой экспертов. Например для 3х объектов предпочтение одного из экспертов или он может количественно выразить интенсивность ; ; .
21707. Разделы модуля «Базовые понятия. Методы извлечения знаний» 368 KB
  Методы извлечения знаний [1] История и этапы развития искусственного интеллекта [2] Подходы к созданию систем искусственного интеллекта [3] Искусственный интеллект в России [4] Направления развития искусственного интеллекта [5] Основные определения [6] Методы извлечения знаний [7] Классификация методов извлечения знаний [8] Пассивные методы [9] Наблюдения [10] Анализ протоколов мыслей вслух [11] Лекции [12] Активные методы [13] Активные индивидуальные методы [14] Анкетирование [15] Интервью [16] Свободный диалог [17] Активные групповые методы...
21708. Модуль Жизненный цикл интеллектуальной системы 147.5 KB
  2] Этап 2: Разработка прототипной системы [1.4] Этап 4: Оценка системы [1.5] Этап 5: Стыковка системы [1.
21709. Модуль Методы представления знаний: Нечеткая логика 192 KB
  Математический аппарат Характеристикой нечеткого множества выступает функция принадлежности Membership Function. Обозначим через MFcx – степень принадлежности к нечеткому множеству C представляющей собой обобщение понятия характеристической функции обычного множества. Значение MFcx=0 означает отсутствие принадлежности к множеству 1 – полную принадлежность. Так чай с температурой 60 С принадлежит к множеству 'Горячий' со степенью принадлежности 080.
21711. Оценка вероятностей возможных последствий от нарушений электроснабжения потребителей 181.5 KB
  Оценка вероятностей возможных последствий от нарушений электроснабжения потребителей Для решения широкого класса задач эксплуатации и проектирования с учётом фактора надёжности необходимо определение вероятностей возникновения возможных последствий от нарушения электроснабжения потребителей которые сводятся к следующим: вероятность возникновения катастрофических и аварийных ситуаций исследование которых необходимо для нормирования надёжности электроснабжения; вероятность возникновения отдельных составляющих ущерба их величина и...
21712. ИСПЫТАНИЯ НА НАДЕЖНОСТЬ ЭМС. КОНТРОЛЬНЫЕ ИСПЫТАНИЯ 2.49 MB
  Показатели надежности экспериментальными методами могут быть получены по результатам либо испытаний – специальных или совмещенных либо наблюдением за функционированием объекта в условиях эксплуатации. Методы испытаний организуются специально с целью определения показателей надежности объем их обычно заранее планируется условия функционирования объектов устанавливаются исходя из требований оценки конкретных показателей. Показатели надежности таких объектов оцениваются в основном либо по результатам совмещенных испытаний при которых...
21713. СТАТИСТИЧЕСКИЕ МЕТОДЫ ОЦЕНКИ, АНАЛИЗА И КОНТРОЛЯ НАДЕЖНОСТИ 358.5 KB
  Сбор информации об отказе элементов технических систем В общем комплексе мероприятий по обеспечению надёжности любого изделия сбор статистической информации об отказах и оценка показателей надёжности в условиях эксплуатации являются последним заключительным этапом. При этом появляется возможность оценить реальные значения показателей надежности и следовательно оценить эффективность мероприятий по обеспечению надёжности на всех этапах – проектирование производство испытания монтаж эксплуатация. Поэтому особое значение приобретает вопрос...