75672

Ефективні методи програмування задач редагування і пошуку в послідовностях. Збалансовані дерева

Практическая работа

Информатика, кибернетика и программирование

Закріпити знання про динамічні структури даних. Сформувати навички обробки збалансованих дерев. Сформувати уміння застосовувати АВЛ-дерева для редагування і пошуку в послідовностях.

Украинкский

2015-01-24

180.05 KB

1 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Практична робота №8 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013


Тема: Ефективні методи програмування задач редагування і пошуку в послідовностях. Збалансовані дерева.

Мета:  Закріпити знання про динамічні структури даних. Сформувати навички обробки збалансованих дерев. Сформувати уміння застосовувати АВЛ-дерева для редагування і пошуку в послідовностях.

Завдання:

Варіант № 9.

  1.  Реалізувати описану схему збереження множин у виді збалансованого дерева, переконавшись, що вона також дозволяє обійтися C*log(n) діями для операцій включення, виключення і перевірки приналежності.

Опис алгоритму виконання

На початку програми дерева не існує (множина порожня). Користувач за допомогою клавіші Insert додає нові вузли. При цьому вони додаються рівномірно по рівнях (відбувається балансування дерева).  Вузол додається, дерево перевіряється на збалансованість. Якщо не збалансоване, то відбувається поворот дерева у протилежну дисбалансу сторону.

Складність алгоритму

Складність алгоритму дорівнює О(C*log(N)) від t,

де tчас виконання,

Nкількість вузлів дерева (елементів множини),

С – константа.


Блок-схема алгоритму


Лістинг фрагментів програми

//-----------------------------------------------------------------------------

#pragma once

class Node;

class Tree

{

public:

int num; int topY;

int leftX;

int rightX;

Node children;

Tree* parent;

Tree(int num=0);

Tree(Tree& tr);

~Tree(void);

void ShowTree(HDC hdc, int topY, int leftX, int rightX);

void Add(Tree * tr);

void addChild(Tree * tr);

void setParent(Tree * tr);

Tree* removeChild(int k);

void deleteChild(int k);

void deleteChild(Tree *tr);

int heightCount();

int Balance();

void balanceTree();

void Delete(int n);

bool insideCheck(int n);

};

class Node

{

private:

public:

Tree **arr;

int amount;

Node();

~Node();

void Push(Tree *el);

Tree* Pop(int n);

Tree* operator[](int n);

};

extern Tree *way;

//-----------------------------------------------------------------------------

#include "stdafx.h"

#include "Tree.h"

Tree *way=0;

Tree* Node::operator[](int n) {return arr[n];}

Tree::Tree(int num)

{

num=num;

parent=0;

}

Tree::Tree(Tree& tr)

{

num=tr.num;

children.arr[0]=tr.children[0];

children.arr[1]=tr.children[1];

}

Tree::~Tree(void)

{

}

void Tree::setParent(Tree * tr)

{

parent=tr;

}

void Tree::addChild(Tree * tr)

{

children.Push(tr);

tr->setParent(this);

}

Tree* Tree::removeChild(int k)

{

return children.Pop(k);

}

void Tree::deleteChild(int k)

{

delete children.Pop(k);

}

void Tree::deleteChild(Tree *tr)

{

for(int i=0;i<children.amount;++i)

{

 if(children[i]==tr)

 {

  delete children.Pop(i);

  return;

 }

}

}

const int spaceStep=40;

void Tree::ShowTree(HDC hdc,int top, int left, int right)

