47287

Алгоритм пересчета балансов вершин выделенного пути и его особенности

Доклад

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

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Русский

2014-03-31

76.6 KB

0 чел.

Алгоритм пересчета балансов вершин выделенного пути и его особенности.

Основная идея

Если вставка или удаление элемента приводит к нарушению сбалансированности дерева то выполняется его балансировка 

 Коэффициент сбалансированности узла

это разность высот его левого и правого поддеревьев 

В АВЛ дереве коэффициент сбалансированности любого

узла принимает значения из множества {-1, 0, 1}

Балансировка дерева

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Типы поворотов:

Одиночный правый поворот

Одиночный левый поворот

Двойной лево -правый поворот

Двойной право- левый поворот


 

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

71364. Corel Draw 9.0 Преобразование формы объектов. Специальные эффекты 357.5 KB
  Инструмент Форма выделяет контур объекта и представляет его как совокупность отрезков прямых и кривых линий соединенных опорными точками узлами. Перемещение узлов меняет форму объекта воспользуйтесь контекстным меню Преобразовать в кривые.
71365. Служба доменних імен (DNS) 457 KB
  Завдання на роботу Провести настроювання первинного сервера DNS для зони згідно варіанту завдання. Визначити резервний DNS-сервер для створеної зони. Виконати процедуру передачі інформації про зону. Створити обернену зону, для локального IP 10.18.51.1.
71366. Передача поштових повідомлень. Протокол SMTP 216 KB
  Налаштувати поштовий сервер на базі MTA Postfix для обробки повідомлень для домену згідно варіанту завдання. Використовувати базові засоби запобігання пересилання небажаних повідомлень, включити підтримку «чорних списків» і синонімів поштових скриньок.
71367. Побудова VPN сервера 1.42 MB
  Коли з на реальній машині підключається VPN з’єднання доступ до Інтернету за замовченням йде через нього, так як віртуальна машина отримує Інтернет через NAT з реальної машини, перевірити працездатність роздачі Інтернету неможливо, бо відбувається замкнуте коло.
71370. Протокол передачі файлів FTP 404.5 KB
  Встановити і настроїти сервер FTP на базі vsftpd. Забезпечити можливість підключення згідно з варіантом. Анонімного користувача. У домашньому каталозі анонімного користувача створити 2 каталоги: pub і incoming. Каталог pub доступний тільки для читання, каталог incoming доступний для читання і запису.
71371. Мережева файлова система NFS 1.38 MB
  Завдання на роботу: Настроїти сервер NFS. Забезпечити можливість монтування файлових систем згідно з варіантом. Перевірити роботу NFS сервера підключивши до нього клієнт.
71372. Спільні ресурси мережі Microsoft Windows. Протоколи NetBIOS/SMB і додаток Samba 881.89 KB
  Завдання на роботу Встановити і налаштувати сервер Samba. Забезпечити можливість підключення поділюваних ресурсів згідно варіанту. Перевірити працездатність Samba сервера.