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;

}


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

Висновки

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


 

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

74237. ДВЕ МОДЕЛИ ХОЗЯЙСТВЕННОГО РАЗВИТИЯ: ДРЕВНЕВОСТОЧНАЯ ЭКОНОМИКА И АНТИЧНОЕ ХОЗЯЙСТВО 58.5 KB
  Отличительной чертой восточного типа хозяйства являлась государственная собственность на землю и ирригационные сооружения. В Древнем Египте регулярно проводились переписи населения и хозяйства в основном для распределения трудовой повинности. Это обусловило невысокий уровень развития хлебопашества в греческих полисах постоянный переход от зернового хозяйства к интенсивному виноградарству и садоводству. Хозяйства носили как правило многоотраслевой характер.
74238. Факторы самобытности в развитии Российской цивилизации 32 KB
  Ее основными элементами были: Община как первичная хозяйственно-социальная ячейка а не как частнособственническое образование как на Западе; Государство с его особой ролью организатора и творца гражданского общества. Но государство было одновременно и сильным и слабым. Слабость проявлялась в чрезвычайно низком коэффициенте полезного действия : государство не смогло создать стабильного общества и само неоднократно разрушалось. В то же время это слабое несовершенное государство было единственным интегратором и организатором общества и...
74239. Великие географические открытия и их результаты 133 KB
  Географические открытия Рост научных знаний Рост производства и появление мануфактур Развитие торговли и складывание европейского и мирового рынка Становление абсолютистских государств Реформация В чем значение эпохи великих географических открытий и каковы ее результаты приведшие к качественным изменениям в мировом развитии Cредневековая Европейская цивилизация замыкалась в узкие рамки европейской территории. Бурное развитие заморской торговли породило акционерные компании имевшие постоянный капитал и боровшиеся за монопольное...
74240. Возбудители гнойно - воспалительных процессов. Стафилококки 717 KB
  Подавляющее большинство гнойно - воспалительных заболеваний вызывают кокки, т.е. имеющие сферическую (шаровидную) форму микроорганизмы. Их делят на две большие группы - грамположительные и грамотрицательные. Внутри этих групп выделяют аэробные и факультативно - анаэробные кокки и анаэробные кокки.
74241. История развития микробиологии, вирусологии и иммунологии. Предмет, методы, задачи 547 KB
  По наличию и строению клеток вся живая природа может быть разделена на прокариоты не имеющие истинного ядра эукариоты имеющие ядро и не имеющие клеточного строения формы жизни. Колония видимая изолированная структура при размножении бактерий на плотных питательных средах может развиваться из одной или нескольких родительских клеток. Деление этих микроорганизмов происходит в одной плоскости образуются пары клеток. Деление в трех взаимоперпендикулярных плоскостях образуя тюки пакеты из 8 16 и большего количества клеток.
74242. ОСНОВЫ АЛГОРИТМИЗАЦИИ 592.5 KB
  В основе любой программы лежит алгоритм. Таблица Изображение блоков в схемах алгоритмов Наименование символа Обозначениеи размеры Функция Процессвычислительный блок Выполнение операции или группы операций в результате которых изменяются значение форма представления или расположение данных Решение логический блок Выбор направления выполнения алгоритма в зависимости от некоторых условий Модификация заголовок цикла Выполнение операций по управлению циклом – повторением команды или группы команд алгоритма Пускостанов началоконец...
74243. Алгоритмы вычисления определенных интегралов 1.27 MB
  Основу численных методов вычисления определенных интегралов составляет их геометрический смысл. В этом случае подынтегральную функцию кривую заменяют прямой а формула для вычисления площади прямоугольника известна. приведена схема алгоритма реализующего вычисления по формуле прямоугольников слева.
74244. Базы данных и их классификация 158 KB
  База данных – это совокупность связанных данных организованных по определенным правилам предусматривающим общие принципы описания хранения и манипулирования независимая от прикладных программ.
74245. ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ 280 KB
  Структура вычислительной сети Узел – это любое устройство непосредственно подключенное к передающей среде сети. Каждый узел в сети имеет минимум два адреса: физический используемый оборудованием и логический используемый пользователями и приложениями. Здесь сообщение – это целостная последовательность данных передаваемых по сети.