53488

Процедура вставки вершин в AVL дерева и ее особенности

Доклад

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

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

Русский

2014-04-01

19.29 KB

0 чел.

Процедура вставки вершин в AVL дерева и ее особенности.

Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Николасом Виртом в «Алгоритмы и структуры данных»):

  1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
  2. Включения новой вершины в дерево и определения результирующих показателей балансировки.
  3. «Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка.

Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl — высота левого поддерева, hr — высота правого поддерева } Включение вершины в левое поддерево приведет к

  1. hl < hr: выравняется hl = hr. Ничего делать не нужно.
  2. hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
  3. hl > hr: теперь hl — hr = 2, — требуется балансировка.

В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.


 

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

12011. Система оценки финансового состояния деятельности коммерческого банка 454.94 KB
  СОДЕРЖАНИЕ Введение 1. Финансовое состояние коммерческого банка и организационнометодическое обеспечение его оценки 1.1 Финансовое состояние банка и факторы его определяющие 1.2 Организационные основы оценки финансового состояния банка 1.3 Направления оценки ф...
12012. Теория и методология формирования и реализации кредитования под залог земель сельскохозяйственного назначения. 844.85 KB
  СОДЕРЖАНИЕ ВВЕДЕНИЕ ГЛАВА 1 Теоретические основы земельноипотечного кредитования 1.1 Земельная ипотека: ретроспективный анализ 1.2 Экономическая сущность основные понятия и отличительные черты земельноипотечного кредитования 1.3 Анализ зарубежного и отечеств...
12013. Фінансова діяльність ХФ АКБ Правекс-Банк 425.91 KB
  68 ЗМІСТ Вступ 1. Теоретичні та правові основи забезпечення фінансової стійкості комерційного банку 1.1 Сутність фінансової стійкості як економічна категорія 1.2 Система економічних показників оцінки фінансового стану комерційного банку 1.3 Вплив ...
12015. Формирования депозитной политики коммерческого банка на примере Сибирского отделения Сбербанка ОАО 1.17 MB
  Содержание Введение 1. Теоретические основы формирования депозитной политики коммерческого банка Содержание принципы и функции депозитной политики коммерческого банка Классификация депозитных операций коммерческих банков Методы и инструменты
12016. Определение перспектив кассовых операций коммерческих банков 679.87 KB
  ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 1 Содержание и структура кассовых операций банкоВ 2 Правила приема выдачи и пересчета наличных денег использование электронных кассиров 2.1 Правила приема выдачи и пересчета наличных денег 2.2 Использование электронных кассиров 3 Эффе
12017. Изучение основ формирования банковской системы США 80.35 KB
  Содержание ВВЕДЕНИЕ 1. История развития банковской системы США 2. Современная структура банковской системы США 2.1 Банковские учреждения США 2.2 Органы регулирования и надзора за деятельностью банков и других финансовых институтов в США 2.3 Совершенствование ...
12018. ІНВЕСТИЦІЙНА ДІЯЛЬНІСТЬ КОМЕРЦІЙНОГО БАНКУ ТА ЇЇ ВПЛИВ НА ЙОГО ФІНАНСОВИЙ СТАН 505.38 KB
  ДИПЛОМНА РОБОТА за освітньокваліфікаційним рівнем Бакалавр ІНВЕСТИЦІЙНА ДІЯЛЬНІСТЬ КОМЕРЦІЙНОГО БАНКУ ТА ЇЇ ВПЛИВ НА ЙОГО ФІНАНСОВИЙ СТАН Зміст ВСТУП РОЗДІЛ 1. ІНВЕСТИЦІЙНА ДІЯЛЬНІСТЬ КОМЕРЦІЙНИХ БАНКІВ ЯК ДЖЕРЕЛО ЙОГО ФІНАНСОВОЇ СТІЙКОСТІ І ПРИБУТКО...