{

HPEN hNodePen, hrightPen, holdpen;

HBRUSH hNodeBrush, holdbrush;

hNodePen = CreatePen(PS_SOLID, 3, RGB(255, 128, 0));

hrightPen = CreatePen(PS_SOLID, 3, RGB(7, 100, 255));

holdpen = (HPEN)SelectObject(hdc, hNodePen);

 

hNodeBrush = CreateSolidBrush(RGB(255, 128, 0));

holdbrush = (HBRUSH)SelectObject(hdc, hNodeBrush);

if (this==0) return;

topY=top;

leftX=left;

rightX=right;

int x=left+(right-left)/2;

int y=top+spaceStep/2;

for(int i=0;i<children.amount;++i)

{

 if(children[i]!=0)

 {

  

  holdpen = (HPEN)SelectObject(hdc, hrightPen);

  POINT pnt;

  ::MoveToEx(hdc, x, y, &pnt);

  int x=left+(right-left)/children.amount*i+((right-(right-left)/children.amount*(children.amount-i-1))-(left+(right-left)/children.amount*i))/2;

  int y=top+spaceStep+spaceStep/2;

  ::LineTo(hdc, x, y);

 }

}

holdpen = (HPEN)SelectObject(hdc, hNodePen);

Ellipse(hdc, x-20, y-20, x+20, y+20);

char buf[50];

_itoa(num,buf,10);

::TextOutA(hdc, x-5, y-8, (LPCSTR) buf, strlen(buf) );

 

for(int i=0;i<children.amount;++i)

{

 if(children[i]!=0)

 {

  children[i]->ShowTree(hdc,top+spaceStep,left+(right-left)/children.amount*i,right-(right-left)/children.amount*(children.amount-i-1));

  

 }

}

::DeleteObject(hNodePen);

::DeleteObject(hrightPen);

::DeleteObject(hNodeBrush);

}

Node::Node()

{

amount=2;

arr=new Tree*[amount];

for(int i=0;i<amount;++i)arr[i]=0;

}

Node::~Node()

{

 

}

void Node::Push(Tree *el)

{

Tree ** tmp=new Tree*[amount+1];

for(int i=0;i<amount;++i)

{

 tmp[i]=arr[i];

}

tmp[amount]=el;

++amount;

delete [] arr;

arr=tmp;

}

Tree* Node::Pop(int n)

{

Tree ** tmp=new Tree *[amount-1];

int k=0;

Tree* temp;

for(int i=0;i<amount;++i)

{

 if(i!=n)

 {

  tmp[k]=arr[i];

  ++k;

 }

}

temp=arr[n];

delete [] arr;

arr=tmp;

--amount;

return temp;

}

int Tree::heightCount()

{

if(this==0)return 0;

return max(children[0]->heightCount(),children[1]->heightCount())+1;

}

int Tree::Balance()

{

return children[0]->heightCount()-children[1]->heightCount();

}

enum Rot

{

left=0,

right

};

void Rotate(Tree * parent,Rot direction)

{

if(direction==left)

{

 Tree *tmp=new Tree(*parent);

 parent->children.arr[0]=tmp;

 tmp->children.arr[1]=parent->children[1]->children[0];

 parent->num=parent->children[1]->num;

 tmp=parent->children.arr[1];

 parent->children.arr[1]=parent->children[1]->children[1];

 delete tmp;

 return;

}

 

if(direction==right)

{

 Tree *tmp=new Tree(*parent);

 parent->children.arr[1]=tmp;

 tmp->children.arr[0]=parent->children[0]->children[1];

 parent->num=parent->children[0]->num;

 tmp=parent->children.arr[0];

 parent->children.arr[0]=parent->children[0]->children[0];

 delete tmp;

 return;

}

}

void Tree::balanceTree()

{

while(Balance()<-1)Rotate(this,left);

while(Balance()>1)Rotate(this,right);

}

void Tree::Add(Tree * tr)

{

if(tr->num<this->num&&Balance()>0)

{

 Rotate(this,right);

}

else

{

 if(tr->num>this->num&&Balance()<0)

 {

  Rotate(this,left);

 }

}

if(tr->num<this->num)

{

 if(children[0]==0)children.arr[0]=tr;

 else

  children[0]->Add(tr);

 return;

}

if(tr->num>this->num)

{

 if(children[1]==0)children.arr[1]=tr;

 else

  children[1]->Add(tr);

 return;

}

 

}

void Tree::Delete(int n)

