53495

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота

Доклад

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

Следовать по пути поиска, пока не окажется, что узла нет в дереве. Включить новый узел и определить показатель сбалансированности. Пройти обратно по пути поиска, определяя сбалансированность.

Русский

2014-04-01

129.41 KB

1 чел.

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота.

Алгоритм добавления узла в AVL дерево

3 этапа:

  1. Следовать по пути поиска, пока не окажется, что узла нет в дереве.
  2. Включить новый узел и определить показатель сбалансированности.
  3. Пройти обратно по пути поиска, определяя сбалансированность.

Включение узла:

  1. Выполнить вставку в бинарное дерево.
  2. Если вставка в левое поддерево, то имеют место 3 случая:
  3. Если правое поддерево было длиннее, то стало сбалансированным.
  4. Если был баланс, то левое поддерево выросло, и нужно проверить балансировку выше.
  5. Левое поддерево было длинее, имеем расбалансировку.
  6. Если в правое:
  7. Если левое поддерево было длиннее, то стало сбалансированным.
  8. Если был баланс, то правое поддерево выросло, и нужно проверить балансировку выше.
  9. Правое поддерево было длинее, имеем расбалансировку.

Случай левого поворота


 

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

55210. Агропромисловий комплекс України, його структура. Роль і значення АПК у народному господарстві 24.56 KB
  Агропромисловий комплекс (АПК) – один із найбільших і найважливіших секторів економіки України. Перед ним стоять відповідальні завдання: впровадження в життя аграрної політики, розв’язання продовольчої проблеми, забезпечення населення продовольством
55212. Застосування екологічних ігор, головоломок в педагогічній практиці 105.5 KB
  За допомогою гри можна зацікавити учнів викликати в них інтерес до навчального матеріалу. За допомогою ігор можна закріплювати вміння і навички. Захоплюють дітей ігри з картинками загадками про рослини і тварини ігри-вікторини Що в лісі росте Хто в лісі живе Лісові орієнтири...
55214. Функції посилань та масиви, математичні та логічні функції Microsoft Excel (MICROSOFT OFFICE 2010) 570 KB
  Мета: Навчитися створювати формули для обчислення даних в масиві, використовувати математичні та логічні функції, умовне форматування комірок.
55215. Форматування тексту 43.5 KB
  Мета: навчальна: продовжувати формувати знання вміння та форматування тексту; розвивати самостійне логічне мислення працьовитість. Запитання: Яку тему ви опрацювали на сьогоднішній урок Відповідь: Форматування тексту. І звичайний текст набраний на клавіатурі може виглядати яскраво красиво і різноманітно...
55216. Особливості галузевої структури господарського комплексу Придніпровського економічного району України. Його роль в е Територіально-галузева структура економіки 25.34 KB
  сновою промислового комплексу району є енергетика, яка базується на використанні місцевих гідроенергетичних ресурсів, привізного донецького вугілля, шебелинського газу і місцевого бурого вугілля.