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;

}


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

Висновки

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


 

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

36153. История создания русского музея 21.96 KB
  К таким несомненно относится учреждение и открытие Русского музея. Идея организации государственного музея национального искусства высказывалась и обсуждалась в образованной среде русского общества с середины XIX века. Уже в конце 1880х годов перед российским обществом встал вопрос о необходимости создания музея русского национального искусства как того требует современное процветание русского искусства и высокое положение занимаемое Россиею в образованном мире Записка обергофмаршала князя С.
36154. Валентин Пикуль “Портрет из Русского Музея” 86.93 KB
  Так появилась Ида Львовна Рубинштейн и скоро видный актер и педагог А. Ида Рубинштейн родилась в еврейской семье киевского миллионера сахарозаводчика. Ида сознавала обаяние своей поразительной красоты и казалось уже смолоду готовила себя к роли околдованно трагической. Ида Рубинштейн заметалась из театра в театр.
36155. Русский музей 34.32 KB
  Это Строгановский и Мраморный дворцы Михайловский Инженерный замок и главное здание музея величественный Михайловский дворец с корпусом Бенуа входящий в ансамбль одной из красивейших площадей Северной столицы площади Искусств. Покровитель всего русского Александр III вынашивал план создания в Михайловском дворце музея русского искусства и такой музей здесь был открыт. История создания Русского музея Основных источников поступлений в формирующуюся коллекцию музея было не так уж много. Да и Особая комиссия проводившая по поручению...
36156. Автоматизированные системы безналичных расчетов 499 KB
  Техническое обеспечение расчетных узлов предприятий торговли и сервиса в условиях функционирования АСБР и системы штриховой идентификации товаров и услуг На предприятиях торговли и сервиса используются: устройства крепления самоклеющихся этикеток для ручного крепления этикеток со штриховыми кодами ярлыков и этикеток для автоматического крепления со штриховыми кодами на различные товары машиночитаемых ярлыков для крепления с помощью механизированных зажимов; весовые терминалы для взвешивания снабжения самоклеющимися этикетками...
36157. Физические основы магнитооптической записи 72.5 KB
  В общем случае магнитооптический эффект это изменение оптических свойств вещества в зависимости от его намагниченности или от силы приложенного к нему магнитного поля. силовые линии магнитного поля образуемого ими перпендикулярны поверхности пленки. Если на вещество воздействует внешнее магнитное поле то носители магнетизма данного вещества сориентируются так что направления их магнитных моментов совпадут с направлением внешнего магнитного поля. Мерой изменения магнитного поля в веществе служит величина его магнитной проницаемости μ...
36158. Общие положения амплитудной модуляции (АМ). Основы инженерного расчёта генераторов с АМ смещением. Схемы модуляторов 422.5 KB
  Общие положения амплитудной модуляции (АМ). АМ смещением: принцип, схема, статические и динамические модуляционные характеристики. Энергетические и качественные показатели. Основы инженерного расчёта генераторов с АМ смещением. Схемы модуляторов.
36159. СПОСОБЫ ПУСКА, РЕГУЛИРОВАНИЯ ЧАСТОТЫ ВРАЩЕНИЯ И ТОРМОЖЕНИЯ ЭЛЕКТРОПРИВОДОВ ПОСТОЯННОГО ТОКА 244.51 KB
  Способы пуска электродвигателей постоянного тока влияние против ЭДС обмотки якоря. Способы регулирования частоты вращения электродвигателей постоянного тока. Электрическое торможение двигателей постоянного тока
36160. Способы пуска электродвигателей переменного тока 277.32 KB
  Прямой пуск короткозамкнутых асинхронных двигателей нормального исполнения Прямой пуск короткозамкнутых асинхронных двигателей специального исполнения Реостатный пуск двигателей с фазным ротором Пуск при пониженном напряжении на обмотке статора
36161. HDD-РЕКОРДЕРЫ 157 KB
  К каждой стороне диска на специальных вращающихся кронштейнах коромыслах подводятся магнитные головки с помощью которых и осуществляется запись и считывание данных рис. Поверхности диска должны быть идеально плоскими и тщательно отполированными. Кронштейны с головками могут поворачиваться вокруг оси на которой они закреплены и головки размещенные на их концах могут таким образом устанавливаться на любую дорожку диска. Кронштейн слегка подпружинен и его конец с закрепленными головками в отсутствии вращения диска должен соприкасаться с...