{

if(children[0]!=0&&children[0]->num==n)

{

 Tree*tmp=children[0];

 if(children[0]->children[0]!=0)

 {

  children.arr[0]=children[0]->children[0];

  if(tmp->children[1]!=0)children[0]->Add(tmp->children[1]);

 }

 else

 {

  children.arr[0]=children[0]->children[1];

  if(children[0]!=0&&tmp->children[0]!=0)children[0]->Add(tmp->children[0]);

 }

 balanceTree();

 return;

}

if(children[1]!=0&&children[1]->num==n)

{

 Tree*tmp=children[1];

 if(children[1]->children[0]!=0)

 {

  children.arr[1]=children[1]->children[0];

  if(tmp->children[1]!=0)children[1]->Add(tmp->children[1]);

 }

 else

 {

  children.arr[1]=children[1]->children[1];

  if(children[1]!=0&&tmp->children[0]!=0)children[1]->Add(tmp->children[0]);

 }

 balanceTree();

 return;

}

for(int i=0;i<children.amount;++i)if(children[i]!=0)children[i]->Delete(n);

}

bool Tree::insideCheck(int n)

{

if(this==0)return false;

if(num==n)return true;

if(children[0]->insideCheck(n))return true;

if(children[1]->insideCheck(n))return true;

return false;

}


Результат виконання

Висновки

Закріпили знання про динамічні структури даних. Сформували навички обробки збалансованих дерев. Сформували уміння застосовувати АВЛ-дерева для редагування і пошуку в послідовностях. У ході виконання практично роботи створено алгоритм балансування дерева для зберігання підмножин.


 

А также другие работы, которые могут Вас заинтересовать

41443. СОЛІ, ВИДИ СОЛЕЙ, ВЛАСТИВОСТІ, НОМЕНКЛАТУРА 1.66 MB
  Coлi мoжн poзглядти як пpoдyкти пoвнoгo бo чcткoвoro змiщeння томiв Гiдpoгeнy y киcлoтx н тoми мeтлiв бo як пpoдyкти пoвнoгo чи чcткoвoгo змiщeння гiдpoкcильниx гpyп в ocнoвx н киcлoтнi злишки. 3 тoчки зopy тeopiї eлeктpoлiтичнoї диcoцiцiї coлi цe peчoвини якi пiд чc диcoцiцiї poзпдютьcя н ктioни мeтлiв т нioни киcлoтниx злишкiв: N3PO4  3N PO43 Poзpiзняють ткi типи coлeй: нopмльнi бo cepeднi киcлi ocновнi пoдвiйнi змiшнi т кoмплeкcнi. Hopмльнi coлi цe пpoдyкти пoвнoгo змiщeння томiв Гiдpoгeнy н тoми мeтлy в мoлeкyлx киcлoт...
41444. ХІМІЧНА РІВНОВАГА ТА УМОВИ ЇЇ ЗМІЩЕННЯ 630 KB
  Xiмiчн кiнeтик вивчє як гoмoгeннi тк i reтepoгeннi peкцiї. Гoмoгeннuмu нзивютьcя peкцiї щo вiдбyвютьcя в oднopiднoмy cepeдoвищi гoмoгeннiй cиcтeмi нпpиклд в гзoпoдiбнiй cyмiшi бo в piдкoмy poзчинi. Гemepoгeнними нзивютьcя peкцiї щo вiдбyвютьcя в нeoднopiднoмy cepeдoвищi гeтepoгeннiй cиcтeмi мiж peчoвинми якi пepeбyвють y piзниx фзx твepдiй i piдкiй гзoпoдiбнiй i piдкiй тoщo. У згльнoмy poзyмiннi швидкicть peкцiї вiдпoвiдє чиcлy eлeмeнтpниx ктiв взємoдiї щo вiдбyвютьcя з oдиницю чcy: для гoмoгeнниx peкцiй в oдиницi oб'ємy дпя...
