Бинарное дерево поиска

Лабораторная работа №4

по дисциплине «Методы построения и анализа алгоритмов»

на тему " Деревья"

Факультет: ПМИ

Группа: ПМИ-21

Студент: Давыдов Д.В.

Преподаватель: Щукин Г.А.

Новосибирск

Задание.

1. Пирамидальная сортировка. Реализовать пирамидальную сортировку. Провести

тест для массива строк, сравнить с другими сортировками (время выполнения, число обменов и сравнений).

БДП

Получить полный список файлов для некоторого каталога и всех его подкаталогов (например, со своего компьютера). Для имени и размера файла (ключи) построить бинарное дерево поиска и найти:

· высоту и кол-во узлов получившегося дерева

· время на построение дерева

· мин. и макс. элементы (+ имена соотв. файлов)

· время поиска произвольных элементов в дереве

· (средний и худший варианты; сравнить со временем обычного поиска в исходном списке)

· время на сортировку

3. Реализовать сбалансированное дерево поиска (2-3 дерево). Провести тесты из предыдущего пункта и сравнить результаты.

Пирамидальная сортировка.

Сначала строим дерево (пирамиду) с учетом того,что самый наибольший элемент из множества(/наименьший) будет находится в корне дерева. После меняем последний элемент с корнем, и строим заново пирамиду, но уже из множества, в котором нет последнего элемента. И так повторяем, пока не отсортируем весь массив.

Оценка сложности. Максимальный/минимальный элемент из неотсортированного множества выбирается за O(log n). Тогда общее быстродействие сортировки будет

n* O(log n)= O(n log n).

Реализация.

построение пирамиды.

void siftDown(int i, int j)

{

bool done = false;

int maxChild;

char temp[mx];

while ((i * 2 < j) && (!done))

{

if (i * 2 == j)

maxChild = i * 2;

else

if (strcmp(A[i*2],A[i*2+1])>0)

maxChild = i * 2;

else

maxChild = i * 2 + 1;

if (strcmp(A[i],A[maxChild])<0)

{

strcpy(temp,A[i]);

strcpy(A[i],A[maxChild]);

strcpy(A[maxChild],temp);

i = maxChild;

change++;

}

else

{

done = true;

}

comparison++;

}

}

void HeapSort()

{

int size=input()-1;

int i;

char tmp[mx];

for (i = (size / 2) - 1; i >= 0; i--)

{

siftDown(i,size);

}

for (i = size - 1; i >= 1; i--)

{

strcpy(tmp,A[0]);

strcpy(A[0],A[i]);

strcpy(A[i],tmp);

change++;

siftDown(0,i-1);

}

}

Тестирование и сравнение результатов.

Тип сортировки	Количество элементов	Время	Количество сравнений	Количество обменов
Выбором		2,69
Вставками	0,69
Слияние	0,008
Быстрая	0,0012
Пирамидальная	0,22
Выбором		13,75
Вставками	3,78
Слиянием	0,06
Быстрая	0,05
Пирамидальная	0,828
Слияние		0,11
Быстрая	0,10
Пирамидальная	1,6680
Слияние		1,244
Быстрая	0,792
Пирамидальная	17,3510

Бинарное дерево поиска.

Дерево поиска – это двоичное дерево, в котором выполняются следующие условия

а) l(u) < l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого – левый преемник v;

б) l(u) > l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого – правый преемник v;

в) для всякого значения aÎ S существует единственная вершина v, для которой l(v) = a

Реализация программы

struct elem

{

char s[50];

int size;

public:

bool operator>(info d)

{ return (strcmp(s, d.s) == 1);}

};

struct tree

{

elem el;

tree *left;

tree *right;};

//добавление элемента в бинарное дерево поиска по ключу - строка

void IncludeString(tree **t,info w)

{

tree *q,*r,*z=NULL;

if (!(*t))

{

*t = new tree;

(*t)->el =w;

(*t)->left = NULL;

(*t)->right = NULL;

}

else

{

q = *t;

while (q)

{

z = q;

if (q->el>w)

q = q->left;

else

q = q->right;

}

r = new tree;

r->el = w;

r->left = NULL;

r->right = NULL;

if (z->el>w)

z->left = r;

else

z->right = r;

}

}

//добавление элемента в бинарное дерево поиска по ключу - размер

void IncludeSize(tree **t, elem w)

{

tree *q, *r, *z=NULL;

if (!(*t))

{

*t = new tree;

(*t)->el = w;

(*t)->left = NULL;

(*t)->right = NULL;

}

else

{

q = *t;

while (q)

{

z = q;

if (q->el.size>w.size)

q = q->left;

else

q = q->right;

}

r = new tree;

r->el = w;

r->left = NULL;

r->right = NULL;

if (z->el.size>w.size)

z->left = r;

else

z->right = r;

}

}

