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

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


 

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

8882. Банківські ресурси як основа функціонування банку 106.5 KB
  Банківські ресурси як основа функціонування банку 1. Банківські ресурси, їх види та класифікація 2. Капітал банку, його склад, структура, джерела формування та напрями використання 3. Залучений капітал банку: суть, значення та загальна характеристик...
8883. Регулювання діяльності банків 101.45 KB
  Регулювання діяльності банків 1. Регулювання банківської діяльності, його суть та форми 2. Регулятивний капітал банку: призначення та порядок визначення 3. Економічні нормативи капіталу банку 4. Економічні нормативи ліквідності 5. Нормативи кредитно...
8884. Класифікація банківських операцій і послуг 78.62 KB
  Класифікація банківських операцій і послуг 1. Основи класифікації банківських операцій і послуг 2. Пасивні банківські операції та їх характеристика 3. Активні банківські операції та їх характеристика 4. Характеристика банківських послуг 1. Основи кл...
8885. Класифікація банківських і операцій і послуг Тестові завдання 23.5 KB
  Класифікація банківських і операцій і послуг Тестові завдання 1. Виберіть класифікацію банківських операцій за функціональними ознаками: а) кредитні, засновницькі, емісійні б) розрахунково-касові, інвестиційні, комісійні в) депозитні, міжбанківськ...
8886. Організація грошового обігу в банках 144.72 KB
  Організація грошового обігу в банках 1. Характеристика платіжного обігу 2. Банківське обслуговування готівкового обігу 3. Безготівкові розрахунки: суть, значення, класифікація та принципи організації 4. Характеристика міжбанківських розрахунків 5. С...
8888. Банківське кредитування як основа діяльності банку Тестові завдання 26.75 KB
  Банківське кредитування як основа діяльності банку Тестові завдання 1. Які з наведених тверджень найбільш повно відображають суть кредиту: а) надання грошей чи товарів у борг б) тимчасове користування позичальником цінностями кредитора в) механізм...
8889. Інвестиційна діяльність банків Тестові завдання 22.54 KB
  Інвестиційна діяльність банків Тестові завдання 1. Найбільш повно відображає зміст терміна інвестиції їх визначення а) будь-яке вкладення коштів (засобів), яке не призводить ні до зростання капіталу, ні до отримання прибутку б) короткострокове вкл...
8890. Банківське кредитування як основа діяльності банку 99.64 KB
  Банківське кредитування як основа діяльності банку 1. Суть, призначення та функції кредиту. Класифікація банківських кредитів 2. Порядок видачі та погашення банківських кредитів юридичним особам 3. Банківське споживче кредитування. 4. Форми забезпеч...