Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СТВОРЕННЯ I ВЕДЕННЯ 2-3 ДЕРЕВ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
КН-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 деревами
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора