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 от узла с нарушенной балансировкой.

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


 

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

3006. Двигатели трехфазные асинхронные напряжением свыше 1000 В для механизмов собственных нужд тепловых электростанций 84 KB
  Настоящий стандарт распространяется на двигатели трехфазные асинхронные (далее — двигатели) с короткозамкнутым ротором, мощностью 200 кВт и более, напряжением 1000 В и выше, частотой 50 и 60 Гц, односкоростные и двухскоростные, предназначенные...
3007. Основы объектно-ориентированного проектирования 238.5 KB
  Цель курса – освоение принципов объектно-ориентированного проектирования и методов объектно-ориентированного программирования с использованием языка С++. Если на компьютере установлена ОС Windows – в курсе рассматриваются примеры п...
3008. Суть и процесс реформ Бальцеровича в Польше 114.5 KB
  Как делаются реформы После краха коммунизма перед экономистами большинства стран бывшего Советского Союза встали устрашающе трудные задачи. Им пришлось отказаться от единой системы цен - искаженных цен - которая господствовала при коммунизме, перейдя...
3009. Коммерческая тайна банков 101 KB
  Вопросы правового регулирования общественных отношений по поводу использования и распространения информации в целом и отдельных ее видов в частности в последнее время занимают одно из значительных мест в юридической литературе. Среди них, несомнен...
3010. Моделирование электропотенциального поля в проводящей среде 42.59 KB
  Используя экспериментальные данные, полученные при моделировании электропотенциального поля в проводящей среде, найти пересечения эквипотенциальных поверхностей Ui, соответствующих значениям U1 = 1,500 B, U2 = 0,160 B и U3 = 0.104 В, с осями х, у и ...
3011. Изучение типов потребителей по психографическому признаку 181.5 KB
  Любой рынок с точки зрения маркетинга состоит из покупателей, которые отличаются друг от друга по своим вкусам, желаниям, потребностям и, главное, приобретают товары исходя из разных мотиваций. Поэтому предприниматель должен понимать, что п...
3012. Интегрированные стратегии коммуникаций предприятий различных типов на примере United Airlines 247.5 KB
  В настоящее время в распоряжении маркетолога имеется огромный арсенал различных маркетинговых коммуникационных инструментов: пресса, радио, телевидение (наземное, спутниковое, кабельное и интерактивное с видеотекстом), телефон, почта, е-мейл и Интер...
3013. BIOS и строение программной части компьютера 70.5 KB
  Составные части BIOS. BIOS - Базовая система ввода-вывода (Basic Input Output System) называется так потому, что включает в себя обширный набор программ ввода-вывода, благодаря которым операционная система и прикладные программы мо...
3014. Бридж - карточная игра 174.5 KB
  Бридж – сравнительно молодая игра. Она сформировалась в несколько этапов (бридж-вист, бридж-аукцион, бридж-плафон, контракт-бридж) в конце XIX – начале XX века на основе русской карточной игры винт и английской карточной...