Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Програмування та алгоритмічні мови
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді і спорту України
Національний технічний університет України
«Київский політехнічний інститут»
Навчально-науковий комплекс «Інститут прикладного системного аналізу»
Кафедра Системного Проектування
Курсова робота
З дисципліни «Програмування і алгоритмічні мови»
«Обхід дерев»
Зміст
Вступ 2
Теоретична частина 4
Обробка даних у вершинах дерева 5
Лівий спадний обхід 6
Лівий висхідний обхід 6
Лівий змішаний обхід 7
Приклад лівого спадного обходу LPreorder 10
Перелік використаної літератури 11
Код програми реалізації обходу дерев мовою С. 12
Вступ
Ця робота присвячена дослідженню засобів обходу дерев.
На сьогоднішній день дерева є найбільш поширеною структурою. Вони використовуються майже в кожній галузі, що стосується програмування, моделювання інформаційних процесів, комунікаційних систем, системного аналізу і систематизації взагалі. Вони популярні серед людей з технічним напрямком занять, і не дарма: дерева забезпечують найшвидші і найоптимальніші умови для знаходження елемента серед інших в певній структурі. Звичайно, існують багато типів дерев, в залежності від мети їх створення, і багато операцій над деревами: створення дерева, включення елемента в дерево, обробка даних у вершинах дерев, видалення елемента з дерева, збереження і відновлення бінарного дерева, знищення бінарного дерева. Але в будь-якому дереві найважливішою операцією все одно залишатиметься пошук (локалізація) елемента в дереві, бо на ній побудовані ледь не всі інші операції. Наприклад, включення елемента в дерево складається з трьох дій: пошуку місця включення, виділення динамічної пам’яті і безпосереднього занесення даних. При чому при пошуку місця для елемента ми повинні впевнитись у тому, що такого елемента ще не існує в цьому дереві. А це означає ще одну операцію обходу. Взагалі, дерева – це така структура, що забезпечує найоптимальніші умови зберігання даних і також найменший час їх пошуку, а в збалансованих деревах взагалі можна знайти елемент зробивши лише один крок. Недарма розв’язанням проблем, пов’язаних з деревами, займаються не тільки національні і державні університети та дослідницькі інститути, а ще й великі комерційні підприємства та фірми. У дерева пошуку, дерева сортування й у взагалі таку область дискретної математики, як дерева вкладено величезну купу грошей, нескінченні роки розумової праці найяскравіших інтелектуалів планети. Проте щоб збалансовані дерева залишалися такими при тому, що в них зберігатимуться величезні об’єми даних, треба винайти ще більш ефективні методи обходу дерев, що займають менше часу і, крім того, ще б по ходу дєла сортували данні у відповідності з принципами, що я наводжу у теоретичній частині. Саме такі задачі поставлені перед нашою сьогоднішньою технічною елітою, і перед нами в тому ж числі.
Теоретична частина
Обхід дерев найчастіше проходить задля пошуку елемента. А пошук елемента має на меті різні завдання. По-перше, визначити, чи належить шуканий елемент дереву, чи ні. В цьому випадку результатом буде повернення ознаки про наявність елемента чи його відсутність( true or false, 1 чи 0 відповідно). По-друге, пошук з метою вибірки й опрацювання даних елементу, тоді результат пошуку повертається у вигляді адреси вершини. По-третє, пошук з метою видалення елементу, такий пошук часто є лиш частиною повної операції видалення, а не самостійною операцією.
Сам алгоритм пошуку залежить від виду дерева. В ідеально збалансованому дереві пошук доводиться проводити обходом вершин в деякій послідовності. Мінімальна довжина пошуку тоді дорівнює 1, максимальна ж – n, ну а середня тоді – n/2.
Алгоритм пошуку в бінарному дереві пошуку, як в простому, так і в збалансованому, достатньо простий. Пошук проходить цілеспрямованим рухом вздовж ребер дерева. Якщо ключ пошуку дорівнює ключу у вершині, тоді ключ вважається знайденим і його адреса повертається через параметр-вказівник. Якщо ж ключ пошуку менший від ключа у вершині, тоді ми рухаємося по лівому піддереву, якщо ж навпаки, то тоді по правому піддереву. Якщо ж у черговій вершині рух вниз неможливий (вказівник дорівнює NULL), то це означає, що шуканого ключа в дереві не знайдено – його там немає. Максимальна довжина пошуку дорівнює висоті дерева.
Обробка даних у вершинах дерева
Розрізняють два види обробки: вибіркову обробку окремої вершини і послідовну обробку всіх вершин. Вибіркова обробка включає в себе пошук елементу, і обробку даних у вершині лише в тому випадку, коли шуканий елемент знайдений. Обробка даних залежить від задачі, що вирішується і може зводитись до вилучення данних з вершини без їх змін, або оновленню даних у вершині дерева.
При послідовній обробці проходить так званий обхід дерева. Обхід дерева – процес одноразового відвідування й обробки даних кожної вершини дерева. В залежності від того, в якому напрямку здійснюється рух вздовж гілок дерева і коли обробляються дані у вершинах, шість видів обходів:
Лівий спадний обхід LPreorder – рух згори до низу, від кореневої вершини до листків, реалізується таким алгоритмом:
procedure ПРЕФІКСНИЙ ОБХІД(:дерево);
begin Відвідати корінь дерева ;
if не лист then
Нехай – піддерева кореня ;
for i := 1 to k do ПРЕФІКСНИЙ-ОБХІД( ) end
end
end.
Таким чином проходить обробка даних у вузлі, потім лівий спадний обхід лівого піддерева, і нарешті лівий спадний одхід правого піддерева. В нашому випадку це буде така послідовність вершин: 12, 4, 2, 1, 3, 8, 6, 5, 7, 10, 9, 11, 17, 14, 13, 16, 15, 20, 19, 18, 21.
Лівий висхідний обхід LPostorder – рух зліва направо, від самого лівого листка догори до кореня, потім донизу до самого правого листка. Реалізується таким алгоритмом:
procedure ПОСТФІКСНИЙ ОБХІД(:дерево);
begin Відвідати корінь дерева ;
if не лист then
Нехай – піддерева кореня ;
for i := 1 to k do ПОСТФІКСНИЙ-ОБХІД( ) end
end
end.
Таким чином в нас проходить спочатку лівий висхідний обхід лівого піддерева, потім лівий висхідний обхід правого піддерева, і тільки потім обробка даних у вузлі. Цьому алгоритму відповідає така послідовність вершин: 1, 3, 2, 5, 7, 6, 9, 11, 10, 8, 4, 13, 15, 16, 14, 18, 19, 21, 20, 17, 12.
Лівий змішаний обхід LІnorder – рух зліва направо, від самого лівого листка догори до кореня, потім донизу до самого правого листка. Реалізується таким алгоритмом:
procedure ІНФІКСНИЙ ОБХІД(:дерево);
begin Відвідати корінь дерева ;
if не лист then
Нехай – піддерева кореня ;
for i := 1 to k do ІНФІКСНИЙ-ОБХІД( ) end
end
end.
Таким чином в нас проходить спочатку лівий змішаний обхід лівого піддерева, потім обробка даних у вузлі, а вже потім – лівий змішаний обхід правого піддерева. Цьому алгоритму в нашому випадку відповідає послідовність вершин: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21.
При всіх обходах рух по гілкам дерева продовжується до тих пір, поки вказівник на вузол дерева не стане нульовим.
Застосовуються також і праві обходи дерев: правий спадний RPreorder, правий висхідний RPostorder і правий змішаний RInorder. Їх алгоритми отримуються з алгоритмів лівих обходів шляхом заміни «лівий» на «правий». Тому їх іноді називають зворотніми обходами.
Окрім спадного, висхідного й змішаного обходів, що були вже розглянуті нами, іноді застосовують обхід дерева по рівням. При такому обході вузли дерева відвідуються згори до низу і зліва на право, тобто спочатку корінь дерева, потім вузли першого рівня зліва на право, потім вузли другого рівня зліва на право, і т.д.
Функції обходу дерев можуть бути як рекурсивними, так і ітеративними, найбільш просто реалізуються рекурсивні функції перших шести видів обходу, що ми вже розглядали, в них рекурсивний обхід відповідає рекурсивній структурі дерева. В них, природно, використовуються системні стеки. У не рекурсивних функціях доводиться використовувати явний стек, який, як відомо, реалізується правилом LIFO – ввійшов останнім, вийшов першим.
Обхід вздовж рівнів (корінь – перший рівень – другий рівень – третій рівень –…) не відповідає рекурсивній структурі дерева (корінь – піддерево кореня – піддерево піддерева –…). В не рекурсивній функції обходу по рівням замість стеку доводиться використовувати чергу типу FIFO – ввійшов першим, першим вийшов.
Очевидно, ця функція обробки даних у вершинах дерева залежить від конкретного застосування дерева. В той же час алгоритми обходів дерев залишаються стабільними і працюють незалежно від конкретної структури. Бінарні дерева пошуку можуть бути використані не тільки відповідно зі своїм прямим призначенням – пошуком елементів, а й для сортування даних. Проводячи лівий змішаний обхід бінарного дерева пошуку і розташовуючи дані з вузлів у тому порядку, в якому вони зустрічаються, отримаємо послідовну множину елементів-ключів дерева, впорядковану за зростанням. Аналогічно, правий змішаний обхід дерева дасть нам послідовну множину елементів-ключів дерева, впорядковану за спаданням. Тому інколи про дерева пошуку кажуть як про дерева сортування.
При роботі з деревами виникає ситуація, коли до певних елементів звертаються частіше, до інших – рідше. Трапляються ситуації, коли необхідно повторно звертатись до елементів, до яких були зверненні найсвіжіші запити. Час досягнення цих елементів було б логічно скоротити, помістивши їх ближче до кореня дерева. Для цього достатньо помістити в корінь дерева вузол, до якого був звернений останній запит. Таким чином всі елементи, що використовувались найчастіше, опиняться в такій близькості від кореня, яка б відповідала частоті їх застосування. Це буде зручно для користувача, якщо, звісно, він ставить перед собою таку мету. Якщо ж використання елементів залежить напряму від теорії вірогідності (кожен елемент використовуватиметься вдруге не раніше, ніж всі інші елементи використаються вперше, або взагалі один раз), то має логічне місце пересунення «використаних» вершин в листки або взагалі їх видалення.
Приклад лівого спадного обходу LPreorder:
Перелік використаної літератури
Н. Вирт Алгоритми і структури даных. М.: Мир, 1989. Глава 4.5 (С. 272-286)
Г. М. Адельсон-Вельский, Е. М. Ландис. Один алгоритм організації інформації // Доповіді АН СССР. 1962. Т. 146, № 2. C. 263–266.
Б. С. Хусаїнов. Структури і алгоритми обробки даних. Приклади мовою Сі, Вид-во: Фінанси й статистика, 2004, (С. 155-196), 464 стр.
Ф. В. Лактионов, В. А. Філіпов, О. В. Андреев //Журнал наукових публікацій аспірантів и докторантів. 2008. № 4. С. 207-210.
http://algolist.ru/
Код програми реалізації обходу дерев мовою С.
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
struct record {//Структура узла дерева
int data;//Ключ
record *leftPtr, *rightPtr;//Левый и правый указатели
int bal;//Признак сбалансированности дерева
};
void instructions(void);//Список возможных действий
int insert(int, record **, int *);//Добавление ключа в дерево
void del(int, record **,int *);//Удаление ключа из дерева
void balanceL(record **, int *);
void balanceR(record **, int *);
void delbal(record**, record **, int*);
void rotL(record**);//Ротация влево
void retR(record**);//Ротация вправо
void preorder(record*);//Нисходящий обход
void inorder(record*);//Смешанный обход
void postorder(record*);//Восходящий обход
int main()
{
cout<<"Coursework. Work with AVL-trees."<<endl;
cout<<"Made by Andrew Grushko, KPI, IASA, SP-SAPR, first course."<<endl;
record *root=NULL;
int *h=new int,choice,key;
instructions();
cin>>choice;
if(!choice) {
cout<<"Error in choice. Run again"<<endl;
return 0;
}
while(choice!=3) {
switch(choice) {
case 1:
cout<<"Type a number to insert into the tree: ";
cin>>key;
insert(key,&root,h);//Добавление ключа в дерево
inorder(root);//Вывод на экран
break;
case 2:
cout<<"Type a number to delete from the tree: ";
cin>>key;
del(key,&root,h);//Удаления ключа из дерева
inorder(root);
break;
default:
cout<<"Invalid choice."<<endl<<"? ";
break;
}
instructions();
cin>>choice;
}
cout<<"End of run."<<endl;
return 0;
}
//=================================inctructions()=========================
void instructions()
{
cout<<"Enter your choice:\n\
1 to insert a number into the tree.\n\
2 to delete a number from the tree.\n\
3 to end."<<endl;
cout<<"? ";
}
//=================================insert()===============================
int insert(int key, record **t, int *h)
{
record *t1, *t2, *T; int ret=0;
T=*t;
if(T==NULL) {//дерево пустое
T=new record;
T->data=key;
T->bal=0;
*h=1;
T->leftPtr=T->rightPtr=NULL;
}//поиск ключа в дереве
else if(key<T->data) {
insert(key, &T->leftPtr,h);
if(*h) {
switch(T->bal) {
case 1:T->bal=0; *h=0; break;
case 0:T->bal=-1;break;
case -1: {
t1=T->leftPtr;
if(t1->bal==-1){//LL-поворот
T->leftPtr=t1->rightPtr;
t1->rightPtr=T;
T->bal=0;
T=t1;
}
else {//Двукратный LR-поворот
t2=t1->rightPtr;
t1->rightPtr=t2->leftPtr;
t2->leftPtr=t1;
T->leftPtr=t2->rightPtr;
t2->rightPtr=T;
if(t2->bal==-1)
T->bal=1;
else
T->bal=0;
if(t2->bal==1)
t1->bal=-1;
else
t1->bal=0;
T=t2;
}
T->bal=0;*h=0;
}
}
}
}
else if(key>T->data) {
insert(key,&T->rightPtr,h);
if(*h==1)
switch (T->bal){
case -1: T->bal=0; *h=0; break;
case 0: T->bal=1; break;
case 1: {//балансировка
t1=T->rightPtr;
if(t1->bal==1) {//RR-поворот
T->rightPtr=t1->leftPtr;
t1->leftPtr=T;
T->bal=0; T=t1;
}
else {//двукратный RL-поворот
t2=t1->leftPtr;
t1->leftPtr=t2->rightPtr;
t2->rightPtr=t1;
T->rightPtr=t2->leftPtr;
t2->leftPtr=T;
if(t2->bal==1)
T->bal=-1;
else
T->bal=0;
if(t2->bal==-1)
t1->bal=1;
else
t1->bal=0;
T=t2;
}
T->bal=0;
*h=0;
}
}
}
else {
cout<<"/nDuplicate key: "<<key<<endl;
ret=-1;
}
*t=T;
return ret;
}
//====================================del()===============================
void del(int key, record **T, int *h)
{
record *t, *K; t=*T;
if(*T==NULL) {
cout<<"Element "<<key<<" is not found"<<endl;
*h=0;
}
else if(key<t->data) {
del(key,&t->leftPtr,h);
if(*h) balanceL(&t, h);
}
else if(key>t->data) {
del(key,&t->rightPtr,h);
if(*h) balanceR(&t,h);
}
else {//Удаление
K=t;//Узел найден
if(K->rightPtr==NULL) {//Имеет только левую ветвь
t=K->leftPtr;
delete K;
*h=1;
}
else if(K->leftPtr==NULL) {//Имеет только правую ветвь
t=K->rightPtr;
delete K;
*h=1;
}
else {
delbal(&K->leftPtr,&K,h);
if(*h) balanceL(&t,h);
}
}
*T=t;
}
//====================================delbal()============================
void delbal(record **R, record **K, int *h)
{
record *r, *k;
r=*R; k=*K;
if(r->rightPtr!=NULL) {//спускаемся по правым ветвям до конца
delbal(&r->rightPtr,&k,h);
if(*h) balanceR(R,h);
}
else {
k->data=r->data;
*R=r->leftPtr;
delete r;
*h=1;
}
}
//====================================balanceL()==========================
void balanceL(record **t, int *h)//h=1 => Левая ветвь короче
{
record *t1, *t2, *T;
int b1, b2;
T=*t;
switch(T->bal) {
case -1:T->bal=0; break;
case 0:T->bal=1; *h=0; break;
case 1: {//балансировка
t1=T->rightPtr;
b1=t1->bal;
if(b1>=0) {//однократный RR-поворот
T->rightPtr=t1->leftPtr;
t1->leftPtr=T;
if(!b1) {
T->bal=1;
t1->bal=-1;
*h=0;
}
else {
T->bal=0;
t1->bal=0;
}
T=t1;
}
else {//двукратный RL-поворот
t2=t1->leftPtr;
b2=t2->bal;
t1->leftPtr=t2->rightPtr;
t2->rightPtr=t1;
T->rightPtr=t2->leftPtr;
t2->leftPtr=T;
if(b2==1) T->bal=-1;
else T->bal=0;
if(b2==-1) t1->bal=1;
else t1->bal=0;
T=t2;
t2->bal=0;
}
}
}
*t=T;
}
//====================================balanceR()==========================
void balanceR(record **t, int *h)//h=-1 =>Правая ветвь короче
{
record *t1, *t2, *T;
int b1, b2;
T=*t;
switch(T->bal) {
case 1:T->bal=0; break;
case 0:T->bal=-1; *h=0; break;
case -1: {//балансировка
t1=T->leftPtr;
b1=t1->bal;
if(b1<=0) {//однократный LL-поворот
T->leftPtr=t1->rightPtr;
t1->rightPtr=T;
if(!b1) {
T->bal=-1;
t1->bal=1;
*h=0;
}
else {
T->bal=0;
t1->bal=0;
}
T=t1;
}
else {//Двукратный LR-поворот
t2=t1->rightPtr;
b2=t2->bal;
t1->rightPtr=t2->leftPtr;
t2->leftPtr=t1;
T->leftPtr=t2->rightPtr;
t2->rightPtr=T;
if(b2==-1) T->bal=1;
else if(b2==1) T->bal=-1;
else T->bal=0;
T=t2;
t2->bal=0;
}
}
}
*t=T;
}
//====================================preorder()==========================
void preorder(record *T)
{
if(T){
cout<<T->data<<", ";
preorder(T->leftPtr);
preorder(T->rightPtr);
}
}
//====================================inorder()===========================
void inorder(record *T)
{
if(T){
inorder(T->leftPtr);
cout<<T->data<<", ";
inorder(T->rightPtr);
}
}
//====================================postorder()=========================
void postorder(record *T)
{
if(T){
postorder(T->leftPtr);
postorder(T->rightPtr);
cout<<T->data<<", ";
}
}
08.02.2013 00:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора