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. Правое поддерево было длинее, имеем расбалансировку.

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


 

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

18310. ЛОГІКА 4 клас Експериментальний навчальний посібник 2.47 MB
  Митник О.Я. М 66 Логіка 4 клас. Навчальний посібник. Київ: Початкова школа 2009. 80 с. ІЗВМ 9789668087332 Навчальний посібник Логіка для 4 класу є продовженням певної системи ознайомлення дітей з основними поняттями сучасної логіки з основними видами логічних задач які...
18311. Умовиводи 97.5 KB
  Практичне заняття № 6 Тема: Умовиводи. І. Перетворення. Теоретичні питання. 1. Умовивід його структура. 2. Перетворення та його суть. 3. Схема перетворення для стверджувального судження загального і часткового. 4. Перетворення заперечного судження та його схема ...
18312. Математика. Практикум. Ч 1 3.21 MB
  Коберник Г.І. Чирва Г.М. Математика. Практикум. Ч 1. – Умань: РВЦ Софія 2009. – 185 с. Навчальний посібник написаний згідно навчальної програми курсу €œМатематика€ для педагогічних вузів спеціальності €œПочаткова освіта€. Посібник містить навчальну програму з цього
18313. Математика. Практикум. Ч ІІ 1.3 MB
  Коберник Г.І. Чирва Г.М. Математика. Практикум. Ч ІІ. – Умань: РВЦ Софія 2009. – 185 с. Навчальний посібник написаний згідно навчальної програми курсу €œМатематика€ для педагогічних вузів спеціальності €œПочаткова освіта€. Посібник містить навчальну програму з цьог
18314. ЕКОНОМІЧНИЙ КОНТРОЛЬ У ПРАВООХОРОННІЙ ДІЯЛЬНОСТІ УКРАЇНИ 338.5 KB
  ТЕМА 1. ЕКОНОМІЧНИЙ КОНТРОЛЬ У ПРАВООХОРОННІЙ ДІЯЛЬНОСТІ УКРАЇНИ ПЛАН 1.1. Поняття економічного контролю його сутність об’єктивність та основні принципи. 1.2. Роль правоохоронних органів під час здійснення економічного контролю. 1.3. Державна податкова служба як ор
18315. СУДОВО-БУХГАЛТЕРСЬКА ЕКСПЕРТИЗА, ЇЇ ВИДИ ТА ЗАВДАННЯ 239 KB
  ТЕМА 2. СУДОВОБУХГАЛТЕРСЬКА ЕКСПЕРТИЗАЇЇ ВИДИ ТА ЗАВДАННЯ ПЛАН 2.1. Поняття про судові експертизи та їх зв’язок з правоохоронною діяльністю. 2.2. Види судових експертиз їх класифікація. 2.3. Сутність судовобухгалтерської експертизи та її зв’язок із практикою бухгал
18316. ПРЕДМЕТ І МЕТОД СУДОВО-БУХГАЛТЕРСЬКОЇ ЕКСПЕРТИЗИ 221.5 KB
  ТЕМА 3. ПРЕДМЕТ І МЕТОДСУДОВОБУХГАЛТЕРСЬКОЇ ЕКСПЕРТИЗИ ПЛАН 3.1. Предмет і об’єкти судовобухгалтерської експертизи. 3.2. Методи методичні прийоми і процедури судовобухгалтерської експертизи. Самостійне вивчення теми передбачає засвоєння о
18317. ОРГАНІЗАЦІЯ СУДОВО-БУХГАЛТЕРСЬКОЇ ЕКСПЕРТИЗИ 346.5 KB
  ТЕМА 4. ОРГАНІЗАЦІЯ СУДОВОБУХГАЛТЕРСЬКОЇ ЕКСПЕРТИЗИ ПЛАН 4.1. Загальна організація судовобухгалтерської експертизи в Україні. 4.2. Процес судовобухгалтерської експертизи та його стадії. 4.3. Порядок атестації судових експертів та основні кваліфікаційні вимоги до
18318. ОРГАНІЗАЦІЙНА СТАДІЯ СУДОВО-БУХГАЛТЕРСЬКОЇ ЕКСПЕРТИЗИ 311 KB
  ТЕМА 5. ОРГАНІЗАЦІЙНА СТАДІЯ СУДОВОБУХГАЛТЕРСЬКОЇ ЕКСПЕРТИЗИ ПЛАН 5.1. Порядок призначення судовобухгалтерської експертизи. 5.2. Зміст та структура постанови ухвали про призначення судовобухгалтерської експертизи. 5.3. Проведення судовобухгалтерської експерти