Министерство общего и профессионального образования Российской Федерации
НГТУ
Кафедра ВТ
Лабораторная работа №2
Группа: АМ-110
Студенты:
Вариант: 7
Проверила :
Новосибирск, 2003г.
Задание: АТД " Рандомизированное дерево" - модификация АТД "Рекурсивное дерево двоичного поиска.
АТД BTree
Данные
Структура данных: рекурсивное дерево двоичного поиска;
Размер дерева: количество значений, находящихся в данный момент в дереве;
Область значений в дереве: любые целочисленные значения.
Операции:
Конструктор
Начальные значения: null–значение данных.
Процесс: создание корня дерева – root.
Size
Вход: корень дерева.
Предусловие корень дерева
null значению.
Процесс: обход двоичного дерева.
Выход: размер дерева; 0 - если не выполнено предусловие.
Постусловие: нет.
Empthy
Вход: нет.
Предусловие: корень дереваnull значению.
Процесс: нет
Выход: логическое значение true, если дерево не пустое;
логическое значение false, если дерево пустое.
Постусловие: нет.
Clear
Вход: корень дерева.
Предусловие: корень дереваnull значению.
Процесс: удаление всех значений из дерева.
Выход: нет.
Постусловие: дерево пустое.
Find
Вход: корень дерева и значение, которое нужно найти в дереве.
Предусловие: корень дереваnull значению.
Процесс: обход дерева для нахождения указанного значения.
Выход: логическое значение true, если заданное значение найдено,
логическое значение false, если заданное значение не найдено.
Постусловие: нет.
Insert:
Вход: корень дерева, значение для вставки, признак вставки.
Предусловие: нет.
Процесс: добавление значения в дерево с сохранением упорядоченности дерева. Значение не вставится, если оно уже имеется в дереве.
Выход: узел со вставленным значением, если значение вставлено,
узел с имеющимся значением, если значение не вставлено.
Постусловие: дерево имеет новый узел с указанным значением
Delete:
Вход: корень дерева, удаляемое значение и признак удаления.
Предусловие: корень дереваnull значению.
Процесс: обход дерева и удаление указанного значения.
Выход: корень дерева, если значение удалено.
null значение, если не выполнено предусловие.
Постусловие: если значение удалено, размер дерева уменьшается на один узел.
Конец АТД BTree.
АТД RandomTree
Данные
Структура данных: рандомизированное дерево на базе рекурсивного дерева двоичного поиска;
Размер списка: количество значений, находящихся в данный момент в дереве;
Область значений в дереве: любые целочисленные значения.
Операции:
Конструктор
Начальные значения: null–значение данных.
Процесс: создание корня дерева - root
Insert:
Вход: корень дерева, значение для вставки и признак вставки.
Предусловие: нет.
Процесс: добавление значения в дерево с сохранением упорядоченности дерева. При вставке нового узла в дерево, состоящее из N узлов, вероятность появления нового значения в корне равняется 1/(N+1), в противном случае используется алгоритм вставки в двоичное дерево. Значение не вставится, если оно уже имеется в дереве.
Выход: корень дерева, если значение вставлено,
корень дерева и отрицательный признак, если значение не вставлено.
Постусловие: дерево имеет новый узел с указанным значением.
Delete:
Вход: корень дерева, удаляемое значение и признак удаления.
Предусловие: корень дереваnull значению
Процесс: обход дерева и удаление указанного значения. Не выполнятся никакое действие, если предусловие не выполняется.
Выход: корень дерева, если значение удалено.
null значение, если не выполнено предусловие.
Постусловие: если значение удалено, размер дерева уменьшается на один узел.
Конец АТД RandomTree.
Текст программы:
#include <iostream. h>
#include <stdlib. h>
int count;
template <class T>
//узел
class node
{
public:
T data;
int level;
node <T>*left,*right;
node(T d)
{
left=right=NULL;data=d; level=1;
}
};
//класс "бинарное" дерево
template <class T>
class BTree
{protected:
unsigned long int test_ins; //счетчики для тестирования программы
unsigned long int test_del;
unsigned long int test_find;
public:
node <T> *root;
BTree(){root=NULL;}
~BTree(){}
int Size(node<T> *n)
{ if (n==NULL) return 0;
return Size(n->left)+Size(n->right)+1;
}
//*****Проверка на пустоту*****
bool Empty()
{ if (root==NULL) return true;
return false;
}
//*****Поиск*****
bool Find(node<T>*n, T d)
{test_find++;
if(n==NULL)return false;
if(d < n->data)
{if(Find(n->left, d)) {::count++;return true;}
else return false;}
if(d > n->data)
{if(Find(n->right, d)){::count++;return true;}
else return false;}
if(d == n->data)return true;
return false;
}
//Вставка*******
node <T>* Insert(node <T> *n, T d, bool &insok)
{ insok=false;test_ins++;
if (n==NULL) {insok=true;n=new node<T>(d);root=n;return n;}
if (d<n->data)
{if (n->left==NULL){insok=true; n->left=new node<T>(d);return n->left;}
else { Insert(n->left, d, insok);}
}
if (d>n->data)
{if (n->right==NULL){insok=true;n->right=new node<T>(d);return n->right;}
else {Insert(n->right, d,insok);}
}
return n;
}
//*******Вывод на экран*
void Print(node <T> *n, int level)
{
if (n==NULL) return;
Print (n->right, level+1);
for (int i=0;i<level;i++) cout << " ";
cout << n->data << endl;
Print (n->left, level+1);
}
//*******Удаление*******
node <T>* Delete(node<T>*n, T d, bool &delok)
{ test_del++;delok=false;
if(n==NULL) return NULL; node <T>*tmp;
if(d<n->data) {n->left=Delete(n->left, d, delok); return n;}
if(d>n->data) {n->right=Delete(n->right, d,delok); return n;}
delok=true;
if(n->left==NULL && n->right==NULL){ if(n==root){delete n; root = NULL;}
else delete n;delok=true; return NULL;}
if(n->left==NULL) { tmp=n->right; if(n==root){delete n; root = tmp; return NULL;}
else delete n; delok=true;return tmp;}
if(n->right==NULL){ tmp=n->left; if(n==root){delete n; root = tmp; return NULL;}
delete n; delok=true; return tmp;}
n->right=Del(n->right, n); return n;
}
node <T>*Del(node <T>*nn, node <T>*n0)
{ if(nn->left!=NULL){nn->left=Del(nn->left, n0); return nn;}
n0->data=nn->data; node <T>*temp=nn->right; delete nn; return temp;
}
//**очистка******
void Clear(node<T> *n)
{ bool del;
if (n==NULL) return;
Clear(n->left);
Clear(n->right);
Delete(root, n->data, del);
}
//**
unsigned long int GetTestIns(){return test_ins;}
unsigned long int GetTestDel(){return test_del;}
unsigned long int GetTestFind(){return test_find;}
void ClearTestValues(){ test_ins=test_del=test_find=0;}
};
template <class T>
class RandomTree: public BTree <T>
{bool okins;
public:
RandomTree():BTree <T>(){}
~RandomTree(){}
node<T>* Insert(node <T> *n, T d, bool &okins)
{ test_ins++;okins=false;
if(n == NULL){ okins=true;n=new node <T>(d);return n; }
if(d==n->data){okins=false;return n;}
if(rand() < RAND_MAX/(n->level+1))
{okins=true; n=InsertT(n, d); n->level=n->level+1; return n;}
if(d< n->data) { okins=true; n->left=Insert(n->left, d,okins);}
if (d> n->data) { okins=true; n->right=Insert(n->right, d,okins);}
n->level=n->level+okins;
return n;
}
node <T>* InsertT(node <T>*nn, T d)
{test_ins++;
if(nn==NULL) {return new node <T>(d); }
if(d<nn->data) { nn->left =InsertT(nn->left, d); return RotR(nn); }
if(d>nn->data) { nn->right=InsertT(nn->right, d);return RotL(nn); }
return nn;
}
node <T>*RotR(node <T> *nn) {node <T> *temp=nn->left; nn->left=temp->right; temp->right=nn; return temp;}
node <T>* RotL(node <T>*nn) {node <T> *temp=nn->right; nn->right=temp->left; temp->left=nn; return temp;}
node <T>* Delete(node <T>*n, T k, bool &delok)
{ test_del++; delok=false;
if(n==NULL)return NULL;
if(k<n->data) {delok=true;n->left=Delete(n->left, k, delok); return n;}
if(k>n->data) {delok=true; n->right=Delete(n->right, k,delok); return n;}
node<T> *temp=n; delok=true;
n=Random_JoinLR(n->left, n->right);
delete temp;return n;
}
node <T> *Random_JoinLR (node <T>*a, node <T>*b)
{ test_del++;
if(a==NULL) return b;
if(b==NULL) return a;
if(rand()/(RAND_MAX/(a->level+b->level+1))<a->level)
{a->right=Random_JoinLR(a->right, b); return a;}
else { b->left=Random_JoinLR(a, b->left); return b;}
}
};
Модуль main. cpp:
#include "class. h"
#include <conio. h>
#include <stdlib. h>
#include <time. h>
#include <fstream. h>
int main()
{
BTree <int> t; long tmp, tmp1; int h, cnt=0,cnt1=0, cnt2=0,cntt=0,cnt3=0,cnttt=0,flag=1;
RandomTree <int> tt; bool k;
int val;
while(1)
{ cout<<"\n#######################################################################"<<endl;
cout<<"BTree: 1 - Print List 2 - Insert elem 3 - Delete elem 4 - Search elem"<<endl;
cout<<"BTree: 5 - Clear List 6 - Size List 8 - Test Tree "<<endl;
cout<<"RandomTree: q - Print List w - Insert elem e - Delete r - Search elem"<<endl;
cout<<"RandomTree: t - Clear List y - Size List 0 - Exit"<<endl;
switch(getch())
{case '0':return 0;
case '1': t. Print(t. root,0); break;
case '2': cout<<"Input value:";cin>>val;
t. Insert(t. root, val, k);if(k==false)cout<<"Elem exists in tree "<<endl ; break;
case '3': cout<<"Input value:";cin>>val;
t. Delete(t. root, val, k); if(k==false)cout<<"Elem is apsend "<<endl;
break;
case '4': count=0;cout<<"Input value:";cin>>val;
if (t. Find(t. root, val)==true)
cout<<"Element`s depth="<<count<<endl;
else cout<<"Element is not in tree\n";
break;
case '5': t. Clear(t. root);t. root=NULL; break;
case '6': cout<<t. Size(t. root)<<endl; break;
//**--RandomTree--*
case 'q': tt. Print(tt. root,0); break;
case 'w': cout<<"Input value:";cin>>val;
tt. root=tt. Insert(tt. root, val, k); if(k==false)cout<<"Elem exists in tree "<<endl ; break;
case 'y': if(tt. root!=NULL)cout<<tt. Size(tt. root)<<endl;else cout<<"0"<<endl; break;
case 'e': cout<<"Input value:";cin>>val;
tt. root=tt. Delete(tt. root, val, k);
if(k==false)cout<<"Elem is apsend "<<endl;break;
case 'r': count=0;cout<<"Input value:";cin>>val;
if (tt. Find(tt. root, val)==true)
cout<<"Element`s depth="<<count<<endl;
else cout<<"Element is not in tree\n";
break;
case 't': tt. Clear(tt. root);break;
//*
case '8': t. Clear(t. root); tt. Clear(tt. root);
cout<<"Input enum elem: "<<flush; cin>>tmp;
for(h=0;t. Size(t. root)<tmp;h++)
{tmp1=rand();
t. Insert(t. root, tmp1,k);
tt. root=tt. Insert(tt. root, tmp1,k);
}
t. ClearTestValues(); tt. ClearTestValues();
cout<<"Size: BTree: "<<t. Size(t. root)<<" RandTree:"<<tt. Size(tt. root)<<endl;
cout<<"Input enum elem: "<<flush; cin>>tmp;
for(h=0;h<tmp;h++)
{tmp1=rand();
flag=1;
while(flag){tmp1=rand(); t. Insert(t. root, tmp1,k);if(k==true)flag=0; else cnt++;}
flag=1;
while(flag){tmp1=rand(); tt. root=tt. Insert(tt. root, tmp1,k); if(k==true)flag=0; else cntt++;}
flag=1;
while(flag){tmp1=rand(); if(t. Find(t. root, tmp1)==true)flag=0; else cnt1++;}
flag=1;
while(flag){tmp1=rand(); if(tt. Find(tt. root, tmp1)==true)flag=0; else cnttt++;}
flag=1;
while(flag){tmp1=rand(); t. Delete(t. root, tmp1,k); if(k==true)flag=0; else cnt2++;}
flag=1;
while(flag){tmp1=rand(); tt. root=tt. Delete(tt. root, tmp1,k); if(k==true)flag=0; else cnt3++;}
}// cout<<cnt<<" "<<cnt1<<" "<<cnt2<<endl;
cout<<"Insert: BTree: "<<(double)t. GetTestIns()/(double)(h+cnt)<< " RandTree: "<<(double)tt. GetTestIns()/(double)(h+cntt)<<endl;
cout<<"Find: BTree: "<<(double)t. GetTestFind()/(double)(h+cnt1)<<" RandTree: "<<(double)tt. GetTestFind()/(double)(h+cnttt)<<endl;
cout<<"Delete: BTree: "<<(double)t. GetTestDel()/(double)(h+cnt2)<< " RandTree: "<<(double)tt. GetTestDel()/(double)(h+cnt3)<<endl;
cout<<"Size list after testing: BTree: "<<t. Size(t. root)<<" RandTree: "<<tt. Size(tt. root)<<endl;
cnttt=cntt=cnt=cnt1=cnt2=cnt3=0;break;
}} return 0;
}
Диаграммы, полученные в процессе тестирования бинарного и рандомизированного деревьев:
Диаграммы, полученные в процессе вырожденного тестирования бинарного дерева:
Рандомизированного дерева:
