Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Створення і ведення збалансованих бінарних дерев
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
Звіт
про виконання лабораторної роботи №4
на тему:
«Створення і ведення збалансованих бінарних дерев»
1. МЕТА РОБОТИ
Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi збалансованих бінарних (АВЛ) дерев. Оволодiти методами роботи iз збалансованими бінарними деревами.
2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI
Зручним методом пошуку у таблицi, якщо вона не надто велика, є метод дiлення пополам. Як приклад розглядається пошук у таблицi, в якiй наведена кiлькiсть населення в окремих областях. Пошук здiйснюється за кодом ключа, що є скороченою назвою областi. Якщо зобразити скiнченну множину у виглядi таблицi, впорядкованої за зростанням ключiв, то з'явиться можливiсть здiйснювати пошук як у словнику.
Послідовність пошуку
Ключ
Дані
ВІН
Вінницька
1997
ВОЛ
Волинська
1032
ДНІ
Дніпропетровська
2808
ДОН
Донецька
3747
ЖИТ
Житомирська
5252
ЗАК
Закарпатська
1570
ЗАП
Запорізька
1188
ІВФ
Франківська
2008
КИЇ
Київська
1360
КІР
Кіровоградська
1924
КРМ
Крим
1238
ЛЬВ
Львівська
2277
МИК
Миколаївська
2622
ОДЕ
Одеська
1268
ПОЛ
Полтавська
2588
Замiнимо таблицю бiнарним деревом, побудованим так:
Рис.1 Лексично впорядковане дерево
Особливiстю цього бiнарного дерева є:
1) у кожному вузлi бiнарного дерева мiститься по одному значенню ключа;
2) для кожного вузла дерева всi ключi у лiвому пiддеревi меншi, а у правому пiддеревi бiльшi значення ключа даного вузла. Таке бiнарне дерево називається бiнарним деревом пошуку. Витрати часу на пошук у двох випадках однаковi.
Якщо множина ключiв фiксована, як у розглянутому прикладi, то немає особливої переваги у програмi, яка виконує пошук по бiнарному дереву. Вигiдним є метод пошуку дiленням таблицi пополам, бо програма вiдносно простiша i у зображеннi такої структури даних немає складностей.
Якщо множина ключiв наперед не вiдома або коли множина ключiв змiнюється, рацiонально використовувати бiнарне дерево пошуку, яке дає змогу значно простiше вставляти i видаляти елементи. Максимальна кiлькiсть вузлiв у бiнарному деревi заданої висоти h:
N2(h)=2h-1
попереднього прикладу), необхiдно вiдчепити вiд вузла "10" вузол "12" i прикрiпити до вузла "14
Рис.5. Вставлення ключа “7”
Нехай вставляється ключ "11". Послiдовнiсть дiй аналогiчна дiям, показаним на рис.3. Тiльки у цьому випадку також при поворотi вузол "11" необхiдно вiдчепити вiд вузла "12" i прикрiпити до вузла "10".
Рис.6. Вставлення ключа "11"
Випадки 1 i 2 проблем не викликають. Розглянемо випадок 3.
Нехай вставляється ключ iз значенням “1”. Показник збалансованостi вузла "4" дорiвнюватиме -2. Корекцiя здiйснюється в межах пiддерева. Замiсть вузла "4" коренем цього пiддерева стає вузол "2", здiйснивши поворот вузлiв "2" i "4" праворуч, як показано стрiлкою.
Рис.3. Вставлення ключа "4"
Нехай вставляється ключ iз значенням "3". У даному випадку вiдновити баланс буде дещо складнiше: спочатку повертаються лiворуч вузли "2" i "3" а). Отримуємо структуру б). Тепер, якщо вузли "3" i "4" повернути праворуч, то дiлянка дерева виявиться збалансованою в).
Рис.4. Вставлення ключа 3
Нехай вставляється "7". У цьому випадку (рис. 4) поблизу вставленого вузла збалансованiсть зберiгається, проте результат вставки дає про себе знати вище для вузла "14". Крiм повороту, показаного на рис.5.а) ("14" аналогiчна "4", а "10" - "2"
У загальному випадку бiнарне дерево з довiльною кiлькiстю вузлiв n називається повнiстю збалансованим деревом, якщо кiлькiсть вузлiв у лiвому i правому пiддеревах вiдрiзняються не бiльше нiж на одиницю.
Кiлькiсть варiантiв структур бiнарних дерев можна приблизно оцiнити за допомогою формули Стiрлiнга:
4n/n*3/2
Якщо кiлькiсть ключiв n=15( серед 9694845 бiнарних дерев лише одне буде повнiстю збалансованим.
Якщо кiлькiсть ключiв n=16( серед 35357670 бiнарних дерев лише вiсiм будуть повнiстю збалансованими. Це переконливо свiдчить про те, що повнiстю збалансованi дерева трапляються рiдко. Кiлькiсть порiвнянь до збiгу аргумента iз ключем вузла:
Cn=1/n*(log2(k+1))
1<k<n(
де Cn - середня кiлькiсть порiвнянь при вдалому пошуку, k - вузол збiгу.
Середня кiлькiсть порiвнянь для невдалого пошуку виражається формулою:
Cnn=[n/(n+1)]*(Cn+1)+1
Бiнарне дерево пошуку можна подати для даних, що вводяться у випадковiй послiдовностi:
а) у послiдовностi географiчного розмiщення iз заходу на схiд;
б) у послiдовностi зростання кiлькостi населення i тому подiбне.
Доведено, що кiлькiсть порiвнянь для випадкового дерева у середньому всього лише на 39% перевищує кiлькiсть порiвнянь для повнiстю збалансованого дерева.
Отже, серед випадкових дерев рiдко трапляються виродженi, а в основному достатньо добре збалансованi; вiдповiдно, кiлькiсть порiвнянь не надто зростає, навiть якщо не намагатися перетворити випадкове дерево у повнiстю збалансоване.
Зауважимо:
1 - iмовiрнiсть появи виродженого дерева на практицi є набагато більша;
2 - процедура вставки, що відновлює ідеальну збалансованість структури дерева після випадкової вставки, дуже складна операція.
Використовуючи відносно прості засоби і послабивши умови збалансованості, можна побудувати майже збалансоване дерево. Одне iз рішень проблеми запропонували Адельсон-Вельський і Ландис. Критерій такий:
Дерево є збалансованим тоді і тільки тоді
коли для кожного вузла висота двох піддерев відрізняється
не більше ніж на одиницю.
Дерева, що задовольняють цю умову, називаються АВЛ-деревами. Усі ідеально збалансовані дерева також є АВЛ-деревами. Визначення приводить до легко виконуваного збалансування, а середня довжина пошуку залишається практично такою ж, як в ідеальнольному збалансованому деревi.
Дамо таке визначення "показника збалансованості" вузлів для дерев довільної структури:
(показник збалансованостi вузла) = (висота правого пiддерева цього вузла) - (висота лiвого пiддерева цього вузла).
В АВЛ-деревi показник збалансованостi всiх вузлiв дорiвнює або -1, 0 або +1. У повнiстю збалансованих деревах для всiх вузлiв, за винятком максимум одного вузла, показник збалансованостi дорiвнює 0.
Вставимо новi ключi в АВЛ-дерево. Якщо вставку нових ключiв здiйснювати у дерево на рис.2., то ключ займе мiсце одного iз зовнiшнiх вузлiв дерева a, b, c,...,x, який стане пiсля вставки внутрiшнiм вузлом дерева.
Можливi такi випадки:
1) випадок с. Показник збалансованостi покращується;
2) випадки h, i, j, k, l, m. Показник збалансованостi погiршується, але властивостi АВЛ-дерева зберiгаються;
3) усi iншi випадки порушують властивостi АВЛ-дерева. З'являються вузли iз показниками збалансованостi +2 чи -2, i для збереження властивостi збалансованостi АВЛ-дерева необхiдна певна корекцiя структури дерева.
Рис.2. АВЛ-дерево
17.07.2020 14:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора