СТВОРЕННЯ I ВЕДЕННЯ 2-3 ДЕРЕВ.. Лабораторна робота з Інші. Робота № 201502

СТВОРЕННЯ I ВЕДЕННЯ 2-3 ДЕРЕВ.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра САПР

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Інші

Група:

КН-24

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР Лабораторна робота № 5 “ СТВОРЕННЯ I ВЕДЕННЯ 2-3 ДЕРЕВ” Виконав: ст. гр. КН-24 Перевірив: Денисюк П. Ю. Львів 2007 МЕТА РОБОТИ Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi 2-3 дерев. Оволодiти методами роботи iз 2-3 деревами. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Визначення. 2-3-деревом називається дерево, у якому кожний вузол, що не є листом, має двох чи трьох нащадків, а довжини всіх шляхів із кореня в листки однакові. Дерево, що складається з 1 вузла, є 2-3-деревом. Лема. Нехай Т буде 2-3-деревом висоти h. Кiлькiсть вузлів дерева Т міститься між 2^(h+1)-1 i (3^(h+1))/2, а кiлькiсть листків між 2^h i 3^h. Лінійно впорядковану множину S можна зобразити 2-3-деревом, приписавши всі елементи листкам дерева. Якщо з вузла f виходить лише два листки l1 i l2, то l робимо сином вузла f. Якщо а<E[l1], то l робимо сином вузла f і приймаємо L[f]=a i M[f]=E[l1]; якщо E[l1]<a<E[l2], то l робимо середнім сином вузла f і приймаємо M[f]=a; Якщо E[l2]<a, то l робимо третiм сином вузла f. В останньому випадку, можливо, потрiбно буде змiнити значення L i M на деяких дiйсних предках вузла f. Приклад 1. Якщо у 2-3 дерево, зображене на рис.1.а. вставляється елемент 2, то отримується дерево, зображене на рис.1.б. Тепер припустимо, що у f вже є три листки l1, l2, l3. Зробимо l вiдповiдним сином вузла f. Тепер f має чотирьох синiв. Щоб зберегти 2-3 властивiсть, утворимо новий вузол g. Два лiвих сина залишаться синами вузла f, а два правих переробимо у синiв вузла g. Потiм зробимо g братом вузла f, зробивши його сином батька вузла f. Якщо батько вузла f мав двох синiв, то на цьому зупиняємося. Якщо ж трьох, то потрiбно рекурсивно повторювати цю процедуру доти, поки у всiх вузлiв у деревi залишиться не бiльше від трьох синiв. Якщо у кореня виявиться чотири сина, утворимо новий корiнь с з двома новими синами, кожен з яких буде мати в якостi двох своїх синiв двох iз чотирьох синiв старого кореня. Приклад 2. Якщо у 2-3 дерево, зображене на рис.2.а. вставляється елемент 4, то новий лист із мiткою 4 потрiбно зробити найлiвiшим сином вузла с. Оскiльки у с уже є три сина, будуємо новий вузол с'. Потiм робимо листки 4 i 5 синами вузла с, а листки 6 i 7 - синами вузла с'. Тепер робимо с' сином вузла а. Але оскiльки в а вже є три сина, будуємо новий вузол а'. Робимо вузли b i c синами старого вузла а, а вузли с і d - синами нового вузла а. Нарешті утворюємо новий корінь r і робимо а і а' його синами. Отримане дерево зображене на рис 3. Алгоритм. Вставляння нового елемента у 2-3 дерево. Вхід. Непорожнє 2-3 дерево Т з коренем r і новий елемент а і Т. Вихід. Перетворене 2-3 дерево Т з новим листом, відміченим а. Метод. За умовою Т містить хоча б один елемент. Щоб спростити описання алгоритму, опустимо деталі коректування L i M. 1. Якщо Т складається з єдиного вузла l з міткою b, утворимо новий корінь r. Утворимо новий вузол V із міткою а. Робимо l i V синами кореня r, причому l буде лівим сином, якщо b<a, і правим, якщо b>a 2.Якщо Т містить більше вiд 1 вузла, припустимо f=ПОШУК(а,r), процедура ПОШУК наведена на рис 4. Утворимо новий листок l з міткою а. Якщо у f два сина з мітками b1 i b2, то робимо l відповідним сином вузла f. l буде лівим сином, якщо а<b1, середнім, якщо b1<a<b2, і правим, якщо b2<a. Якщо у f три сина тоді робимо l відповідним сином вузла f, а потім, щоб ввести в Т вузол f і його чотирьох синів, видаляємо ДОБАВСИНА(f). Щоб врахувати присутність вузла а, коректуємо значення L i M уздовж шляху з а в корінь. Інші очевидні зміни, які коректують значення L i M, здійснюються процедурою ДОБАВСИНА. Випадок 1. Якщо l-корінь, видаляємо його. (У цьому випадку а був єдиним елементом у дереві). Випадок 2. Якщо l-син вузла, що має трьох синів, видаляємо його. Випадок 3. Якщо l-син вузла, що має двох синів, то може бути одне з двох: а) f-корінь; видаляємо l і f та робимо коренем другого сина S; б) f-не корінь. Допустимо, що f має брата ліворуч від себе. Випадо к, коли брат знаходиться праворуч, розглядається аналогічно. Якщо у g лише два сина, робимо вузол S найправішим сином вузла g, видаляємо l і рекурсивно викликаємо процедуру видалення, щоб видалити f. Якщо у g три сина, то найправішого сина робимо лівим сином вузла f і видаляємо l. Приклад 3. Із 2-3-дерева на рис.6 видалимо елемент 4. Вузол с-син вузла а, в якого є два сина. Вузол а' - правий брат вузла а. Тому за симетрією робимо b найлівішим сином вузла а', видаляємо с і потім рекурсивно видаляємо а. Рис.6. Дерево з рис.3 пiсля видалення елемента 4 ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Програмно реалiзувати: 1) процедуру вставляння нового елемента у 2-3-дерево; 2) процедуру видалення з 2-3-дерева; 3) процедуру пошуку у 2-3-деревi. #include <stdio.h> #include <stdlib.h> #include <conio.h> typedef char type_of_element; struct unit { type_of_element key; unit * left; unit * right; unit * parent; }; void tree_insert(unit **, type_of_element); void inorder_tree_walk(unit *); unit * tree_search(unit *, type_of_element); unit * initialization_tree(void); unit * tree_minimum (unit *); unit * tree_successor(unit *); unit * tree_delete(unit *, unit *); void main (void) { unit * root; root=initialization_tree(); type_of_element element; while (1) { printf ("\n 1 - add element\n2 - delete element\n 3 - show tree \n4 - exit \n"); int answer; scanf(" %d",&answer); switch (answer) { case 1:{ printf("\n Enter the key of current element\n"); scanf(" %c",&element); tree_insert(&root,element); }; break; case 2:{ type_of_element symbol; printf("\n Enter the key of element \n"); scanf(" %c",&symbol); tree_delete(root, tree_search(root, symbol)); }; break; ase 3:{ inorder_tree_walk(root); }; break; default:{ printf("\n Good bye \n"); goto l1; } } } l1: getch(); } void tree_insert(unit ** root, type_of_element element) { unit * run_pointer,* pointer, * inserting_unit; pointer=(*root); run_pointer=NULL; inserting_unit=(unit *)malloc(sizeof(struct unit)); inserting_unit->left=NULL; inserting_unit->right=NULL; inserting_unit->parent=NULL; inserting_unit->key=element; while (pointer!=NULL) { run_pointer=pointer; if (element<pointer->key) pointer=pointer->left; else pointer=pointer->right; } inserting_unit->parent=run_pointer; if (run_pointer==NULL) (*root)=inserting_unit; else if (inserting_unit->key<run_pointer->key) run_pointer->left=inserting_unit; else run_pointer->right=inserting_unit; } unit * initialization_tree (void) { unit * root; root=(unit *)malloc(sizeof(struct unit)); root->left=NULL; root->right=NULL; root->parent=NULL; printf("\n Enter the key of the root of tree\n"); type_of_element element; scanf(" %c",&element); root->key=element; if (root!=NULL) return root; else { printf("\n Error\n") ;return NULL;}; } void inorder_tree_walk(unit * root) { if (root!=NULL) { inorder_tree_walk(root->left); printf(" %c",root->key); inorder_tree_walk(root->right); }; } unit * tree_minimum (unit * x) { while (x->left!=NULL) x=x->left; return x; } unit * tree_successor(unit * x) { unit * y; if (x->right!=NULL) return tree_minimum(x->right); y=x->parent; while ((y!=NULL) && (x==y->right)) { x=y; y=y->parent;}; return y; } unit * tree_delete(unit * root, unit * z) { unit * y, * x; if ((z->left==NULL) || (z->right==NULL)) y=z; else y=tree_successor(z); if (y->left!=NULL) x=y->left; else x=y->right; if (x!=NULL) x->parent=y->parent; if (y->parent==NULL) root=x; else if (y==y->parent->left) y->parent->left=x; else y->parent->right=x; if (y!=z) z->key=y->key; return y; } unit * tree_search(unit * pointer, type_of_element symbol) { if ((pointer==NULL)|| (pointer->key==symbol)) return pointer; if (symbol<pointer->key) tree_search(pointer->left,symbol); else tree_search(pointer->right,symbol); } Висновок На цій лабораторній роботі я ознайомився iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi 2-3 дерев. Оволодiв методами роботи iз 2-3 деревами

Лабораторна робота Інші

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись