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

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


 

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

40749. Сучасні види та способи друку 175.54 KB
  Класифікація видів та способів друку. Спеціальні види та способи друку. Класифікація видів та способів друку. Вид друку оприділяється конкретними особливостями роз положення друкарських елементів відносно пробільних на друкарських формах.
40750. АХОДИ ЗАБЕЗПЕЧЕННЯ КРИМІНАЛЬНОГО ПРОВАДЖЕННЯ 107.41 KB
  Затримання особи та обрання їй запобіжного заходу у вигляді взяття під варту : у чинному КПК України та у його проекті О. Поміщення особи у медичний заклад : пропозиції до нового КПК України В. 131 КПК заходами забезпечення кримінального провадження є: 1 виклик слідчим прокурором судовий виклик і привід ст. 133−143 КПК; 2 накладення грошового стягнення ст.
40751. Загальні положення досудового розслідування 41.62 KB
  Загальні положення досудового розслідування Поняття стадії досудового розслідування. Форми досудового розслідування: дізнання та досудове слідство. Поняття та характеристика загальних положень досудового розслідування.
40752. ПРОВАДЖЕННЯ СЛІДЧИХ (РОЗШУКОВИХ) ДІЙ 70.79 KB
  Забезпечення недоторканості житла чи іншого володіння особи в кримінальному процесі : Інститут слідчої дії ‑ це система правових приписів що визначають: сферу й об’єкт слідчої дії його мету і завдання; підстави проведення; коло учасників та їх правовий статус; механізм реалізації ними своїх прав і обов’язків; порядок здійснення і правила провадження пізнавальнозасвідчувальних дій; способи і форми їх фіксації; гарантії захисту прав і свобод людини заходи та межі примусу і відповідальності які застосовуються у разі...
40753. ПОВІДОМЛЕННЯ ПРО ПІДОЗРУ 44.63 KB
  Повідомлення про підозру займає особливе місце в структурі досудового розслідування. Воно підводить підсумок проведеної до того часу роботи, зібраним доказам, у більшості визначає подальше спрямування кримінального провадження і є початковим моментом притягнення до кримінальної відповідальності.
40754. Абразивні матеріали: класифікація, властивості та галузі використання 111.92 KB
  Абразивные материалы это материалы обладающие высокой твердостью и используемые для обработки поверхности различных материалов. Для изготовления абразивных инструментов используются частицы материалов различной зернистости обладающие высокой твердостью и способностью резания. Карбид кремния SiC обладает более высокой твердостью до3235 ГПа но имеет высокую хрупкость и малую прочность поэтому применяется для обработки хрупких материалов – чугунов бронзы титановых и тугоплавких сплавов заточки твердосплавных инструментов.
40755. Регулювання конфліктів 69.82 KB
  Згладжування конфлікту. Співробітництво – базується на впевненості сторін конфлікту в тому що розбіжності в поглядах є закономірними і сторони визнають право кожного на особисту думку та готові зрозуміти один одного що дає можливість аналізувати причини розбіжностей і знайти прийнятний для всіх вихід. Методика вирішення конфлікту
40756. ЗУПИНЕННЯ І ЗАКІНЧЕННЯ ДОСУДОВОГО РОЗСЛІДУВАННЯ 39.61 KB
  Підстави і процесуальний порядок зупинення та відновлення досудового розслідування. Форми закінчення досудового розслідування. Про затвердження Інструкції з організації взаємодії органів досудового слідства з оперативними підрозділами ОВС на стадіях документування злочинних дій реалізаціїоперативних матеріалів розслідування кримінальної справи та її розгляді в суді : наказ МВС України від 07 верес.
40757. ОСКАРЖЕННЯ РІШЕНЬ, ДІЙ ЧИ БЕЗДІЯЛЬНОСТІ ПІД ЧАС ДОСУДОВОГО РОЗСЛІДУВАННЯ 42.38 KB
  ОСКАРЖЕННЯ РІШЕНЬ ДІЙ ЧИ БЕЗДІЯЛЬНОСТІ ПІД ЧАС ДОСУДОВОГО РОЗСЛІДУВАННЯ Поняття і суть оскарження рішень дій чи бездіяльності під час досудового розслідування.Порядок оскарження рішень дій чи бездіяльності органів досудового розслідування. Порядок оскарження ухвал слідчого судді.