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

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


 

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

25084. Благодійність 33 KB
  Існують різні погляди на благодійність: 1 благодійність немає сенсу і є аморальною тому що а це різновид бізнесу; б інструмент ідеологічного і політичного впливу; в засіб розваги для багатих бо велика помпезність потребує великих грошей і вони більші ніж ті що йдуть для бідних. 2 благодійність має тісний зв’язок з владою а саме з владою церкви яка говорить про милосердя. 3 благодійність і милосердя існують для того щоб мати похвалу від сучасників та залишитись у пам’яті нащадків. 5 благодійність направлена на послаблення...
25085. Етикет 37.5 KB
  Іноді достатньо одного погляду на людину щоб оцінити її смак і манеру вбиратися. Одяг підкреслює гарний смак одних і несмак інших. У здоровому цивілізованому суспільстві панує здоровий естетичний смак. Смак володар моди.
25087. Толерантність 35.5 KB
  Толерантність є необхідною умовою людського співжиття. Толерантність вимагає від людей примирення досягнення компромісу. Толерантність не є насиллям над людською волею позаяк це не людська кара. Приклади толерантності: батьки миряться з певною поведінкою своїх дітей; людина терпить слабкості іншої людини; людина терпить толерантність; монарх терпить інакомислення; релігійна течія терпимо ставиться до гомосексуалів; держава визнає релігійні меншини; суспільство терпимо ставиться до певних форм девіантної поведінки.
25088. Мораль – это совокупность исторически определенных норм 33.5 KB
  Функции морали отражают основные направления ее применения и через них реализуются цели задачи назначение морали. Функции морали: Регулятивная функция морали главная функция регулирующая поведение людей и общества в целом посредством: ограничения негативных устремлений людей; саморегуляции индивида и социальной среды управление общественными отношениями; воплощение в жизнь гуманистических норм морали. Воспитательная функция морали формирование нравственных привычек установок моральных запретов самовоспитания человека в течение всей...
25089. Мораль как целостное общественное явление 42.5 KB
  Альтруизм – нравственный принцип предписывающий сострадание и милосердие к другим людям бескорыстное служение им и готовность к самоотречению во имя их блага. Слово милосердие является самым близкими и понятными каждому человеку. Милосердие – свойство характера определяющее постоянный нравственный образ действий человека. Милосердие – это: доброжелательное сострадательное отношение к другому человеку; сочувствие жалость сострадание любовь; благотворительность.
25090. Поняття естетика 36.5 KB
  Естетичне це специфічно духовне чуттєве відношення людини до світу. Характеристикою такого відношення є здатність людини самореалізуватися цілісно і всебічно. У естетичному відношенні людина вільна від егоїстичного інтересу вона піднімається до безкорисливого дійсно людського відношення до предмету.