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

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


 

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

4261. Изучение системных средств языка ассемблер 15.42 KB
  Изучение системных средств языка ассемблер Цель работы: научиться работать в среде программирования Ассемблера Выполнение работы: 1. Для вызова редактора нажать клавиши SHIFT + F4. В редакторе набрать текст программы и затем сохранить с расширением ...
4262. Парадигмы программирования 37.57 KB
  Парадигмы программирования Парадигма программирования — это система идей и понятий, определяющих стиль написания компьютерных программ, а также образ мышления программиста. Развитие парадигм программирования Знакомое нам из курса философии слов...
4263. Разница между CPU и GPU в параллельных расчётах 68.36 KB
  Разница между CPU и GPU в параллельных расчётах Рост частот универсальных процессоров упёрся в физические ограничения и высокое энергопотребление, и увеличение их производительности всё чаще происходит за счёт размещения нескольких ядер в одном чипе...
4264. Области применения параллельных расчётов на GPU 257.34 KB
  Области применения параллельных расчётов на GPU. Чтобы понять, какие преимущества приносит перенос расчётов на видеочипы, приведём усреднённые цифры, полученные исследователями по всему миру. В среднем, при переносе вычислений на GPU, во многих зада...
4265. Возможности NVIDIA CUDA 17.64 KB
  Возможности NVIDIA CUDA Технология CUDA — это программно-аппаратная вычислительная архитектура NVIDIA, основанная на расширении языка Си, которая даёт возможность организации доступа к набору инструкций графического ускорителя и управления его ...
4266. Решения с поддержкой NVIDIA CUDA 71.41 KB
  Решения с поддержкой NVIDIA CUDA Все видеокарты, обладающие поддержкой CUDA, могут помочь в ускорении большинства требовательных задач, начиная от аудио- и видеообработки, и заканчивая медициной и научными исследованиями. Единственное реальное огран...
4267. Состав NVIDIA CUDA. Модель программирования CUDA 118.94 KB
  Состав NVIDIA CUDA CUDA включает два API: высокого уровня (CUDA Runtime API) и низкого (CUDA Driver API), хотя в одной программе одновременное использование обоих невозможно, нужно использовать или один или другой. Высокоуровневый работает «сверху» ...
4269. Программирование на С#. Методические указания к лабораторным работам. А.Ю. Демин, В.А. Дорофеев 2.25 MB
  А.Ю. Демин, В.А. Дорофеев. Программирование на С#. Томский политехнический университет. В пособии рассматривается введение в язык программирования С#, основные конструкции языка и типы данных, среда разработки visual Studio 2010, работа с базовыми элементами управления. Содержится указания и задания для выполнения лабораторных работ. Текстовый вариант предназначен для ознакомления. Полный обновленный вариант находится в файле который Вы можете скачать бесплатно.