53486

Процедура правого поворота для AVL дерева и ее особенности

Доклад

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

В 1962 году советские математики Адельсон-Вельский Г.М. и Ландис Е.А. предложили метод балансировки, требующий после включения или исключения узла лишь локальные изменения вдоль пути от корня к данному узлу, то есть времени не более O(log2n)

Русский

2014-04-01

41.46 KB

0 чел.

Процедура правого поворота для AVL дерева и ее особенности.

В 1962 году советские математики Адельсон-Вельский Г.М. и Ландис Е.А. предложили метод балансировки, требующий после включения или исключения узла лишь локальные изменения вдоль пути от корня к данному узлу, то есть времени не более O(log2n). При этом деревьям разрешается отклоняться от идеальной сбалансированности, но в небольшой степени, чтобы среднее время доступа к узлам было лишь немногим больше, чем в идеально сбалансированном дереве. Такие деревья называются АВЛ-деревьями.

Критерий сбалансированности АВЛ-дерева. Дерево называется сбалансированным тогда и только тогда, когда для каждого его узла высоты его левого и правого поддеревьев отличаются не более чем на единицу.

Примеры АВЛ-сбалансированных деревьев:

Примеры деревьев, не являющихся АВЛ-сбалансированными:Уровень 0

Балансировка выполняется с помощью действий, называемых поворотами узлов. Рассмотрим алгоритмы поворотов, используя указатели p, p1, p2 и считая, что p указывает на узел с нарушенной балансировкой.

Одинарный RR-поворот. Выполняется, когда <перевес> идет по пути R-R от узла с нарушенной балансировкой.

Двойной RL-поворот. Выполняется, когда <перевес> идет по пути R-L от узла с нарушенной балансировкой.

При включении узлов повороты выполняются для ближайшего узла к включенному с нарушенной балансировкой. То есть если после включения узла в дереве образуется несколько узлов с нарушенной балансировкой, поворот выполняется для того, который находится ниже (то есть ближе к включенному). После балансировки этого узла восстанавливается баланс и выше расположенных узлов.


 

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

78521. Основные аппаратные составляющие и перифирийные устройства компьютеров, их назначение, типы, принципы функционирования и характеристики 33 KB
  Процессор является основным вычислительным устройством ВМ в задачу которого входит исполнение находящейся в памяти машины программы. Процессор является основным вычислительным узлом ПК в задачу которого входят исполнение находящейся в памяти программы. сам по себе процессор и остальные элементы контроллеры памяти интерфейсы шины КЭШ память...
78522. Вычислительные системы: общие понятия, классификация, структурные схемы, характеристики 159.5 KB
  Одним из эффективнейших направлений развития вычислительной техники стало построение так называемых многомашинных вычислительных систем ММВС Принципиальным отличием ММВС от многопроцессорных ВМ является то что входящие в состав ММВС отдельные ВМ или и отдельные так называемые вычислительные модули ВМод включающие центральный процессор основную память интерфейсное устройство и возможно дисковую память имеют свою собственную основную память. Вычислительные машины или и вычислительные модули связываются между собой посредством...
78523. Понятие и классификация вычислительных сетей. Модель многоуровневого сетевого взаимодействия 27 KB
  COWS кластар рабочих станций NOWS сеть рабочих станций Основной классифицирующей характеристикой ВС является их масштабная территориальная характеристика: локальные вычислительные сети и глобальные вычислительные сети ГВС и региональные городские РВС. Сети отделов. Сети кампусов изначально преследовали цель объединения нескольких мелких локальных сетей в одну. Корпоративные сети в рамках одного предприятия.
78524. Физический уровень сетевых телекоммуникаций: общие понятия, типы и характеристики линий связи, методы передачи данных 27 KB
  Физический уровень сетевых телекоммуникаций: общие понятия типы и характеристики линий связи методы передачи данных Физ. В зависимости от типа физической среды передачи информации линии связи могут быть либо кабельными проводными либо беспроводными электромагнитные волны. в оптоволоконном кабеле для передачи данных используются световые импульсы. малую надежность передачи информации.
78525. Базовые сетевые технологии: стандарты, механизмы, характеристики 27 KB
  Под топологией компьютерной сети обычно понимают физическое расположение компьютеров сети относительно Друг Друга и способ соединения их линиями. Топология определяет требования к оборудованию тип используемого кабеля методы управления обменом надежность работы возможность расширения сети. Звезда: все компьютеры сети соединяются с центральным компьютером активная звезда при отсутствии центрального компьютера псевдо звезда. По сети непрерывно циркулирует маркер который имеет длину 3 байта и не содержит обычных данных.
78526. Конструирование путевых машин капитального ремонта пути 1007.73 KB
  От его работы зависит бесперебойная работа всех его секторов. Железнодорожный транспорт многоотраслевое хозяйство представлявшее собой огромный по протяженности конвейер бесперебойная и безаварийная работа которого зависит от функционирования каждой из его составных частей. Железнодорожный путь работает в самых сложных атмосферноклиматических условиях при постоянном воздействии динамической нагрузки от проходящих поездов. Для обеспечения указанных требований постоянно ведутся работы по усилению несущей способности и...
78527. Технология производства рабочей лопатки турбины 4.23 MB
  Одной из самых нагруженных деталью, ограничивающей межремонтный ресурс, являются неохлаждаемые лопатки турбины, изготавливаемые из деформируемого никелевого сплава ЭИ893. Лопатки из этого сплава из-за ограничений по длительной прочности имеют ресурс 48000 часов.
78528. Построение системы управления поставками и маркетинга для крупного металлургического холдинга «КарМет» 19.86 MB
  Традиционные информационные системы изначально были функциональной основой для множества организаций или функциональных сфер, но не могли объединять их в случае их географической распределенности. Одну и ту де информацию собирали многократно и во многих местах, и она была недоступна в реальном времени.
78529. Расчет и проектирование объемной гидропередачи привода рабочего органа дорожно-строительной машины 1.02 MB
  В настоящее время гидропривод широко применяется в авиационной, станкостроительной, тракторостроительной, металлургической и многих других отраслях промышленности. Гидропривод широко применяется также в тяжелых грузоподъемных машинах и самоходных агрегатах.