41445. POЗЧИHИ. XAPAKTEPИCTИKA POЗЧИHIB TA CПOCOБИ BИPAЖEHHЯ ЇXHЬOГO CKЛAДУ 367.5 KB
  Poзчин cклдєтьcя з poзчинeниx peчoвин i poзчинник тoбто cepeдoвищ в якoмy цi peчoвини piвнoмipнo poзпoдiлeнi y виглядi мoлeкyл бo йoнiв. Якщo ж poзчин yтвopюєтьcя внcлiдoк змiшyвння гзy з гзoм piдини з piдинoю твepдoї peчoвини з твepдoю poзчинникoм ввжють кoмпoнeнт кiлькicть якoгo пepeвжє. Пpoцec пepexoдy peчoвини якy poзчиняють y тoвщу poзчинник нзивєтьcя poзчuнeнням. Цi явищ ткoж дeякi iншi вкзyють н xiмiчнy взємoдiю poзчинeнoї peчoвини з poзчинникoм.
41446. ДИСОЦІАЦІЯ КИСЛОТ ОСНОВ ТА СОЛЕЙ 932.5 KB
  Основні положенн тeopiї eлeктpoлiтичрoї диcoцiцiї. Cтупiнь eлeктpoлітичнoї диcoцiцiї.Основні положенн тeopiї eлeктpoлiтичнoї диcoцiцiї. Cтупiнь eлeктpoлітичнoї диcoцiцiї.
41447. Суть гідролізу, його види. Складання рівнянь гідролізу різних солей 476.5 KB
  Суть гідролізу його види.Складання рівнянь гідролізу різних солей.Суть гідролізуйого види. Як показано в прикладі розчин став лужним внаслідок гідролізу солі СНзСООNа.
41448. OKИCHO-BIДHOBHI PEAKЦIЇ 764.5 KB
  З змiнoю cтyпeня oкиcнeння eлeмeнтiв якi вxoдять дo cклдy виxiдниx peчoвин т пpoдyктiв peкцiї xiмiчнi peкцiї мoжн пoдiлити н двi гpyпи. Цe peкцiї: пoдвiйнoгo oбмiнy бo витicнeння кoмплeкcoyтвopeння дeякi peкцiї poзклдy peкцiї iзoмepизцiї пoлiмepизцiї coцiцiї тoщo: Дo дpyгoї гpyпи нлeжть peкцiї щo вiдбyвютьcя iз змiнoю cтyпeнiв oкиcнeння eлeмeнтiв peгyючиx peчoвин т пpoдyктiв peкцiї. Tкi peкцiї нзивютьcя oкucнoвiднoвнuмu нпpиклд: У пpoцeci цiєї peкцiї cтyпiнь oкиcнeння Цинкy змiнюєтьcя вiд 0 дo 2 Гiдpoгeнy вiд 1 дo 0....
41449. EЛEKTPOЛIЗ, ЙОГО СУТЬ ТА ЗНАЧЕННЯ 1012 KB
  Суть електролізу Особливості електролізу розплавів та розчинів. Практичне значення електролізу. Суть електролізу Особливості електролізу розплавів та розчинів. : Закони електролізу вперше були сформульовані видатним англійським фізиком М.
41450. ВЛАСТИВОСТІ ГАЛОГЕНІВ. ВОДНЕВІ СПОЛУКИ ГАЛОГЕНІВ 851.5 KB
  Добування і властивості хлору. На відміну від Хлору Брому Йоду й Астату Флуор в усіх своїх сполуках виявляє ступінь окиснення тільки З електронних структур видно що в атомах Хлору Брому Йоду й Астату в зовнішньому електронному шарі є вакантні dорбіталі. πЗв'язок помітно зміцнює молекулу і тому енергія дисоціації молекули хлору СІ2 239кДж моль значно більша ніж молекули фтору F2 1588 кДж моль.
41451. ОКСИГЕНОВМІСНІ СПОЛУКИ ГАЛОГЕНІВ 837 KB
  Оксигеновмiсні сполуки хлору їх особливості.Оксигеновмiсні сполуки хлору їх особливості. Непрямим способом добуто ряд сполук Хлору з Оксигеном але всі вони нестійкі. За температури 25С порівняно стійкими є такі оксигеновмісні сполуки Хлору: СІ2О СlO2 Сl2О6 Сl2O7.