о у неї ліва гілка довше правою, або знайти сусідню праворуч запис, якщо права гілка довшим. Знайдена сусідня запис поміщається на місце незбалансованої, а сама незбалансована запис заново включається в дерево.
В упорядкованому бінарному дереві (рис. 2.1), незбалансованої записом є запис 70, т. к. у цієї вершини різниця гілок дорівнює 2 (довжина лівої гілки дорівнює 1, довжина правої гілки - 3, отже, 3 - 1=2). Всі інші вершини є збалансованими.
ітерація. Підрівняти вершину зі значенням 70. На місце вершини 70 ставимо вершину зі значенням 85 разом з усіма витікаючими з неї вершинами (71, 96, 93), далі перерозподіляємо вершину 66, потім перерозподіляємо вершину 70 (рис. 2.2).
Малюнок 2.2 - Підрівнювання вершини 70
ітерація. На малюнку 2.2, видно, що незбалансованої записом є запис 71, т. к. у цієї вершини різниця гілок дорівнює 2 (довжина лівої гілки дорівнює 2, довжина правої гілки - 0, отже, 2 - 0=2). Всі інші вершини є збалансованими.
підрівняти вершину. На місце вершини 71 ставимо вершину зі значенням 66 разом з випливає з неї вершиною 70, далі перерозподіляємо вершину 71 (рис. 2.3).
Малюнок 2.3 - Підрівнювання вершини 71
3 ітерація. З малюнка 2.3, видно, що незбалансованої записом є запис 66, у цієї вершини різниця гілок дорівнює 2 (довжина лівої гілки дорівнює 0, довжина правої гілки - 1, отже, 2 - 0=2). Всі інші вершини є збалансованими.
Виконаємо підрівнювання вершини. На місце вершини 66 ставимо вершину зі значенням 70 разом з випливає з неї вершиною 71, далі перерозподілимо вершину 70 (рис. 2.4).
Малюнок 2.4 - Підрівнювання вершини 66
В результаті перетворень отримуємо подравненное бінарне дерево, т. к. всі його записи є збалансованими (рис. 2.5).
Рисунок 2.5 - Підсумкове подравненное бінарне дерево
Завдання 2. Проставити в вершинах бінарного дерева ключові ознаки від 1 до 12 так, щоб дерево стало впорядкованим (підрівнювати не треба) (рис. 2.6).
Малюнок 2.6 - Приклад головоломки
Проставляючи в вершинах бінарного дерева ключові ознаки, враховувалося те, що записи, позначені однаковими буквами, мають рівні значення. По лівій гілки розташовуються записи з меншими значеннями, по правій гілки - з великими. У підсумку отримали впорядковане бінарне дерево (рис. 2.7).
Малюнок 2.7 - Впорядковане бінарне дерево
1.2 Нелінійні спискові структури даних
Нелінійний список - безліч елементів, кожен з яких може бути або записом, або списком. Структуру списку виражають формулою, в якій записи позначаються буквами, а списки полягають в круглі дужки. Список, включений в інший список, називається підсписків. Адреси зв'язків, що належать кожному записі, утворюють ланка зв'язку. У ланці зв'язку односпрямованого списку дві адреси: перший вказує на наступний елемент списку, другий - на подспісок або запис. Спискові структури даних можуть мати два види подання: за допомогою аналітичної записи та графічної інтерпретації структури списку.
Аналітична запис списковому структури будується за наступними правилами: ...