//поиск данного элемента по строке в бинарном дереве поиска

void search_elem_String(tree *t, elem w)

{

tree *q = t;

while (q)

{

if (w > q->el)

q = q->right;

else

if (q->el > w)

q = q->left;

else

return;

}

}

//поиск данного элемента по размеру в бинарном дереве поиска

void search_elem_size(tree *t, elem w)

{

tree *q = t;

while (q)

{

if (w.size > q->el.size)

q = q->right;

else

if (q->el.size > w.size)

q = q->left;

else

{

q = q->right;

}

}

}

//поиск максимального элемента в бинарном дереве поиска

info search_max(tree *t)

{

tree *q = t;

while (q->right)

{

q = q->right;

}

return q->el;

}

//поиск минимального элемента в бинарном дереве поиска

info search_min(tree *t)

{

tree *q = t;

while (q->left)

{

q = q->left;

}

return q->el;

}

//поиск высоты бинарного дерева поиска

void heightTree(tree *t,int i)

int max=0;

if (t!= NULL)

{

if (i > max) max = i;

heightTree(t->left, ++i);

i--;

heightTree(t->right, ++i);

i--;

}

}

//сортировка

void sort(tree *t, FILE *in)

{ if (t)

{

sort(t->left,in);

fprintf(in, "%ld\n", t->el.size);

sort(t->right, in);

}

}

Результаты.

Ключ	Высота	Кол-во узлов	Мин. элемент	Макс. элемент	Время на построение	Время на сортировку
Имя			Имя:taz.bmp Размер: 1438	Имя: Онлайн-регистрация продукта ASUS.lnk Размер: 1142
Размер			Имя:lol.txt Размер: 0	Имя: hiberfil.sys Размер: 6775930880

Поиск элемента по размеру

Среднего: 1343
Худшего: 3543

Поиск элемента ключ- имя файла

Среднего: 812
Худшего: 1543

Дерево.

Текст программы для ключа -размера:
struct info

#include <stdio.h>

struct info

{

char s[40];

int size;

};

enum nodetype{ leaf, interior };

struct two_three

{

nodetype kind;

info inf;

two_three *left;

two_three *midle;

two_three *right;

int lows;

int lowt;

};

enum nodetype{ leaf, interior };

struct two_three

{

nodetype kind;

info inf;

two_three *left;

two_three *midle;

two_three *right;

int lows;

int lowt;

};

info search(two_three * node, long long int id) //поиск в 2-3 дереве

{

info x;

if (node!= NULL)

{

if (node->kind == interior)

{

if (id<node->lows) x = search(node->left, id);

else if (node->right == NULL) x = search(node->midle, id);

else if (id<node->lowt) x = search(node->midle, id);

else x = search(node->right, id);

}

else if (id == node->inf.size) x = node->inf;

}

return x;

}

void insert1(two_three * node, info x, two_three **pnew, int *low)

{ //поиск места для добавления и определение

two_three * pback; // возможной перестройки дерева

int lowback;

int child;

two_three * w;

*pnew = NULL;

if (node->kind == leaf)

{

if (node->inf.size!= x.size)

{

*pnew = new two_three;

(*pnew)->kind = leaf;

if (node->inf.size<x.size)

{

(*pnew)->inf = x; *low = x.size;

}

else

{

(*pnew)->inf = node->inf;

node->inf = x;

*low = (*pnew)->inf.size;

}

}

}

else

{

if (x.size<node->lows)

{

child = 1; w = node->left;

}

else if ((node->right == NULL) || (x.size<node->lowt))

{

child = 2;

w = node->midle;

}

else

{

child = 3;

w = node->right;

}

insert1(w, x, &pback, &lowback);

if (pback!= NULL)

{

if (node->right == NULL)

if (child == 2)

{

node->right = pback;

node->lowt = lowback;

}

else

{

node->right = node->midle;

node->lowt = node->lows;

node->midle = pback;

node->lows = lowback;

}

else

{

*pnew = new two_three;

(*pnew)->kind = interior;

if (child == 3)

{

(*pnew)->left = node->right;

(*pnew)->midle = pback;

(*pnew)->right = NULL;

(*pnew)->lows = lowback;

*low = node->lowt;

node->right = NULL;

}

else

{

(*pnew)->midle = node->right;

(*pnew)->lows = node->lowt;

(*pnew)->right = NULL;

node->right = NULL;

}

if (child == 2)

{

(*pnew)->left = pback;

*low = lowback;

}

if (child == 1)

{

(*pnew)->left = node->midle;

*low = node->lows;

node->midle = pback;

node->lows = lowback;

}

}

}

}

}

void insert(info x, two_three **root) //добавление в 2-3 дерево

