3. 2-3 Дерево.
Текст программы для ключа -размера: 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;
}
Тесты.
|
Ключ |
Размер файла |
Имя файла |
|
Время построения дерева |
1045 |
3430 |
|
Высота |
10 |
12 |
|
Кол-во узлов |
128200 |
128200 |
|
Минимальный элемент |
Имя:lol.txt Размер: 0 |
Имя taz.bmp Размер: 1438 |
|
Максимальный элемент |
Имя : tree.sys Размер: 6775930880 |
Имя: sdd.lnk Размер : 1142 |
|
время на сортировку |
85 |
69 |
|
Время на поиск элементов |
Средний случай= 0 Худший случай= 0 |
Средний случай= 0 Худший случай= 0 |