МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР Лабораторна робота № 4 “ СТВОРЕННЯ I ВЕДЕННЯ ЗБАЛАНСОВАНИХ БІНАРНИХ ДЕРЕВ” Перевірив: [ім’я автора приховано] Львів 2007 МЕТА РОБОТИ Ознайомитися 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нарним деревом, побудованим так: Рис.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льк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. АВЛ-дерево Випадки 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д вузла "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" Узагальнимо розглянуті випадки корекції структури дерева для збалансування. Прямокутники - піддерева . ІНДИВІДУАЛЬНЕ ЗАВДАННЯ #include <conio.h> #include <stdio.h> #include <stdlib.h> typedef int Key; typedef struct tnode * node; struct tnode { Key key; node l,r; }; typedef node BSTtree; node insert (node * h, Key key); node find (node h, Key key); void remove( node * x ); #define N 13 int main(){ clrscr(); int masiv[N] = {70,62,78,72,60,80,90,40,30,77,64,20,86}; int i; node Tree = 0, f; for ( i = 0; i < N; i++){ insert( &Tree, masiv[i]); } f = find(Tree,78); if (!f ) printf("not finded.\n"); else{ printf("\head->r = %d\n",Tree->r->key); printf("p->left = %d\np->right = %d",f->l->key,f->r->key); remove(&f); printf("\nhead->r = %d",Tree->r->key); } return 0; } node newnode( Key i, node l, node r) { node p = (node) malloc (sizeof (*p)); p->l = l; p->r = r; p->key = i; return p; } node insert (node * h, Key key){ node &x = *h; if ( x == 0 ) return x = newnode(key, 0, 0); if ( key < x->key ) return insert(&x->l, key ); else if ( key > x->key ) return insert( &x->r, key ); else if ( key == x->key ) return x; } node find (node h, Key key){ if ( h == 0 ) return 0; if ( h->key == key ) return h; if ( h->key < key) return find ( h->r, key); else return find ( h->l, key); } static node t = newnode(0,0,0); // потрібно для BSTremove, delnode void delnode( node & x ){ if ( x->r != 0 ) delnode( x->r ); else { t->key = x->key; t = x; x = x->l; } } void remove( node * x ){ if ( *x == 0 ) return; t = *x; if ( t->r == 0 ) *x = t->l; else if ( t->l == 0 ) *x = t->r; else delnode( t->l ); } Висновок На цій лабораторній роботі я ознайомився iз способами подання даних в оперативнiй пам'ятi ЕОМ у виглядi збалансованих бінарних (АВЛ) дерев. Оволодiв методами роботи iз збалансованими бінарними деревами.