{

two_three * pback;

int lowback;

two_three * saves;

if (*root == NULL)

{

*root = new two_three;

(*root)->kind = leaf;

(*root)->inf = x;

}

else

{

insert1(*root, x, &pback, &lowback);

if (pback!= NULL)

{

saves = *root;

*root = new two_three;

(*root)->kind = interior;

(*root)->left = saves;

(*root)->midle = pback;

(*root)->lows = lowback;

(*root)->right = NULL;

}

}

}

void sort(two_three *d,FILE *out) //сортировка

{

if (d->kind == interior)

{

sort(d->left, out);

sort(d->midle, out);

if (d->right) sort(d->right, out);

}

else fprintf(out, "%d\n", d->inf.size);

}

int height(two_three *d) // высота дерева

{

int i = 0;

do

{

i++;

d = d->left;

}

while (d->kind == interior);

return i;

}

info max(two_three *d) // максимум в дереве

{

if (d->kind == interior)

if (d->right)

max(d->right);

else max(d->midle);

else return d->inf;

}

info min(two_three *d) // минимум в дереве

{

if (d->kind == interior)

min(d->left);

else return d->inf;

}
Текст программы для ключа -имени:
struct info

{

char s[40];

int size;

public:

bool operator>(char t[])

{

return (strcmp(s, t) == 1);

}

bool operator<(char t[])

{

return (strcmp(s, t) == -1);

}

bool operator==(char t[])

{

return (strcmp(s, t) == 0);

}

}P[N];

enum nodetype{ leaf, interior };

struct two_three

{

nodetype kind;

info inf;

two_three *left;

two_three *srednee;

two_three *pravoe;

char lows[40];

char lowt[40];

};

info search(two_three * node, info id)

{

info x;

if (node!= NULL)

{

if (node->kind == interior)

{

if (id<node->lows) x = search(node->left, id);

else if (node->pravoe == NULL) x = search(node->srednee, id);

else if (id < node->lowt) x = search(node->srednee, id);

else x = search(node->pravoe, id);

}

else if (id == node->inf.s) x = node->inf;

}

return x;

}

void insert1(two_three *node, info x, two_three **pnew, char low[])

{

two_three * pback;

char lowback[40];

int child;

two_three * w;

*pnew = NULL;

if (node->kind == leaf)

{

if!(x==node->inf.s))

{

*pnew = new two_three;

(*pnew)->kind = leaf;

if (x>node->inf.s)

{

(*pnew)->inf = x;

strcpy(low, x.s);

}

else

{

(*pnew)->inf = node->inf;

node->inf = x;

strcpy(low, (*pnew)->inf.s);

}

}

}

else

{

if (x<node->lows)

{

child = 1; w = node->left;

}

else if ((node->pravoe == NULL) || (x<node->lowt))

{

child = 2;

w = node->srednee;

}

else

{

child = 3;

w = node->pravoe;

}

insert1(w, x, &pback, lowback);

if (pback!= NULL)

{

if (node->pravoe == NULL)

if (child == 2)

{

node->pravoe = pback;

strcpy(node->lowt, lowback);

}

else

{

node->pravoe = node->srednee;

strcpy(node->lowt, node->lows);

node->srednee = pback;

strcpy(node->lows, lowback);

}

else

{

*pnew = new two_three;

(*pnew)->kind = interior;

if (child == 3)

{

(*pnew)->left = node->pravoe;

(*pnew)->srednee = pback;

(*pnew)->pravoe = NULL;

strcpy((*pnew)->lows, lowback);

strcpy(low,node->lowt);

node->pravoe = NULL;

}

else

{

(*pnew)->srednee = node->pravoe;

strcpy((*pnew)->lows, node->lowt);

(*pnew)->pravoe = NULL;

node->pravoe = NULL;

}

if (child == 2)

{

(*pnew)->left = pback;

strcpy(low,lowback);

}

if (child == 1)

{

(*pnew)->left = node->srednee;

strcpy(low, node->lows);

node->srednee = pback;

strcpy(node->lows, lowback);

}

}

}

}

}

void insert(info x, two_three **root)

{

two_three * pback;

char lowback[40];

two_three * saves;

if (*root == NULL)

{

*root = new two_three;

(*root)->kind = leaf;

(*root)->inf = x;

}

else

{

insert1(*root, x, &pback, lowback);

if (pback!= NULL)

{

saves = *root;

*root = new two_three;

(*root)->kind = interior;

(*root)->left = saves;

(*root)->srednee = pback;

strcpy((*root)->lows,lowback);

(*root)->pravoe = NULL;

}

}

}

void sort(two_three *d,FILE *out)

{

if (d->kind == interior)

{

sort(d->left, out);

sort(d->srednee, out);

if (d->pravoe) sort(d->pravoe, out);

}

else fprintf(out, "%s\n", d->inf.s);

}

int height(two_three *d)

{

int i = 0;

do

{

i++;

d = d->left;

}

while (d->kind == interior);

return i;

}

Тесты.