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

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


 

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

10788. Модели жизненного цикла ПО 48 KB
  Модели жизненного цикла ПО Стандарт ISO/IEC 12207 не предлагает конкретную модель ЖЦ и методы разработки ПО под моделью ЖЦ понимается структура определяющая последовательность выполнения и взаимосвязи процессов действий и задач выполняемых на протяжении ЖЦ. Модель ЖЦ зав...
10789. Каскадная модель ЖЦ ПО 62.44 KB
  Каскадная модель ЖЦ ПО Классическая каскадная модель несмотря на полученную в последнее время негативную оценку исправно служила специалистам по программному инжинирингу многие годы. Понимание ее сильных сторон и недостатков улучшает оценочный анализ других зачаст...
10790. Спиральная модель ЖЦ ПО 62.61 KB
  Спиральная модель ЖЦ ПО Спиральная модель воплощает в себе преимущества каскадной модели. При этом в нее также включены анализ рисков управление ими а также процессы поддержки и менеджмента. Здесь также предусмотрена разработка программного продукта при использовани...
10791. Диаграммы потоков данных DFD 31.51 KB
  Диаграммы потоков данных DFD В основе данной методологии методологии Gane/Sarson [11] лежит построение модели анализируемой ИС проектируемой или реально существующей. В соответствии с методологией модель системы определяется как иерархия диаграмм потоков данных ДПД или D...
10792. Общие требования к методологии и технологии проектирования 23.16 KB
  Общие требования к методологии и технологии проектирования Методологии технологии и инструментальные средства проектирования CASEсредства составляют основу проекта любой ИС. Методология реализуется через конкретные технологии и поддерживающие их стандарты метод
10793. Подход RАD. Стадии планирования требований и проектирования 18.62 KB
  Подход RАD. Стадии планирования требований и проектирования. Одним из возможных подходов к разработке ПО в рамках спиральной модели ЖЦ является получившая в последнее время широкое распространение методология быстрой разработки приложений RAD Rapid Application Development. Под этим ...
10794. Разработка системы управления технологическим процессом на базе контроллера Siemens Logo 1.29 MB
  Разработка системы управления технологическим процессом на базе контроллера Siemens Logo Реферат Курсовой проект содержит 46 страниц 21 рисунков 12 таблиц 11 источников 3 приложения 2 листа графического материала вынесенного в приложения. Ключевые слова: автомати
10795. Розвиток і розміщення туристичного комплексу Франції 1.46 MB
  Курсова робота з курсу Розміщення продуктивних сил на тему: Розвиток і розміщення туристичного комплексу Франції Вступ Туризм відіграє одну з головних ролей в світовій економіці забезпечуючи десяту частину світового валового національного прод
10796. Особливості розвитку і розміщення туристичного комплексу Туреччини 79.5 KB
  Курсова робота з дисципліни Маркетинг Особливості розвитку і розміщення туристичного комплексу Туреччини Вступ3 1. Сутність значення і місце рекреаційнотуристичного комплексу в господарстві5 2. Передумови розвитку і розміщення рекреаційнотуристичного к