Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СТВОРЕННЯ I ВЕДЕННЯ ЗБАЛАНСОВАНИХ БІНАРНИХ ДЕРЕВ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
КН-24
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
Лабораторна робота № 4
“ СТВОРЕННЯ I ВЕДЕННЯ ЗБАЛАНСОВАНИХ БІНАРНИХ ДЕРЕВ”
Виконав:
ст. гр. КН-24
Перевірив:
Денисюк П. Ю.
Львів 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з збалансованими бінарними деревами.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора